from palette import colorful_colors

참고서적: 이것이 코딩테스트다 with 파이썬 graph를 이용해 최단거리를 이용하는 방법이다. 다익스트라는 특정 노드에서 다른 노드로 가는 최단거리를 구하는 방법이고, 시간복잡도는 짜는 방법에 따라 O(V^2), O(ElongV)다. (V는 간선의 개수, E는 간선의 개수) 간선은 모두 양수여야 한다. 플로이드 워셜은 모든 노드에서 모든 노드로 가는 최단거리를 구하는 방법이고, DP를 이용해 구한다. 시간복잡도는 O(V^3)이다. 음수 가중치 간선이 있어도 수행할 수 있다. 다익스트라 알고리즘 먼저 거리를 무한으로 초기화하고, 출발노드부터 시작해 방문하지 않은 노드를 선택해 인접한 다른 노드로 가는 비용을 체크한다. 이때 해당 노드를 거쳐 다른 노드로 가는 거리가 다른 노드의 기존 거리보다 작다면 갱신..

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈 메모리 공간을 더 사용하여 연산 속도를 증가시킬 수 있는 방법. ex) 점화식을 이용해 풀기 2가지 방법(top down, bottom up)이 있다. 예시: 피보나치 함수 # 피보나치 함수를 재귀로 구현할때 def pibo(x): if x == 1 or x == 2: return 1 else: return pibo(x-1) + pibo(x-2) print(pibo(4)) 이렇게 단순 재귀로 작성하면 n이 커질 수록 시간복잡도가 기하급수적으로 늘어난다. O(2^N) 따라서 dp를 이용한다. dp를 사용할 수 있는 경우: 1. 큰 문제를 작은 문제로 나눌 수 있다 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하..

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈 up down 게임처럼 탐색범위를 반으로 쪼개면서 탐색하는 알고리즘. 따라서 시간복잡도는 O(logN)이다. 배열 내부 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 처리해야 할 데이터 개수나 값이 1000만이상처럼 무척 높으면 이진탐색과 같이 O(logN)의 속도를 내는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다. # 이진 탐색 구현 def binary_search(array, target, start, end): if start > end: return None # 아무런 값을 반환하지 않고 종료 mid = (start + end) // 2 # 찾은경우 중간점 인덱스 반환 if array[mid] == ta..

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈 버블정렬, 선택정렬, 삽입정렬, 퀵정렬, 계수정렬, 파이썬 기본 정렬 함수(sort, sorted) 코드 첨부 0. 정렬 문제풀이 방법 - 정렬 라이브러리로 풀 수 있는 문제(sort, sorted): 정렬 라이브러리 사용방법 숙지하기 - 정렬 알고리즘의 원리에 대해 물어보는 문제: 선택 정렬, 삽입 정렬, 퀵 정렬 등의 원리를 알고 있어야함 - 더 빠른 정렬이 필요한 문제: 퀵 정렬 기반으로도 해결이 불가능할때, 계수 정렬 등의 더 빠른 알고리즘을 이용하거나 구조적으로 개선하기 예시: 문제에서 리스트의 최대 원소가 100000처럼 크게 주어졌을땐 O(NlogN)인 정렬 라이브러리나 퀵 정렬을 사용한다. 1. Bubble Sort..

참고서적: 이것이 취업을 위한 코딩테스트다 with python - 나동빈 1. 그래프 표현 방법 - 인접 행렬(Adjacency Matrix): 2차원 배열로 그래프 관계 표현 - 인접 리스트(Adjacency List): 리스트로 그래프 관계 표현 2. DFS 구현 # DFS 함수 정의하기 def dfs(graph, v, visited): # 1. 현재 노드 방문 처리하기. visited[v] = True print("visited node:",v) # 2. 현재 노드와 연결된 다른 노드 재귀적으로 방문하기. for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 확인용 코드 (이 밑의 코드는 없어도 무방) # 3. 모두 방문했다면 해당 dfs..

1. 입출력 한 줄에 여러개 입력 받기: map 함수와 input의 split을 이용하고, list로 map을 묶어준다. # 예시: 1 2 4 3 5 를 list로 입력받고 정렬하고 싶을때: number = list(map(int, input().split())) number.sort() 여러줄에 여러개 입력받기 (List Comprehension 활용): comprehension과 list로 map을 묶어준다. # 예시: 라인을 받을 횟수 n을 입력받고 라인마다 push 1 ,.... 이런식으로 여러줄에 여러개가 있을때: n = int(input()) command = [list(map(str, input().split())) for _ in range(n)] for c in command: # c[0..