코딩테스트 준비 (32) 썸네일형 리스트형 [백준 9376][C++] 탈옥 문제 https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 풀이 과정 [참고 링크 1] [참고 링크 2] [0-1 BFS 알고리즘 링크] 필자는 링크 1의 코드를 기반으로 풀이를 작성했다. 해당 문제는 0-1 BFS 알고리즘을 통해 다익스트라 알고리즘보다 효율적으로 구현할 수 있다. 주변의 위치에 존재하는 BFS탐색 시, 문이거나 문이 아닌 경우로 나뉘기 때문이다. 이 문제의 핵심은 아래 3가지 경우를 모두 고려해야 한다는 점이다. 1) 1번 죄수가 탈출하며 문.. [백준 11049][C++] 행렬 곱셈 순서 문제 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 과정 [참고 링크] 해당 문제는 11066 파일 합치기 문제와 매우 유사하다. 파일 합치기 문제를 풀이했을 때 사용했던 알고리즘과 동일한 구조로 동작하도록 구현하기 위해 위의 링크를 참고했다. 해당 문제와 동일한 블로그의 포스팅이다. 설명이 매우 자세하고 충분히 이해하고 DP를 적용한 코드를 사용할 수 있었다. 해당 포스팅을 보고 공부 중 어려웠던 부분을 다른 사람들이 더 .. [백준 1956][C++] 운동 문제 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 풀이 과정 플로이드-워셜(floyd-warshall) 알고리즘을 이용한다. 해당 알고리즘은 2차원 배열을 이용하여 두 노드를 잇는 최단거리를 구하는 알고리즘이다. 이때 노드의 최단 거리를 구할 때 자기 자신의 노드는 0으로 설정하는데, 이 부분만 수정한다면 위의 문제를 해결할 수 있다. 아래의 그림은 플로이드 워셜 알고리즘이 적용되기 전, 후의 상태를 나타낸.. [백준 2933][C++] 미네랄 문제 https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 풀이 과정 1. 문제 조건에 맞게 입력을 받는다. 2. 순서대로 발사하여 미네랄을 부순다. 3. 부순 미네랄을 기준으로 주변을 탐색하여 미네랄 군집(cluster)을 파악하고, 중력에 의한 이동을 수행한다. 4. 최종 형태를 출력한다. 세부 풀이 (1) 초기 형태와 이후 던질 막대의 높이에 대한 정보도 한 번에 입력받아 order 배열에 넣어 저장한 뒤 사용했다. (2) shoot 함수 order 배열에 .. [백준 3197][C++] 백조의 호수 문제 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 풀이 과정 해당 문제를 정말 많이 고민하면서 풀었지만 계속 메모리 초과가 발생했다. 메모리 초과에 의해서 문제를 풀지 못했던 적은 처음이라 이런저런 경우를 많이 테스트해보며 과정을 적으려 한다. 1) int -> char 변경 (실패) 처음엔 전체 호수의 상태를 저장하기 위해 int map [1501][1501]를 이용했었는데, 여기서 메모리가 초과되었나 하고 고.. [백준 11066][C++] 파일 합치기 문제 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net [풀이 참고 링크 1] [풀이 참고 링크 2] 풀이 과정 처음에는 가장 작은 순서대로 정렬해서 가장 작은 것부터 결합하면 되는 것 아닌가라는 착각을 했었지만, 좌 우 정보가 사라지기 때문에 그렇게 처리하면 오답이 나온다. 그렇다면 각각에서 좌 우 탐색을 하며 DP를 진행해야 하는 것인가 고민하였다. 해당 문제 시간 안에 풀지 못했다. DP로 구현해야겠다는 생각이 들었지만, 구현에서 .. [백준 2749][C++] 피보나치 수 3 문제 https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 과정 [피사노 주기 문제] [행렬 풀이 코드 1] [행렬 풀이 코드 2] [피보나치의 행렬 멱법] 해당 문제를 직접 풀지 못하고 다른 사람들의 풀이를 찾아보게 되었다. 풀이는 크게 두 가지였다. 하나는 피사노 주기를 이용하는 방법과 다른 하나는 행렬을 이용하는 방법이었다. 필자는 위의 링크들을 참고하여 행렬을 이용한 풀이를 선택했다. 피사노 주기에 대한 풀이가 훨씬 간단했지만, 해당 조건보다 행렬을 이용해 문제를 풀이하는 방법이 더 보편적이고 다른 문제에도 적용할 수.. [백준 10830][C++] 행렬 제곱 문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 과정 분할 정복 알고리즘을 적용한다. 행렬 곱 함수를 작성한 뒤, 행렬의 제곱을 기록하며 결과를 이용하도록 구현한다. 예를 들어 A^9를 구한다고 가정했을 때, A^9 = A * (A^4) * (A^4) 형태로 곱이 이루어지며, O(logN)의 시간 복잡도를 가진다. 정답 배열을 초기화할 때는 곱을 해도 원래 형태가 나오도록 단위행렬 형태로 초기화해야 한다. 소스 코드 #include #include.. 이전 1 2 3 4 다음
