파이썬 코딩테스트 꿀팁 모음

예전에 노션에 기록했던거 가져옴

깨지는건 다음에 고칠 예정....

노션으로 보기(이게 나음)

자료형

실수
- 수 자료형의 연산
  - / : 결과가 실수형 예) 7/3 = 2.333333…
  - % : 나머지 예)7%3 = 1
  - // : 몫 예)7//3 = 2
  - ** : 거듭제곱 예)5**3 = 125
- 반올림 함수 round()
  - round(**실수형데이터**, **반올림하고싶은 위치 -1**)
  - 123.456을 소수점 셋째 자리에서 반올림하려면 round(123.456 , 2)라고쓴다. 결과는 123.46
  - 반올림 위치를 지정안하면 디폴트로 소수점 첫째자리에서 반올림한다.
리스트
- 리스트는 list[-1]처럼 음수 인덱스로 접근 가능
- 슬라이싱: list[ **시작인덱스** : **종료인덱스-1** ]
  - 두 번째 원소부터 네 번째 원소까지: print(a[1 : 4]) << 인덱스는 0부터시작
- 리스트 컴프리헨션 (반복문으로 리스트 생성)
  - 대괄호 안에 반복분을 넣어서 리스트를 초기화 가능
  - 0부터 19까지의 수 중에서 흘수만 포함하는 리스트
  - array = [i for i in range(20) if i%2 == 1]
  - 2차원 리스트 초기화 시 좋다. (n_m 크기의 2차원배열)
    `array = [ [0]_4 for in range(3)]결과 :[[0,0,0,0], [0,0,0,0], [0,0,0,0]]`
  - 특정한 크기의 2차원리스트를 초기화 할 때는 반드시 리스트컴프리헨션을 사용해야한다.
- 특정한 값의 원소를 지울때
- a = [1,2,3,4,5,5,5] remove_set = {3 , 5} # remove_set에 포함되지 않은 값만을 저장 result = [i for i in a if i not in remove_set] print(result ) #[1, 2, 4]
- 주요 메소드

| 메소드명 | 사용법 | 설명 | 시간복잡도 |
| --- | --- | --- | --- |
| append() | 변수명.append() | 리스트에 원소 삽입 | O(1) |
| sort() | 변수명.sort()
변수명.sort(reverse=True) | 오름차순 정렬
내림차순 정렬 | O(NlogN) |
| reverse() | 변수명.reverse() | 리스트 거꾸로 뒤집기 | O(N) |
| insert() | 변수명.insert(삽입할 위치인덱스, 삽입할 값) | 특정 인덱스에 원소 삽입 | O(N) |
| count() | 변수명.count(특정값) | 특정값을 가지는 데이터의 수 세기 | O(N) |
| remove() | 변수명.remove(특정값) | 특정 값을 가지는 데이터 삭제
(특정값이 여러개면 하나만 삭제) | O(N) |

문자열
- 이스케이프 문자로 백슬래시\를 이용
- “문" + “자열”
- a = “문" * 3 #문문문
- 정규표현식
  - re.sub('패턴', '바꿀문자열', '문자열', 바꿀횟수)
- 슬라이싱 기능

'안녕하세요'를 슬라이싱 한 결과
s[1:4] = 녕하세
s[1:-2] = 녕하
s[1:] = 녕하세요
s[:] = 안녕하세요
s[1:100] = 녕하세요
s[-1] = 요
s[-4] = 녕
s[:-3] = 안녕
s[-3:] = 하세요
s[::1] = 안녕하세요
s[::-1] = 요세하녕안
s[::2] = 안하요

