선택은 나의 것

문제 BOJ 17090 : https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문� www.acmicpc.net 접근 DFS를 이용하여 문제를 풀었다. 이때 주의할 점은 DFS를 통해 모든 경우의 수를 전부 돌아본다면 미로의 최대 크기가 500x500이므로 시간 초과가 날 것이다. 그렇다면 어떻게 해야 효율적으로 탐색할 수 있을까? 어떤 경로에 대해 탐색이 끝났다면 우리는 그 경로에 대한 답-더이상 나아갈 길이 없거나 미로를 탈출했거나-을 알고 있다. 이때 이 결..

문제 BOJ 16954 : https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 접근 이 게임은 시간이 1초 흐를 때마다 벽이 한 칸씩 아래로 내려온다. 캐릭터가 먼저 인접한 빈칸으로 이동한 후 벽이 내려온다. 이때 캐릭터는 이동하지 않고 현재 위치에 서 있을 수도 있다. 이 문제의 관건은 시간에 따라 변화하는 미로이다. 따라서 미로를 저장해주는 배열(block)을 3차원으로 선언해 시간의 흐름에 따라 바뀌는 미로의 모양을 저장해 줄 수 ..

문제 Programmers 2018 KAKAO BLIND RECRUITMENT : [3차] 파일명 정렬 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램�� programmers.co.kr 접근 문자열은 조건에 맞게 HEAD, NUMBER, TAIL 부분으로 나눈다. 이때 중간에 숫자 영역인 NUMBER을 기준으로 split으로 잘라준다. python의 문자열 처리에 대해서 궁금한 사람들은 파이썬 프로그래밍 입문서를 참고하길 바란다. 정리가 매우 잘 되어있어 많은 도움을 받았다. 다음으로 대소문자 구분 없이 HEAD 문자에 따라 정..

문제 Programmers 2018 KAKAO BLIND RECRUITMENT : [1차] 셔틀버스 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 접근 어려운 문제는 아니지만, 문자열 처리가 까다로우므로 python을 이용해 풀었다. 지난 [SWEA] 7732 시간 개념 문제에서도 말했듯이 시간과 관련된 문제는 비교하기 편하게 가장 작은 단위-이 문제에서는 분(minute)-로 환산해 주는 것이 편하다. 분(minute)으로 환산한 시간 정보를 timetab..

문제 BOJ 1766 : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 접근 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 위상 정렬(Topological Sort)을 사용한다. 따라서 이 문제는 위상 정렬을 이용해 문제를 풀었다. 위상 정렬(Topological Sort) 알고리즘에 관해 HeeJeong Kwon 님과 안경잡이개발자 님의 블로그를 참고했다. 이 문제에는 한 가지 조건이 더 있는데, 가능한 ..

문제 BOJ 16939 : https://www.acmicpc.net/problem/16939 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 접근 큐브는 칸마다 색이 칠해져 있으며 큐브를 방향에 상관없이 한 번 돌려서 큐브를 완성할 수 있는지 구하는 문제이다. 언뜻 보면 복잡해 보이지만 실은 단 한 번만 돌리는 경우만 생각해주면 되기 때문에 간단하다. 육면체 큐브가 돌아가는 모습을 상상해보자. 큐브는 아래 이미지의 표시된 위치끼리 돌아갈 것이다. 우리는 이 큐브를 단 한 번 돌릴 것이다. 그렇다면 어느 방향으로..