목록전체 글 (104)
개발자 김수진
[문제] www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net [풀이] 하반기 어느 기업 코테에서 굉장히 이 문제와 유사한 문제가 나왔었다. 현재 위치를 기준으로 왼쪽과 오른쪽으로 나누고 그 중에서 가장 큰 값을 left, right 변수에 저장한다. left와 right 중에서 작은 값을 고르고 여기서 현재 블록의 높이를 빼주면 해당 블록의 고이는 빗물의 양이 된다. 위와 같은 방식으로 두번째 블록부터 마지막 블록 전까지 반복해주면 된다. [코..
[문제] www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [풀이] DP 배열을 2차원을 선언하여 풀었다. DP[i][j]는 i자리 수에서 마지막 숫자가 J인 경우의 수를 나타낸다. 예를 들어 DP[2][2]는 'X2'인 경우로 12,32가 있으므로 2이다. 따라서 계단 수를 구하는 것이므로 점화식을 아래와 같이 세울 수 있다. DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]; 단 , j가 0이거나 9인 경우 따로 예외처리 해줘야된다. [코드] #include #define MAX 101 #define MOD 1000000000 using namespa..
[문제] www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net [풀이] 입력으로 사각형 판의 가로,세로 길이가 주어지고 사각형의 상태가 주어진다. 0은 비어있는 부분이고 1은 치즈가 존재하는 곳이다. 이 때 , 치즈가 공기와 접촉된 칸은 1시간 뒤에 녹아서 없어진다. 또한 치즈에 구멍이 있을 수 있는데 구멍에는 공기가 존재하지 않는다. 처음에 치즈에서 구멍을 먼저 찾아야겠다고 생각했다. 구멍을 찾는 방법으로는 사각형에서 치즈 밖의 부분은 0으로 모두 연결되어 있다. 따라서 BFS를 ..
[문제] www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net [풀이] 입력이 주어지면 섬의 개수를 구해서 출력하면 된다. 상,하,좌,우,대각선 방향으로 연결된 것은 하나의 섬으로 본다. 전형적인 BFS 문제로 섬의 개수로 방문 처리도 해주었다. 따라서 입력이 0과 1이므로 섬의 개수를 저장하는 cnt 변수를 2부터 시작하고 출력은 cnt-1로 해주었다. BFS 경우 방문 처리를 꼭 해줘야된다. 방문처리를 하지 않으면 계속 queue에 담기게 되어 메모리,시..
[문제] www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [풀이] 시식할 수 있는 포도주의 최대 양을 구하는 문제. 단, 연속해서 3잔을 마실 수 없다. 점화식을 세워서 DP를 통해 해결했다. DP[x]는 x잔 마시는데 마실 수 있는 최대 포도주의 양을 저장하는 배열이다. 연속해서 3잔을 마실 수 없으므로 아래와 같이 점화시을 유도할 수 있다. DP[x]= max(DP[x-3]+arr[x-1]+arr[x] , DP[x-2]+arr[x]); 하지만 예외가 있어서..
[문제] www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net [풀이] 고슴도치가 비버의 굴로 이동해야 하는데 물이 있거나 돌이 있는 곳으로는 움직일 수 없다. 물은 매 분마다 인접한 곳으로 퍼진다. 단 , 비버가 존재하는 곳이나 돌이 존재하는 곳으로는 퍼질 수 없다. 이 때 최단 거리를 구하는 문제. 고슴도치의 이동경로를 저장하는 visited 배열과 물, 돌의 정보를 저장하는 map을 선언했다. BFS 함수의 while 문에서 물이 먼저 퍼지고 그 다음에 고슴도치가 움직이..
[문제] www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net [풀이] 미로의 정보가 입력으로 주어지고 시작점 (1,1)에서 도착점(N,M)까지의 최단거리를 구하는 문제이다. 1은 이동할 수 있는 칸을 의미하고, 0은 이동할 수 없는 칸을 의미한다. BFS를 사용해 풀었다. 다음 위치의 값이 1인 경우에만 좌표를 queue에 저장하였고, 이미 방문했던 곳이라면 queue에 담지 않았다. 실수했던 부분이 BFS는 동시에 움직이므로 최단거리를 구하는 경우 재방문 하지 않아도 된다. [코드] 시간 :..
[문제] www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net [풀이] 1번 컴퓨터가 바이러스에 걸렸고 1번 컴퓨터와 연결된 컴퓨터는 모두 바이러스에 걸리게 된다. 이 때 1번은 제외하고 바이러스에 걸린 컴퓨터의 갯수를 출력하면 된다. 문제는 DFS를 사용해서 풀 수 있었다. map이라는 2차원 배열을 선언하여 연결 정보를 저장했다. 그 다음 DFS를 1번부터 시작하여 start와 연결된 모든 컴퓨터에 대해 DFS 함수를 호출한다. visited를 통해서 이미 방문했는..