튜플
- tuple = () 로 선언
- 선언 후 값 변경 불가
- 보통 (비용, 노드번호) 형태로 사용
- 리스트에 비해 공간 효율이 좋다.
딕셔너리
- 해시테이블을 이용해 O(1) 로 데이터의 검색 및 수정이 가능
- 선언
- data = dict() data['사과'] = 'Apple' data['바나나'] = 'Banana' data['코코넛'] = 'Coconut' print(data) #{'사과': 'Apple', '바나나' 'Banana’ ， '코코넛': 'Coconut'}
- 특정한 값이 있는지 검사
- #data = {'사과': 'Apple', '바나나' 'Banana’ ， '코코넛': 'Coconut'} if '사과' in data: print ("'사과'를 키로 가지는 데이터가 존재합니다 ")
- 주요메소드
- # 키 데이터만 담은 리스트 key_list = data.keys() # 값 데이터만 담은 리스트 value_list = data.values()
집합(set)
- 중복을 허용하지 않는다
- 순서가 없다 (인덱싱이 불가능하다)
- set = {} 또는 변수명 = set(list)로 선언
- 검색 시 O(1)
- 특정한 값이 등장한적이 있는지 검색할때 효과적
- 원본list와 set(list)의 length차이 비교하면 중복값이 있는지 확인 가능
- 연산
  - | : 합집합
  - & : 교집합
  - - : 차집합
- 주요 메소드

    | 메소드명 | 사용법 | 설명 | 시간복잡도 |
    | --- | --- | --- | --- |
    | add() | 변수명.add(값) | 원소 삽입 | O(1) |
    | update() | 변수명.update([리스트]) | 여러개 원소 삽입 | ? |
    | remove() | 변수명.remove(값) | 원소 삭제 | O(1) |

람다 = (lambda a, b: a + b)(3, 7)

주요 라이브러리

내장함수 : print(), input()과 같은 기본 입출력 기능, sorted()와 같은 정렬기능을 포함하고있는 기본 내장 라이브러리
- sum = 합 반환
- min = 가장 작은값 반환
- max = 가장 큰값 반환
- eval = 수식이 문자열로 들어오면 수식을 계산한 결과를 반환
- sorted = 정렬, key, reverse 옵션이 있다.
itertools : 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리이다.
- permutations = 리스트에서 모든 경우의 수를 반환
  list(permutations(data, 뽑을 인자 수))
- product = permutations과 비슷한데 a,a나 b,b도 나옴
  list(product(data, repeat = 뽑을 인자 수))
- combinations = 리스트에서 모든경우의 수를 반환 (a,b 와 b,a는 같은것으로 봄=중복제거)
  list(combinations(data, 뽑을 인자 수))
- combinations_with_replacement = combinations와 비슷하지만 a,a 나 b,b도 나옴
  list(combinations_with_replacement(data, 뽑을 인자 수))
heapq : 힙(Heap) 기능을 제공하는 라이브러리이다. 우선순위 큐 기능을 구현할 수 있다.
- heapq,heappush()
- heapq,heappop()
- 힙 정렬
- import heapq def heapsort(iterable): h = [] result = [] # 모든 원소를 차례대로 힘에 삽입 for value in iterable: heapq.heappush(h, value) # 힘에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i in range(len(h)): result.append(heapq.heappop(h)) return result result = heapsort([ l , 3, 5, 7, 9, 2, 4, 6, 8, 8]) print (result )
- 힙 내림차순
- import heapq def heapsort(iterable): h = [] result = [] # 모든 원소를 차례대로 힘에 삽입 for value in iterable: heapq.heappush(h, **-value**) # 힘에 삽입된 모든 원소를 차례대로 꺼내어 담기 for i in range(len(h)): result.append(**-heapq**.heappop(h)) return result result = heapsort([ l , 3, 5, 7, 9, 2, 4, 6, 8, 8]) print (result )
bisect : 이진 탐색(BinarySearch) 기능을제공하는 라이브러리이다.
from bisect import **bisect_left, bisect_right** # [left_v, right_v] 범위 내에 있는 원소 개수 출력 함수 def cnt_within_range (arr, left_v, right_v): # 맨 좌측 인덱스 left_idx = bisect_left(arr, left_v) # 맨 우측 인덱스 right_idx = bisect_right(arr, right_v) return right_idx - left_idx # 리스트 생성 arr = [5, 6, 7, 7, 7, 7, 8, 8, 9, 10] # 값이 9인 원소 개수 출력 print(cnt_within_range(arr, 9, 9)) # 1 # [4, 7] 범위 내에 있는 원소 개수 출력 print(cnt_within_range(arr, 4, 7)) # 6
collections : 데큐(deque), 카운터(Counter) 등의 자료구조를 위한 라이브러리이다
- deque = data = deque([2 , 3, 4])
- Counter = 등장횟수를 센다.
- from collections import Counter counter = Counter([ 'red', 'blue', 'red' , 'green', 'blue']) print(counter['blue']) # 'blue’가 등장한 횟수 출력 print(counter['green') # 'green‘이 등장한 횟수 출력 print(dict(counter)) # 사전 자료형으로 변환 #{'red': 2, 'blue': 3, 'green': 1}
math = 수학
- factorial(n) = 팩토리얼
- sqrt(x) = 제곱근
- gcd(a, b) = 최대공약수
- print(math.pi) # 파이(pi) 출력
- print(math.e ) # 자연상수 e 출력

