1. 이진탐색과 순차탐색순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 2. 이진탐색의 시간 복잡도단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 log2N에 비례한다.예를들어 초기 데이터 개수가 32개 일 때, 이상적으로 1단계를 거치면 16개 가량 => 2단계를 거치면 8개 가량 => 3단계를 거치면 4개 가량의 데이터만 남는다.즉, 이진탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 logN을 보장한다.- 이진 탐색: 재귀적 구현def binary_search(array, target, start, end): if start > end: ..

1. 다이나믹 프로그래밍 개념 개념: 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법으로 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.다이나믹 프로그래밍은 동적계획법이라고 부르고 동적 할당은 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법을 의미하지만 다이나믹 프로그래밍에서 다이나믹은 별다른 의미 없이 사용된 단어이다. 구현: 탑다운과 보텀업 조건:1) 최적부분 구조(큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 구조)2) 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결해야한다.) - 예시1) 피보나치 수열점화식이란 인접한 항들 사이의 관계식을 의미하고 다이나믹 프로그래밍으로 ..

1. DFS개념: 깊이 우선 탐색으로 깊은 부분을 우선적으로 탐색하는 알고리즘이다.구현: DFS는 스택 자료구조 혹은 재귀 함수를 이용한다.동작:- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다.방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.- 2번의 과정을 수행할 수 없을 때까지 반복한다. def dfs(graph, v ,visited): visited[v] = True print(v, end=' ') for i in graph[v]: if not visited[i]: dfs(graph, i, visited)graph = [ ..

1. 그래프 탐색 알고리즘탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정코딩테스트에 꼭 나오는 문제대표적으로 DFS, BFS 그래프 탐색 알고리즘을 알기 위해서는 파이썬에서 재귀, 스택과 큐 개념이 필요하다 2. 스택먼저 들어 온 데이터가 나중에 나가는 선입후출의 자료구조입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.stack = []stack.append(5)stack.append(2)stack.append(3)stack.append(7)stack.pop()stack.append(1)stack.append(4)stack.pop()print(stack[::-1])print(stack)5 삽입 = > 2 삽입 => 3 삽입 => 7 삽입 => 7 제거 =>1 삽입 = > 4 삽입 => ..

1. 구현 개념 및 아이디어 개념: 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정구현: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제시뮬레이션: 일련의 명령에 따라서 개체를 차례대로 이동시킨다는 점(실제로 시뮬레이션 해보는 것)완전탐색: 가능한 경우의 수를 모두 검사해보는 탐색방법 예시- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제- 실수 연산을 다루고, 특정 소수점까지 출력- 문자열을 특정한 기준에 따라서 끊어 처리해야하는 문제- 적절한 라이브러리를 찾아서 사용해야하는 문제 2. 예제 2차원 공간 문제에서 많이 쓰이는 행렬예제1) 행렬for i in range(5): for j in range(5): print('(',i,',',j,')', end=' ')..

1. 그리디 개념 및 아이디어 개념: 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법해결법: 최소한의 아이디어를 떠올릴 수 있는 능력평가: 가장 좋아보이는 것만 반복해도 최적의 해를 구할 수 있는지 검토해야된다. 그리디 알고리즘의 문제: 최적의 해를 보장 할 수 없을 때가 많지만 코딩테스트에서는 그리디로 얻은 해가 최적의 해로 설정해놓고 문제를 내기에 그리디 문제라는 것만 알면된다. 2. 예제문제예제 1) 거스름 돈 문제 아이디어: 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면된다. => 그래야 돈이 빨리 0으로 수렴되니까정당성: 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기에 가장 큰 화폐 단위부터 나눠주는게..