세상을 바꾸는 데이터

문제 링크: https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ★문제풀이 Point★ 1. 계속해서 이동하는 벽을 어떻게 추가하고 삭제하는지 고민 필요(set, pop, appendleft) 2. 캐릭터가 이동한 다음, 벽이 이동하는 순서로 진행 3. 너비 우선 탐색(bfs)으로 구현 풀이 과정: 이 문제는 욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보는..

문제 링크: https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 풀이 유형: 구현, 시물레이션 ★문제풀이 Point★ 1. 나무의 정보를 3차원 리스트로 담기 (행, 열, 나이) 2. 문제를 꼼꼼히 읽으면서 사계절별로 구현 3. 사계절 중에 여름 양분 처리 중요 풀이 과정: 이 문제는 K년이 지난 후 상도의 땅에 살아있는 나무의 개수를 구하는 프로그램을 작성하는 전형적인 시물레이션 문제이다. 구현, 시물레이션 문제는 문제를 꼼꼼히 ..

문제 링크: https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색, 플러드 필(Flood fill) ★문제풀이 Point★ 1. 0으로 인접해 있는 위치들을 같은 그룹으로 묶어준다. (플러드 필 = 색칠 알고리즘 이용) 2. 각 그룹별로 0의 개수가 몇 개인지 딕셔너리에 저장한다. 3. 벽으로 된 위치를 상하좌우를 돌며 인접한 그룹들을 구한 뒤, 그룹에 ..

문제 링크: https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 시물레이션 ★문제풀이 Point★ 1. 벽을 부술 수 있는 경우는 단 1번! 2. 2차원 리스트가 아닌 3차원 리스트로 풀어야 한다. 풀이 과정: 이 문제는 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하는 문제이다. 단, 벽을 부술 수 있는 개수가 최대 1개임이 핵심이다. 필자는 다음 포..

문제 링크: https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 ★문제풀이 Point★ 1. 총 돌의 개수는 고정이다. 2. 총 돌의 개수가 3의 배수가 아니라면 어떤 수를 쓰더라도 모든 그룹에 있는 돌의 개수를 같게 만들 수 없다. 풀이 과정: 이 문제는 강호가 모든 그룹에 있는 돌의 개수를 같게 만들려고 할 때 가능하면 1을, 불가능하다면 0을 출력하는 문제이다. 먼저 돌의 총합이 ..

문제 링크: https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 앞서 풀은 이모티콘 문제와 유사하다. 이모티콘 문제는 다음 포스트를 참고하자. https://data-flower.tistory.com/80 [백준 14226번] 이모티콘 - 파이썬 문제 링크: https://www.acmicpc.net/problem/1422..

문제 링크: https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 유형: 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 다이나믹 프로그래밍(DP)로 풀지 않고 딕셔너리를 이용한 bfs로 풀었다. bfs 대부분의 문제는 방문 표시를 가능한 전체 인덱스 수만큼 만들어서 해결하는데, 이 문제는 다르다. 이 문제는 현재 이모티콘의 개수와 클립보드에 있는 이모티콘 개수 2가지를 이용해 bfs로 풀어야 한다. 방문..

문제 링크: https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 유형: 그래프 이론, 그래프 탐색, 너비 우선 탐색 풀이 과정: 이 문제는 숨바꼭질 문제를 응용한 문제로서 난이도가 조금 높아졌다. 기본 숨바꼭질 문제는 다음 링크를 참조하자. https://data-flower.tistory.com/78 [백준 1697번] 숨바꼭질 - 파이썬 문제 링크: https://www.acmicpc.net/problem..