큐/스택

큐
from collections import deque # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque() # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.popleft() queue.append(1) queue.append(4) queue.popleft() print(queue) # 먼저 들어온 순서대로 출력 queue.reverse() # 다음 출력을 위해 역순으로 바꾸기 print(queue) # 나중에 들어온 원소부터 출력
스택
stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력

DFS/BFS

인접 행렬방식으로 노드 구현
INF = 999999999 # 무한의 비용 선언 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph)
인접 리스트방식으로 노드 구현
# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현 graph = [[] for _ in range(3)] # 노드 0에 연결된 노드 정보 저장 (노드, 거리) graph[0].append((1, 7)) graph[0].append((2, 5)) # 노드 1에 연결된 노드 정보 저장 (노드, 거리) graph[1].append((0, 7)) # 노드 2에 연결된 노드 정보 저장 (노드, 거리) graph[2].append((0, 5)) print(graph)
인접행렬 = 모든관계를 저장해서 노드가 늘수록 메모리가 낭비 대신 두 노드가 연결되었는지 빠르게 알수있음
인접 리스트 = 행렬과 반대로 메모리는 적게쓰나 두 노드가 연결되었는지 알려면 오래걸림
DFS
# DFS 함수 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visited = [False] * 9 # 정의된 DFS 함수 호출 dfs(graph, 1, visited)
BFS
from collections import deque # BFS 함수 정의 def bfs(graph, start, visited): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque([start]) # 현재 노드를 방문 처리 visited[start] = True # 큐가 빌 때까지 반복 while queue: # 큐에서 하나의 원소를 뽑아 출력 v = queue.popleft() print(v, end=' ') # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입 for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visited = [False] * 9 # 정의된 BFS 함수 호출 bfs(graph, 1, visited)
예제
- 음료수 얼려먹기0 0 1 1 0·첫 번째줄에 얼음틀의세로 길이 N과 가로 길이 M이 주어진다 (1 ≤ N, M ≤ 1,000)
  • 두 번째 줄부터 N + 1번째 줄까지 얼음 틀의 형태가 주어진다
  • 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다
  - 한 번에 만들 수 있는 아이스크림의 개수를 출력한다
  - #DFS # N, M을 공백을 기준으로 구분하여 입력 받기 n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력 받기 graph = [] for i in range(n): graph.append(list(map(int, input()))) # DFS로 특정한 노드를 방문한 뒤에 연결된 모든 노드들도 방문 def dfs(x, y): # 주어진 범위를 벗어나는 경우에는 즉시 종료 if x <= -1 or x >= n or y <= -1 or y >= m: return False # 현재 노드를 아직 방문하지 않았다면 if graph[x][y] == 0: # 해당 노드 방문 처리 graph[x][y] = 1 # 상, 하, 좌, 우의 위치들도 모두 재귀적으로 호출 dfs(x - 1, y) dfs(x, y - 1) dfs(x + 1, y) dfs(x, y + 1) return True return False # 모든 노드(위치)에 대하여 음료수 채우기 result = 0 for i in range(n): for j in range(m): # 현재 위치에서 DFS 수행 if dfs(i, j) == True: result += 1 print(result) # 정답 출력
