Python
[알고리즘] CheatSheet - python
다익스트라 import heapq def dijkstra(n): # O(ElogV) hq = [(0, n)] dis[n] = 0 while hq: cur_dis, cur_x = heapq.heappop(hq) if cur_dis > dis[cur_x]: continue for i, w in graph[cur_x]: new_dis = cur_dis + w if dis[i] > new_dis: dis[i] = new_dis heapq.heappush(hq, (new_dis, i)) 벨만 포드 def bellman_ford(n): # O(VE) min_d = [float('inf')] * (v + 1) min_d[n] = 0 for i in range(v): for j in range(e): a, b, w =..
[Python] 백준(BOJ) 9663번 N-Queen(백트래킹)
9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 예제 입력 1 8 예제 출력 1 92 코드 n = int(input()) arr = [0] * n cnt = 0 def det(num): # 검증 함수 for v in ..
[Python] 중복순열, 중복조합(itertools.product, combinations_with_replacement)
import itertools alphabet = ['A', 'B', 'C'] # 문자열이나 range로도 가능 print([*itertools.product(alphabet, alphabet)]) # 2개의 원소로 중복순열 print([*itertools.product(alphabet, repeat=3)]) # 3개의 원소로 중복순열 print() print([*itertools.combinations_with_replacement(alphabet, 2)]) # 2개의 원소로 중복조합 출력값 [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B..
[Python] collections.Counter
import collections li = [1, 2, 3, 4, 5, 6, 7, 8, 7, 9, 1, 3, 5, 7, 9, 1, 5, 9, 0, 1, 10, 100, 10, 1] cnt = collections.Counter(li) print(cnt[1]) # 1의 개수: 5 print(cnt[2]) # 2의 개수: 1 print(cnt[3]) # 3의 개수: 2 print(cnt[5]) # 5의 개수: 3 print(cnt[10]) # 10의 개수: 2 print(cnt[100]) # 100의 개수: 1 출력값 5 1 2 3 2 1
[Python] 순열, 조합(itertools.permutations, combinations)
import itertools alphabet = ['A', 'B', 'C'] # 문자열이나 range로도 가능 print([*itertools.permutations(alphabet)]) # 3개의 원소로 순열 print([*itertools.permutations(alphabet, 2)]) # 2개의 원소로 순열 print() print([*itertools.combinations(alphabet, 2)]) # 2개의 원소로 조합 출력값 [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')] [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'..
[Python] 백준(BOJ) 10989번 수 정렬하기 3 (계수 정렬)
문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 예제 입력 1 10 5 2 3 1 4 2 3 5 1 7 예제 출력 1 1 1 2 2 3 3 4 5 5 7 코드 import sys input = sys.stdin.readline print = sys.stdout.write arr = [0]*10000 for i in range(int(input())): # 1~10000까지 각 숫자의 개수 구하기 arr[int(input..
[Python] 누적합 itertools.accumulate
from itertools import accumulate li = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] ac = list(accumulate(li)) print(li) print(ac) 출력값 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] [1, 3, 6, 10, 15, 21, 28, 36, 45, 55]
[Python] 힙 자료구조 Heapqueue
가장 작은 값이 항상 앞에 오는 자료구조 - 최대값, 최솟값을 빠르게 찾아내기 위해 고안되었다 import heapq heap = [] heapq.heappush(heap, 5) # heap = [ 5 ] heapq.heappush(heap, 1) # heap = [ 1, 5 ] heapq.heappush(heap, 2) # heap = [ 1, 5, 2 ] heapq.heappop(heap) # heap = [ 2, 5 ] print(heap) 출력값 [2, 5] heap = [ 5, 1, 2 ] heapq.heapify(heap) # heap = [ 1, 5, 2 ] print(heap) 출력값 [1, 5, 2]