쏭의 개발 블로그

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 이 문제는 상반기에 쳤던 기업 코테 문제를 비슷했다. 그 때는 이 문제를 못 풀었는데 빗물 문제를 일찍 풀었다면 좋았을 듯 문제 풀이 이 문제의 알고리즘을 생각하는데 꽤 오랜시간이 걸렸다. 막상 보니까 생각보다 간단했던 것 같다. 위 그림을 보면 특정 위치의 물의 높이는 해당 위치를 기준으로 오른쪽에서 가장 높은 블록의 높이와 왼쪽에서 가장 높은 블록의 높이 중 최소값이다. 이 ..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 이 문제도 벽 부수고 이동하기 문제만큼이나 오랜 시간이 걸린 문제다. 문제 문제를 요약하면 다음과 같다 n*n 크기의 공간에 물고기 m마리, 아기 상어 1마리가 있다 (아기상어와 물고기는 크기를 가짐) 아기상어는 1초에 상하좌우 중 하나 1칸을 이동하고 물고기를 먹으면 그 칸은 빈칸이 됨 아기상어의 초기 크기는 2 아기상어 크기 > 물고기 크기 : 먹을 수 있고 지나갈 수 있음 아기상어 크..

https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 문제 오목 문제를 요약하면 다음과 같다. 가로, 세로 19줄씩 있는 바둑판 같은 색의 바둑알이 연속으로 5알이 놓이면 이김 - 가로, 세로, 대각선 6알 이상 연속적으로 놓이면 이긴 것이 아님 검은 바둑알 1, 흰 바둑알 2, 알이 놓이지 않는 자리는 0 바둑판 상태가 주어졌을 때, 검은색과 흰색 중 누가 이겼는지 or 비겼는지 판단하는 프로그램 풀이 먼저 모든 2차원 바둑알의 위치를 위부터 아래..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 정말 오래 삽질한 문제다. 진짜 진짜 너무 어려워서 저거 푼다고 며칠동안 끙끙댔다. 한 일주일동안 저거 때문에 다른 문제를 못 풀었던 기억.. 이렇게 사진으로 보면 안그런거같지만 로컬에서 계속 돌려서 그렇지 진짜 한 5일은 붙잡고 있었음. 겨우 힌트보고 해결했고 알고리즘 스터디하면서 친구들한테 풀이 설명해주는거 조차 너무 어려웠음 문제 위 문제를 간단하게 정리하..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 문제를 요약하자면 아래와 같다. 여행에 필요하다고 생각하는 n개의물건 각 물건의 무게 w, 가치 v 준서는 최대 k만큼의 무게를 넣을 수 있는 배낭을 들고다님 배낭에 넣을 수 있는 물건들의 가치합은 최대가 되어야 함 풀이 평범한 배낭은 배낭(Knapsack) 문제이다. 배낭 문제는 짐을 쪼갤 수 있는 경우와 짐을 쪼갤 수 없는..

평소 항상 알고리즘 문제를 풀고 깃헙에 올리거나 공유 노션을 통해 친구들과 스터디를 진행했었다. 최근 하반기 채용공고가 많이 올라오면서 한동안 알고리즘 문제를 잘 못 풀었다. 한동안 잊고 있었던 알고리즘 풀이를 다시 환기도 시킬 겸, 기록도 할 겸 문제 풀면서 어려웠거나 까다로웠던 문제 풀이들을 기록해보려고 한다. 대충 어떤 문제를 적을지 생각도 해놓았다. 아마 여기 있는 내용 위주로 할 듯..? 다른 것도 할일이 많아서 저걸 다 적을 수 있을 진 모르겠지만 차근차근 해봐야지!!

[1] 백트래킹이란 한정 조건을 가진 문제를 푸는 전략 모든 경우의 수를 시도하여 문제의 정답을 찾아감 한정 조건에서의 모든 경우의 수를 시도 ⇒ 상당한 경우의 수들이 배제되므로 다중 for문보다 빠름 (1) 원리 각 단계에서 해결책 후보군 중 하나를 선택하고 이 선택이 조건을 만족하는지 검사 조건을 만족하지 않으면 이전 단계로 돌아가 다른 후보군 선택 1,2 과정을 반복하면서 최종적으로 해결책을 찾아가는 것이 백트래킹의 기본적인 원리 (2) 구현 한정 조건을 걸어 완전탐색에서 유망하지 않은 시도를 걸러내는 것 DFS, BFS를 사용하여 구현 모든 경우에서 한정 조건을 만족하는 경우를 탐색 한정 조건에 부합하지 않다면 이전 수행으로 돌아와야하므로 DFS의 구현이 편함 코드의 형태 def 재귀함수(n): ..

[1] 플로이드 워셜 알고리즘 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 가는 노드를 찾는 과정이 필요 없음 2차원 테이블에 최단 거리 정보를 저장 다이나믹 프로그래밍 유형에 속함 동작 과정 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인 : a에서 b로 가는 최단 거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사 점화식 상세 동작 과정 [초기상태] 그래프를 준비하고 최단 거리 테이블을 초기화 현재 노드와 인접한 노드를 확인하여 테이블을 갱신하도록 함 2차원 테이블 : “노드 → 노드” 를 기록 [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 테이블 갱신 k = ..