- 0 0 0 1 1
  1 1 1 1 1
- NXM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된
  다. 구멍이 뚫려 있는 부분끼리 상， 하， 좌， 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한
  다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성
  하시오. 다음의 4X5 얼음틀 예시에서는아이스크림이 총3개생성된다.
- 미로탈출
  - 첫째줄에두정수N,M(4200)01주어집니다. 다음N개의줄에는각각M개의정수(0
    혹은 1 )로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다 또한 시작 칸
    과 마지막칸은항상 1이다
  - ~~N,M~~
  - 첫째 줄에 최소 이동 간의 개수를 출력하라
  - 5 6
    1 0 1 0 1 0
    1 1 1 1 1 1
    0 0 0 0 0 1
    1 1 1 1 1 1
    1 1 1 1 1 1
  - #BFS from collections import deque # N, M을 공백을 기준으로 구분하여 입력 받기 n, m = map(int, input().split()) # 2차원 리스트의 맵 정보 입력 받기 graph = [] for i in range(n): graph.append(list(map(int, input()))) # 이동할 네 가지 방향 정의 (상, 하, 좌, 우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS 소스코드 구현 def bfs(x, y): # 큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append((x, y)) # 큐가 빌 때까지 반복하기 while queue: x, y = queue.popleft() # 현재 위치에서 4가지 방향으로의 위치 확인 for i in range(4): nx = x + dx[i] ny = y + dy[i] # 미로 찾기 공간을 벗어난 경우 무시 if nx < 0 or nx >= n or ny < 0 or ny >= m: continue # 벽인 경우 무시 if graph[nx][ny] == 0: continue # 해당 노드를 처음 방문하는 경우에만 최단 거리 기록 if graph[nx][ny] == 1: graph[nx][ny] = graph[x][y] + 1 queue.append((nx, ny)) # 가장 오른쪽 아래까지의 최단 거리 반환 return graph[n - 1][m - 1] # BFS를 수행한 결과 출력 print(bfs(0, 0))
- 동빈이는 NXM 크기의 직사각형 형태의 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이
  를피해 탈출해야한다. 통빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한
  번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로， 괴물이 없는 부분은 1로 표시되어 있
  다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최
  소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

정렬

선택정렬 = 가장 작은거를 선택해서 맨앞으로 넣는다. 비효율적 O(n2)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] # 스와프 print(array)
삽입정렬 = 데이터를 들고 하나씩 맞춰보다가 자기보다 큰 수 바로 앞에 삽입
(원래는 비효율적이나 거의 정렬된 리스트에선 효과적)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(array)): for j in range(i, 0, -1): # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법 if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동 array[j], array[j - 1] = array[j - 1], array[j] else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤 break print(array)
퀵 정렬 = 제일 많이 쓰는정렬로써 빠르고 최악일때 O(n)을 보장한다. 피벗을 지정해서 탐색범위를 줄인다
(이진탐색이랑 비슷)
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array, start, end): if start >= end: # 원소가 1개인 경우 종료 return pivot = start # 피벗은 첫 번째 원소 left = start + 1 right = end while(left <= right): # 피벗보다 큰 데이터를 찾을 때까지 반복 while(left <= end and array[left] <= array[pivot]): left += 1 # 피벗보다 작은 데이터를 찾을 때까지 반복 while(right > start and array[right] >= array[pivot]): right -= 1 if(left > right): # 엇갈렸다면 작은 데이터와 피벗을 교체 array[right], array[pivot] = array[pivot], array[right] else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체 array[left], array[right] = array[right], array[left] # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행 quick_sort(array, start, right - 1) quick_sort(array, right + 1, end) quick_sort(array, 0, len(array) - 1) print(array) ###좀더 직관적인 버전(처리속도는 조금 희생) array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quick_sort(array): # 리스트가 하나 이하의 원소만을 담고 있다면 종료 if len(array) <= 1: return array pivot = array[0] # 피벗은 첫 번째 원소 tail = array[1:] # 피벗을 제외한 리스트 left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분 right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분 # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환 return quick_sort(left_side) + [pivot] + quick_sort(right_side) print(quick_sort(array))
계수정렬 = 정렬대상과 대응되는 리스트를 생성하여 정렬
(데이터가 100만개 이하이고 양의정수일때 적용가능하며 빠름)
# 모든 원소의 값이 0보다 크거나 같다고 가정 array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] # 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화) count = [0] * (max(array) + 1) for i in range(len(array)): count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가 for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인 for j in range(count[i]): print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력
sort()와 sorted()
#sort는 리스트 원소값을 정렬(리스트를 반환하지 않음) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] array.sort() print(array) #sorted는 리스트를 반환(딕셔너리나 set을 파라미터로 던져도 리스트를 반환) array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] result = sorted(array) print(result) #key를 사용하여 정렬기준을 지정할 수 있다. key는 함수나 람다를 파라미터로 던진다 array = [('바나나', 2), ('사과', 5), ('당근', 3)] def setting(data): return data[1] result = sorted(array, key=setting) print(result)
엥간하면 sort()나 sorted()쓰는게 효율 제일 잘나온다고함

