💡 CodingTest/이것이코딩테스트다

[Python] 이것이 코딩테스트다 10장 그래프 이론

그래프 이론의 핵심 지금까지 배운 내용 시간 제한 참고 파이썬 => 1초 20000000번 연산 데이터 20,000,000 => O(N) 데이터 1,000,000 => O(NlogN) 데이터 4~5,000 => O(N^2) 데이터 100~200 => O(N^3) 그래프의 구현 방법 노드의 개수가 V, 간선의 개수가 E라고 하면 인접 행렬 : 2차원 배열을 사용하는 방식 인접 행렬의 경우 O(v^2) 만큼의 메모리 공간 필요 (메모리 측면) 인접 행렬의 경우는 특정 노드의 간선의 비용을 알기 위해선 O(1)의 비용이 듦 (속도 측면) 인접 리스트 : 리스트를 사용하는 방식 인접 리스트의 경우 O(E) 만큼의 메모리 공간 필요 (메모리 측면) 인접 리스트의 경우는 특정 노드의 간선의 비용을 알기 위해선 O(..

[Python] 이것이 코딩테스트다 9장 최단 경로

최단 경로의 핵심 최단 경로 알고리즘에는 다양한 종류가 있음. 우선 , 한 지점에서 특정 지점으로 까지의 최단 경로를 구해야하는 경우 모든 지점에서 모든 지점까지의 최단 경로를 구해야 하는 경우 경우를 생각해본다. 또, 최단 경로의 합을 구하는 경우 최단 경로에서 거쳐온 노드들을 구하는 경우 를 캐치 한다. 🔑 앞서 공부한 그리디, 다이나믹은 최단경로 알고리즘에서 그래도 적용 된다. 다익스트라 알고리즘: 기준 노드에서 각 노드에 대한 현재까지의 최단 거리 정보를 항상 1차원 리스트에 저장하여 갱신한다는 특징이 있다. 방법 1. 구현하기 쉽지만 느리게 동작하는 다익스트라 O(n^2) 방법 2. 구현하기 조금 어렵지만 빠르게 동작하는 다익스트라 (우선순위 힙 이용) O(elogv) 플로이드 알고리즘 : 2차..

[Python] 이것이 코딩테스트다 8장 다이나믹 프로그래밍

다이나믹 프로그래밍의 핵심 🔑 수열의 점화식을 구하는 것이 핵심! 중복되는 연산을 줄이자. 연산 속도와 메모리공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성 현재의 항들로 다음 항을 구할 수 있는 경우 다이나믹 프로그래밍을 쓴다. 대표적 예시 >> 피보나치 수열 재귀 함수(탑다운 방식) 구현하긴 간편하지만 숫자가 커지면 기하급수적으로 연산횟수가 늘어난다. f(100)을 구하기 위해서는 약 1,000,000,000,000,000,000,000,000,000,000번 연산을 해야한다. 시간으로 따지면 수백억년이 넘어가는 시간이 걸림. 다이나믹 프로그래밍 (보텀업 방식) 하지만 다이나믹으로 풀 경우, 같은 문제라면 한번 씩만 풀어 저장해 놓기 때문에 효율적으로 해결하게 된다. O(N)의 성질을 보임..

[Python] 이것이 코딩테스트다 7장 이진탐색

이진탐색의 핵심 순차 탐색 : 앞에서부터 차례차례 탐색 이진 탐색 : 반으로 쪼개면서 중간점을 기준으로 탐색 O(logn) 이진 탐색은 우선 정렬이 되어있다는 가정하에 할 수 있는 탐색이다 따라서, 정렬이 안되어 있다면 정렬을 하고 이진탐색을 해야하므로 O(logn)의 성능이 안나올 수 있다. 이진 탐색 트리 : 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 이진 탐색 트리를 구현하면은 부모노드 부터 검사를 해서 왼쪽으로 갈지 오른쪽으로 갈지 정할 수 있기 때문에 이진 탐색을 쉽게 적용 가능하다 이진 탐색의 핵심은 문제를 보고 이진탐색이냐 아니냐를 구별해 내는 능력을 키우는 것 보통 몇십억~ 기하급수적인 숫자가 나오면 아무리 순차탐색의 O(n)성능이라도 시간초과가 나기 때문에 이진 탐색을 떠올려야한..

[Python] 이것이 코딩테스트다 6장 정렬

정렬의 핵심 선택 삽입 퀵 계수 합병 버블 평균시간복잡도 O(n^2) O(n^2) O(nlogn) O(N+K) O(nlogn) O(n^2) 선택 정렬 선택 정렬은 코드가 구현하기 쉬우나, 데이터의 갯수가 늘어나면 늘어날 수록 현저히 느리게 작동하는 것을 확인 할 수있다 데이터가 많아지면 비효율적이다 삽입 정렬 삽입 정렬은 선택 정렬과 같이 O(n^2)이지만 실제 실행시간 측면에서는 조금 더 효율적이라고 알려져 있다 그리고 거의 모든 데이터가 정렬이 되어있다면 삽입 정렬은 가장 효율성이 극대화된다 최선의 경우 O(N)의 시간까지 극대화 될 수 있다 즉, 거의 정렬이 되어있다면 속도 : 삽입정렬 > 퀵정렬 퀵 정렬 대부분 라이브러리 하면 사용되는 정렬. 기본적으로 분할을 이용하기 때문에 기하급수적으로 줄어들..

[Python] 이것이 코딩테스트다 5장 BFS/DFS

BFS 와 DFS의 핵심 완전탐색이라면 BFS, DFS에서 사실상 시간은 비슷하지만 일반적으로는 BFS가 더 성능이 좋고 보면된다. 왜냐하면 DFS는 재귀함수를 이용하며 BFS는 반복문을 기반으로 하기 때문 재귀와 반복의 시간차이는 피보나치 수열로 확인해보면 알 수 있다. 하지만, 완전 탐색이 아니라면 Backtracking같은 곳에서는 이야기가 다르다. 백트래킹에서는 DFS가 더 성능이 좋은경우가 많다. (예를들어 branch and bound) Best first search (우선순위 큐 이용) > Depth first search (스택 이용) > Breath first search (큐 이용) 순이다. 이 밖에 더 좋은 알고리즘이 있을 수 있다. 어찌됐든 완전탐색을 해야하는 경우라면 BFS를 선..

[Python] 이것이 코딩테스트다 4장 구현

구현 파트의 핵심 구현은 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 그리고 공간복잡도와 시간복잡도를 얼추 따져보는 것이 완점탐색을 할 것인지를 결정할 수 있다. 공간복잡도의 관한 얘기 int 는 4바이트 이며 데이터 갯수가 1000개라 하면 약 4KB 메모리를 쓰게 된다. 그렇다면 128MB의 메모리 제한이 있는 곳에선 32000000개의 데이터까지 쓸 수 있다는 말이 된다. 시간복잡도의 관한 얘기 일반적으로 파이썬은 1초에 2000만번 (20000000)번의 연산을 수행하는 속도이다. 시간제한이 1초라는 것은 20000000번의 연산이하로 수행할 수 있다면 된다는 것이다. 그렇다면 데이터 제한을 보고 어느정도 시간복잡도가 허용되는 지 유추할 수 있다. 예를들어, 데이터가 2000만개까지 수행..

[Python] 이것이 코딩테스트다 3장 Greedy

거스름돈 🔑 Key Point 가장 큰 화폐 단위부터 거슬러 주며 그 나머지를 이용하는 것 큰 수의 법칙 🎨 처음 짠 코드 직관적으로 짠다면 이 문제는 for 문이 1~2개 필요하다. 하지만 📌 반복문을 사용하지 않고, 구현이 가능한 아이디어 가 있다. 🎨 반복문을 사용하지 않는 BEST 코드 아이디어는 이렇다. 이 문제에서 가장 큰 수는 6이며, 그 다음 큰 값은 5이다. 이 두가지만 번갈아 쓴다면 답을 구할 수 있다. 🔑 Key Point 간과했던 부분은 📌똑같이 반복되는 구간이 발생한다는 점 이다. 6 6 6 5 6 6 6 5 ... M의 수에 따라 만족하는 만큼 위의 과정이 반복된다. 나누기를 잘 이용하면 몇번 반복되는지 알 수 있기 때문에 , 반복문이 필요 없다. #가장 큰 수가 더해지는 횟수 ..