코딩테스트

다이나믹 프로그래밍의 조건 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 할 때 메모이제이션 top-down, 하향식 한 번 계산한 결과를

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.n번만큼 가장 작은 수를 찾아 맨앞으로 보내기 때문에, 전체 연산 횟수는 N + (N-1) + (N-2) + ... + 2따라서 O(N^2)이다.처리되지 않은 데이터를

DFS 스택(또는 재귀함수) 이용 모든 노드를 방문하고자 하는 경우 선택 DFS가 너비 BFS보다 좀 더 간단함 검색 속도 자체는 BFS에 비해서 느림 [동작 과정] 탐색 시작 노드를 스택에 삽입하고 방문 처리 스택 최상단 노드에 방문하지 않은 인접한 노드가 하나라

이진탐색 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용해 탐색 범위를 설정 시간복잡도 : O(logN) 이진탐색 반복문 파라메트릭 서치 파라메트릭 서치: 최적화 문제를 결정 문제(예/아니오)로 바꿔어 해결

문제 : https://www.acmicpc.net/problem/14502 접근 설치한 벽의 개수가 3개가 되는 모든 조합에 대해,바이러스 확산을 진행하고 안전 영역의 크기를 계산해야 한다. DFS vs BFS DFS로 풀 경우 BFS로 풀 경우 얕은 복사 v