구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 코딩테스트에 자주 출제됨, 완전 탐색과 시뮬레이션 유형을 같이 공부함 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 방법을 말하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야하는 문제 유형을 말한다. 구현 시 고려해야 할 메모리 제약 사항 파이썬에서는 리스트 크기를 고려해야 한다. 대체로 코딩 테스트에서는 128~51MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되곤 한다. int 자료형 데이터의 개수에 따른 메모리 사용량 데이터의 개수 (리스트의 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 리스트 ..

Greedy 현재 상황에서 지금 당장 좋은 것만 고르는 방법 대부분의 문제가 그리디 알고리즘을 이용했을 때 최적의 해를 찾을 수 없을 가능성이 다분하다. 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 잇따는 보장이 있을 때 매우 효과적이고 직관적이다. 어떤 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민해본다. 만약 오랜 시간을 고민해도 그리디 알고리즘으로 해결 방법을 찾을 수 없다면 DP나 그래프 알고리즘 등 다른 알고리즘을 고려해본다. 예제 3-1 거스름돈 문제 거스름돈으로 사용할 500원,100원,50원,10원짜리 동전이 무한히 존재한다고 가정함 손님에게 거슬러 줘야할 돈이 N원일 때 거슬..

DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다.*탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말함 깊이 우선 탐색 DFS(DEPTH - FIRST SEARCH): 탐색 노드(루트 노드 or 다른 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 DFS 구현 방법- 재귀함수- 스택  (되돌아가기 위해 스택 필요)  1) 재귀함수-Linkedlist 이용package dd;import java.util.*;public class Main { public static void dfs_list(int v,LinkedList[] adjList,boolean[] visited) { visited[v]=true; System.out.print(v+" "); ..