이전에 풀었던 문제들을 다시 풀면서 무엇이 어려웠고, 어느 부분에서 막혔는지 어떻게 풀었는지 적어보려고 한다. 문제 [D2] 16504_Gravity 가로 N, 세로 100 크기의 방에 상자가 쌓여있다. 90도 회전 했을 때 낙차가 제일 큰 값 출력해라. 입력 및 출력 입력 9 7 4 2 0 0 6 0 7 0 출력 #1 7 접근 자신 보다 작은 수를 세서 cnt += 1 그 중 최댓값(maxV)과 비교해서 maxV 갱신 풀이 코드 T = int(input()) for tc in range(1, T + 1): N = int(input()) box = list(map(int, input().split())) maxV = 0 for i in range(N): cnt = 0 for j in range(i + 1..
Algorithm
분할 정복(divide and conquer) 알고리즘 개념 큰 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 기법이다. 재귀적으로 구현한다. 대표적인 예시로는 병합 정렬(Merge Sort), 이진 검색(Binary Search), 거듭 제곱(Exponentiation), 퀵 정렬(Quick Sort)이 있다. 이 외로는 행렬 곱셈(Matrix Multiplication), 최대 부분 합(Maximum Subarray)이 있다. 설계 1) Divide(분할): 주어진 문제를 분할한다. 단, 문제를 적절한 크기로 분할하는 것이 중요하다. (최소 2개 이상) 2) Conquer(정복): 각 하위 문제들을 재귀적으로 해결한다. 나눌 수 없으면 탈출 조건을 설정하고, 문제를 해결한다. 3) Combine(..
- 탐색 알고리즘 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. DFS, BFS는 그래프 탐색 알고리즘에 속한다. - 그래프 노드(Node)와 간선(Edge)으로 이루어진 자료구조의 일종 간선으로 연결되어 있는 노드들을 인접하다(adjacent)라고 표현된다. 구현하는 방식 → 인접 행렬, 인접 리스트 인접 리스트 graph = [ [1, 2, 3], [0, 3], [0, 3], [0, 1, 2] ] 각각의 인덱스에 해당하는 노드에 연결된 노드들을 리스트 형태로 저장하는 방식 연결 리스트를 활용하여 표현하는 방식 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우 인접 행렬 graph = [[0, 1, 1, 1], [1, 0, 0, 1], [1, 0, 0, 1], [1, 1, ..
