알고리즘 문제풀이/백준
-
[백준/BOJ] 1764번 듣보잡 (C++)알고리즘 문제풀이/백준 2020. 12. 1. 14:04
www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net map 자료구조를 이용하는 쉬운 문자열 문제입니다. 이름을 key값, 이름이 나오는 수를 value로 설정합니다. n과 m만큼 반복문을 돌려 입력받은 문자열을 map의 key로 둬 값을 증가시키고, 이름이 2번 이상 나온경우 듣보잡이므로 해당 값을 벡터에 넣어 정렬 후 출력하면 간단하게 해결할 수 있습니다. #include #include #include using namespace std; int main(..
-
[백준/BOJ] 1941번 소문난 칠공주 (C++)알고리즘 문제풀이/백준 2020. 12. 1. 13:48
www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 새롭게 알게된 점 십자가 모양은 일반적인 DFS + 백트래킹으로 문제를 해결할 수 없다. DFS와 BFS를 같이 쓰는 문제가 존재한다. (이번 문제가 그러했음) 문제를 해결하는 순서는 다음과 같습니다. 1. 학생 25명중 7명을 선택하는 조합을 DFS를 통해 구하기 2. 해당 조합에서 다솜이파 학생이 4명 이상인지 확인하는 isMoreThanFour() 함수 구현 3. 해당 조합에서 선택된 학생이 인접한지 확인하는..
-
[백준/BOJ] 9663번 N-Queen (C++)알고리즘 문제풀이/백준 2020. 11. 30. 22:38
www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 전형적인 DFS + 백트래킹 문제 하나의 행에 퀸을 하나만 넣을 수 있으므로 열마다 퀸을 넣어보고 현재 위치를 기준으로 위, 왼쪽 위 대각선, 오른쪽 위 대각선을 검사합니다. 행이 n에 도달할 때 마다 하나의 경우의 수가 완성되므로 answer 값을 더해줍니다. #include using namespace std; int n,res; bool map[15][15]; bool isPossible(int row, int col) ..
-
[백준/BOJ] 1799번 비숍 (C++)알고리즘 문제풀이/백준 2020. 11. 30. 22:14
www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 난이도 높은 DFS + 백트래킹 문제 처음에 N-Queen 문제처럼 접근했는데 시간초과가 발생했습니다. 시간초과가 발생하는 이유는 입력받은 값이 전부 1일 때 최악의 경우 2^10*10의 시간복잡도를 가질 수 있기 때문이라고 합니다. 따라서 이 문제를 해결하기 위해서는 체스판의 검은 칸, 흰칸을 나누어 DFS를 진행하는 것입니다. 그러면 시간 복잡도가 2^5*5+2^5*5로 확연히 줄어듭니다. 이러한 접근법을 생각해내는..
-
[백준/BOJ] 17071번 숨바꼭질 5 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:30
www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 굉장히 난이도가 있는 BFS 문제, 일반적인 BFS 접근으로는 위의 문제를 해결할 수 없습니다... 문제를 해결하기 위한 포인트는 수빈이가 짝수초에 접근한 위치는 짝수초에 또 방문할 수 있고, 홀수초에 접근한 위치는 홀수초에 또 방문할 수 있다는 것입니다. 그러므로 현재 수빈이의 위치를 중심으로 시간이 지날 때 마다 몇초에 해당 위치를 최초로 방문하게 되는지 기록하고, 시간..
-
[백준/BOJ] 13913번 숨바꼭질 4 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:29
www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기존 숨바꼭질 문제에 최소 시간이 걸리는 경로의 기록까지 구해야하는 문제입니다. 경로를 기록하기 위해서 배열 record를 선언하였고, 큐가 진행될때 마다 다음 위치에 이전 위치가 기록됩니다. 수빈이가 동생을 만나면, traceBack() 함수를 통해 현재 수빈의 위치에서 부터 처음 위치까지 역으로 추적하도록 구현했습니다. #include #include #include #in..
-
[백준/BOJ] 13549번 숨바꼭질 3 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:28
www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 문제와 비슷한 BFS 문제 주의할 점은 이동의 순서를 순간이동 -> 뒤로 가기로 맞춰야 한다는 점입니다. #include #include #include #define MAX 200001 using namespace std; int n, k; int visit[MAX]; void BFS() { memset(visit, -1, sizeof(visit)); queue q;..
-
[백준/BOJ] 12851번 숨바꼭질 2 (C++)알고리즘 문제풀이/백준 2020. 11. 29. 13:27
www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 기존의 숨바꼭질 1에서는 visit 배열을 int로 선언하여 큐가 진행되면서 최소 시간을 기록했지만, 여기서는 최소 시간이 똑같이 나오는 경우의 개수도 출력해야하기 때문에 visit 배열을 bool로 선언하고, 큐가 pop을 하고 난 후 방문 처리를 해 중복 방문이 가능하게 만들었습니다. 처음에 동생을 만난 경우와 이후에 동생을 만난 경우를 구분하기 위해 cnt가 0일때 동..