gunnew의 잡설

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving 우선 이 문제는 여러 방법으로 풀 수 있는 것 같다. 혹자는 MST로 풀어버리던데... 문제를 풀고 나서 다른 사람 코드를 보면서 이걸 '어케 MST라고 판단했지?' 하는 생각이 들었다. 나는 MST로 푼다는 생각 자체를 하지 못했다. 당연히 DFS로 완전 탐색 돌리는 거라고 생각했는데 생각해보니 참 신박하다. 뭐, 어쨌든 문제를 보니 input이 워낙 작기 때문에 애초에 완전 탐색을 유도한 문제라고 생각했기에 MST라고 생각하지 못한 것에 대한 억지 위로를 하였다. (뭐 어쨌든 MST도 거리 계산할 때 완전 탐색 할듯?) https://www.acmicpc.net/problem/17472 1747..

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 이 문제를 처음 풀기 시작했을 때 한 20분 동안은 멍했다. 분명히 완전 탐색인데 어떻게 '구현'하지? 뭔가 문제가 상당히 난잡해 보였다. 그도 그럴 것이 밑에 제시된 그림만 봐도 현기증 나게 생겼다. 이건 뭐 어쩌라는 거지... 20분은 그렇게 날렸다. 그러다가 실제 시험이라고 생각하니 정신이 들었다. 기존 문제처럼 정갈하게 연결 상태가 주어진 것도 아니고, 친절하게 그림으로 설명을 첨부해 주지도 않았다. 그러면 할..

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving https://www.acmicpc.net/problem/5373 5373번: 큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란 www.acmicpc.net 세상에 이런 무식한 문제가 있었다..

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 www.acmicpc.net 이 포스팅은 적어도 내가..

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 이 문제를 꽤나 빨리 풀고 (대략 2-30분) 정답률을 확인하고 조금 놀랐다. 정답률 23%대를 기록하고 있었는데 이 문제가 요구하는 수준이 그 정도인가 하는 생각이 들었다..

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다. 입력되는 모든 보드 www.acmicpc.net 본 문제를 읽어보면 ..

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 마시멜로 이야기를 아는가??!! 지금 하나를 먹으면 다음 마시멜로는 없지만, 지금 30분 동안 꾹 참으면 마시멜로를 무려 두 개나 먹을 수 있다는 사실! 이 이야기는 내가 생각하기에 완전 탐색을 쉽게 이해하게 하는 예시라고 생각한다. 모든 경우의 수를 열어 놓는 것. 모든 경우의 수를 열어 놓기 위해 지금 눈 앞에 있는 이득을 꾹 참는 것. 그것이 완전 탐색, 어쩌면 Dynamic Programming의 핵심이다. 그래서 이들은..

PS 백준 소스 코드 모음 : https://github.com/kgw4073/Problem-Solving https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 나는 이 문제를 DFS와 BFS..