관찰과 질문, 그리고 데이터

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net BFS이면서 heapq 라이브러리를 활용하는 방식에서 실마리를 찾았고, 방문여부를 확인하는 visited배열에 하나의 dime..

https://programmers.co.kr/learn/courses/30/lessons/17687 코딩테스트 연습 - [3차] n진수 게임 | 프로그래머스 N진수 게임 튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다. 숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다. 10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다. 이렇게 게임을 진행할 programmers.co.kr 조건에 맞게 함수식을 만들어 답을 구현하는 문제. 문제 풀이를 ..

https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 | 프로그래머스 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr DP로 해결해야 하는 문제. 대각선 방향으로 오른쪽 / 왼쪽 아래로 값이 이동해야 하므로, value[row][idx] += max(value[row-1][idx-1], value[row-1][idx]) 형태의 점화식을 세울 수 있다. 예외사항은 '가장 왼쪽 값 (idx = 0) 과 가장 오른쪽 값 (idx = row)' 인 경우로, 이 경우는 최댓값을 구할 필요 없이 이전 row의 index 값을 그대로 더하면 된다.

https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net BFS 문제. '고슴도치 S가 먼저 이동하고, 고슴도치가 이미 이동한 공간이라 해도 물이 해당 공간을 잠식하도록' 코드를 구성했다. 고슴도치..

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net BFS를 사용하지만, BFS에서 사용하는 queue를 heap 자료구조로 활용해야 하는 독특한 문제. heap을 사용하는 이유는 '벽을 가장 적게 부수고 이동하는 경우'가 항상 우선순위에 위치한 채 BFS로 순회해야 하기 때문. 이 개념을 생각 못해서 문제를 푸는 데 정말 오래 걸렸다.

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 | 프로그래머스 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> programmers.co.kr 꽤 예전에 풀었던 문제. 그래서 코드가 효율적인 편은 아니다. 현재 단어..

https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 처음에는 이걸 어떻게 풀어야 하나 접근을 못해서 꽤나 고생했는데, ..

https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 | 프로그래머스 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 차량의 진입 / 진출지점이 겹치면, 겹치는 지점의 공통범위로 감시카메라의 범위를 좁힌다. 감시카메라 범위에 포함되지 않을 경우 새 카메라를 설치해야 한다. 코딩테스트 초창기에 접했던 문제라서 푸는 데 정말 오래 걸렸었다.

https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 시뮬레이션 문제. 주어진 조건대로 프로그램을 짜면 충분히 해결할 수 있다. '방향을 바꾸는 경우'를 계산하기 위한 함수를 만들고, 뱀의 좌표를 ..

https://programmers.co.kr/learn/courses/30/lessons/49995 코딩테스트 연습 - 쿠키 구입 | 프로그래머스 과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다. 철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 l번 바구니부터 m번 바구니까지, 둘째 아들에게는 m+1번 바구니부터 r번 바구니까지를 주려합니다. 단, 두 아들이 받을 과자 수는 같아야 합니다(1