이진탐색

이진탐색 = 정렬되어 있을때만 사용가능하며, 중간값을 기준으로 탐색범위를 나눈다.
# 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array, target, start, mid - 1) # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: return binary_search(array, target, mid + 1, end) # n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기 n, target = list(map(int, input().split())) # 전체 원소 입력 받기 array = list(map(int, input().split())) # 이진 탐색 수행 결과 출력 result = binary_search(array, target, 0, n - 1) if result == None: print("원소가 존재하지 않습니다.") else: print(result + 1) # 이진 탐색 소스코드 구현 (반복문) def binary_search(array, target, start, end): while start <= end: mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: end = mid - 1 # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: start = mid + 1 return None # n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기 n, target = list(map(int, input().split())) # 전체 원소 입력 받기 array = list(map(int, input().split())) # 이진 탐색 수행 결과 출력 result = binary_search(array, target, 0, n - 1) if result == None: print("원소가 존재하지 않습니다.") else: print(result + 1)
순차탐색 = 그냥 순서대로 본다.
# 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): # 현재의 원소가 찾고자 하는 원소와 동일한 경우 if array[i] == target: return i + 1 # 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기) return -1 # 원소를 찾지 못한 경우 -1 반환 print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.") input_data = input().split() n = int(input_data[0]) # 원소의 개수 target = input_data[1] # 찾고자 하는 문자열 print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.") array = input().split() # 순차 탐색 수행 결과 출력 print(sequential_search(n, target, array))

다이나믹 프로그래밍

피보나치
# 그냥 구현하면 너무 오래걸림 # 재귀의 깊이제한이 문제가 될 때 sys모듈을 이용하여 풀어줄 수있다. import sys sys.setrecursionlimit(10**7) # 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화 d = [0] * 100 # 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍) def fibo(x): # 종료 조건(1 혹은 2일 때 1을 반환) if x == 1 or x == 2: return 1 # 이미 계산한 적 있는 문제라면 그대로 반환 if d[x] != 0: return d[x] # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환 d[x] = fibo(x - 1) + fibo(x - 2) return d[x] print(fibo(99))

최단경로

다익스트라
import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n + 1)] # 방문한 적이 있는지 체크하는 목적의 리스트를 만들기 visited = [False] * (n + 1) # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n + 1) # 모든 간선 정보를 입력받기 for _ in range(m): a, b, c = map(int, input().split()) # a번 노드에서 b번 노드로 가는 비용이 c라는 의미 graph[a].append((b, c)) # 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환 def get_smallest_node(): min_value = INF index = 0 # 가장 최단 거리가 짧은 노드(인덱스) for i in range(1, n + 1): if distance[i] < min_value and not visited[i]: min_value = distance[i] index = i return index def dijkstra(start): # 시작 노드에 대해서 초기화 distance[start] = 0 visited[start] = True for j in graph[start]: distance[j[0]] = j[1] # 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복 for i in range(n - 1): # 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리 now = get_smallest_node() visited[now] = True # 현재 노드와 연결된 다른 노드를 확인 for j in graph[now]: cost = distance[now] + j[1] # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 if cost < distance[j[0]]: distance[j[0]] = cost # 다익스트라 알고리즘을 수행 dijkstra(start) # 모든 노드로 가기 위한 최단 거리를 출력 for i in range(1, n + 1): # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력 if distance[i] == INF: print("INFINITY") # 도달할 수 있는 경우 거리를 출력 else: print(distance[i])
다익스트라(개선)
import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(input()) # 각 노드에 연결되어 있는 노드에 대한 정보를 담는 리스트를 만들기 graph = [[] for i in range(n + 1)] # 최단 거리 테이블을 모두 무한으로 초기화 distance = [INF] * (n + 1) # 모든 간선 정보를 입력받기 for _ in range(m): a, b, c = map(int, input().split()) # a번 노드에서 b번 노드로 가는 비용이 c라는 의미 graph[a].append((b, c)) def dijkstra(start): q = [] # 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입 heapq.heappush(q, (0, start)) distance[start] = 0 while q: # 큐가 비어있지 않다면 # 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기 dist, now = heapq.heappop(q) # 현재 노드가 이미 처리된 적이 있는 노드라면 무시 if distance[now] < dist: continue # 현재 노드와 연결된 다른 인접한 노드들을 확인 for i in graph[now]: cost = dist + i[1] # 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우 if cost < distance[i[0]]: distance[i[0]] = cost heapq.heappush(q, (cost, i[0])) # 다익스트라 알고리즘을 수행 dijkstra(start) # 모든 노드로 가기 위한 최단 거리를 출력 for i in range(1, n + 1): # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력 if distance[i] == INF: print("INFINITY") # 도달할 수 있는 경우 거리를 출력 else: print(distance[i])
플로이드 워셜
INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수 및 간선의 개수를 입력받기 n = int(input()) m = int(input()) # 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화 graph = [[INF] * (n + 1) for _ in range(n + 1)] # 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화 for a in range(1, n + 1): for b in range(1, n + 1): if a == b: graph[a][b] = 0 # 각 간선에 대한 정보를 입력 받아, 그 값으로 초기화 for _ in range(m): # A에서 B로 가는 비용은 C라고 설정 a, b, c = map(int, input().split()) graph[a][b] = c # 점화식에 따라 플로이드 워셜 알고리즘을 수행 for k in range(1, n + 1): for a in range(1, n + 1): for b in range(1, n + 1): graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]) # 수행된 결과를 출력 for a in range(1, n + 1): for b in range(1, n + 1): # 도달할 수 없는 경우, 무한(INFINITY)이라고 출력 if graph[a][b] == 1e9: print("INFINITY", end=" ") # 도달할 수 있는 경우 거리를 출력 else: print(graph[a][b], end=" ") print()

구현 Tip

리스트 내 원소 교체
# 0 인덱스와 1 인덱스의 원소 교체하기 array = [3, 5] array[0], array[1] = array[1], array[0] print(array)
readline() = 빠르게 입력받기
import sys # 하나의 문자열 데이터 입력 받기 input_data = sys.stdin.readline().rstrip() # 입력 받은 문자열 그대로 출력하기 print(input_data) #readline()을 쓰고나면 반드시 rstrip()함수를 호출해야한다. #readline()입력 후 엔터가 줄바꿈 기호로 입력되기 때문에 rstrip()으로 제거해줘야한다

알고리즘 Tip

최댓값과 최솟값을 찾는 문제에선 Heap을 사용한다.
탐색할 건수가 엄청나게 많으면 이진탐색을 이용한다.
- 이진탐색은 정렬된 자료에서 사용 가능하다.

저작자표시