1. 수학
2. 다이나믹 프로그래밍
3. 그래프 이론
4. 문자열
5. 그리디 알고리즘
6. 그래프 탐색
7. 정렬
1) 일곱 난쟁이
import sys
input = sys.stdin.readline
array = [int(input()) for _ in range(9)]
#7명, 합 100
array.sort()
need = sum(array) - 100
for i in range(0, 9):
n = array[i] # 리스트 순서대로 값 지정
array.remove(n)
if need - n in array:
array.remove(need - n)
break
else:
array.insert(i, n)
for i in array:
print(i, sep='\n')
//2
import sys
input = sys.stdin.readline
array = [int(input) for _ in range(9)]
#7명, 합 100
array.sort()
s = sum(arr)
for i in range(9):
for j in range(i+1, 9):
if s - (array[i]+array[j]) == 100:
for k in range(9):
if k == i or k == j:
continue
else:
print(array[k])
exit()
8. 세그먼트 트리
9. 트리
1) 트리 순회
import sys
from collections import defaultdict
input = sys.stdin.readline
n = int(input())
tree = defaultdict(list)
for _ in range(n):
n, l, r = map(str, input().split())
tree[n] = [l, r]
result = [""] * 3
def dfs(node):
result[0] += node
if tree[node][0] != ".":
dfs(tree[node][0])
result[1] += node
if tree[node][1] != ".":
dfs(tree[node][1])
result[2] += node
dfs("A")
for i in result:
print(i)
2)
10. 이분 탐색
1) 나무 자르기
import sys
input = sys.stdin.readline
#나무 수, 나무 길이
n, m = map(int, input().split())
data = list(map(int, input().split()))
start, end = 0, max(data)
answer = -sys.maxsize
while start <= end:
mid = (start + end) // 2
total = 0
for d in data:
if d > mid:
total += (d - mid)
if total >= m:
answer = mid
start = mid + 1
else:
end = mid - 1
print(answer)
2) 공유기 설치
import sys
input = sys.stdin.readline
#집, 공유기
n, c = map(int, input().split())
data = []
for _ in range(n):
data.append(int(input()))
data.sort()
start, end = 1, data[-1] - data[0] #가장 먼 간격
while start <= end:
mid = (start + end) // 2
value = data[0]
count = 1
for i in range(1, n):
if data[i] >= value + mid:
value = data[i]
count += 1
if count >= c:
answer = mid
start = mid + 1
else:
end = mid - 1
print(answer)
3) K번째 수
1*1~1*10
2*1~2*10
3*1~3*6
...
10*1~10*2위 수가 존재할텐데, 이는 반대로 생각해보면 20을 행으로 나눈 몫이다.
20//1: 10개 --> 단 열의 숫자(n*n배열이므로)를 초과할 수 없다.
20//2: 10개
20//3: 6개
//https://developmentdiary.tistory.com/m/354
1 2 3
2 4 6
3 6 9
1 이하의 수는 1개
2 이하의 수는 3개
3 이하의 수는 5개
4 이하의 수는 6개
5 이하의 수는 6개
6 이하의 수는 8개
7 이하의 수는 8개
8 이하의 수는 8개
9 이하의 수는 9개
- 자 여기서 어떻게 8번째 수가 7,8이 아닌 6임을 알 수 있느냐면..
6을 보면, 6 이하의 수는 8개 이지만, 4 이하의 수는 6입니다. 그러한가요?
그런데 7을 보면, 7 이하의 수는 8개이지만, 6이하의 수 역시 8개입니다. 이 말인 즉슨,
7은 존재하지 않는다는 겁니다.
8을 봐도 마찬가지입니다. 8이하의 수는 8개이지만, 7이하의 수 역시 8개입니다. 이
말인 즉슨, 8 역시 존재하지 않는다는 겁니다.
n, k = int(input()), int(input())
#어떤 수보다 작은 자연수의 곱(i * j)이 몇 개인지
#A보다 작은 숫자가 몇개인지 찾아내면 A가 몇 번째 숫자인지 알 수 있다.
start, end = 1, k
while start <= end:
mid = (start + end) // 2
temp = 0
for i in range(1, n + 1):
temp += min(mid//i, n) #mid 이하의 i의 배수 or 최대 n
if temp >= k: #이분탐색 실행
answer = mid
end = mid - 1
else:
start = mid + 1
print(answer)
// 시간 복잡도 -> O(n²)
import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
A = [[-1] * (n + 1) for _ in range(n + 1)]
B = [-1]
for i in range(1, n + 1):
for j in range(1, n + 1):
A[i][j] = i * j
for i in range(1, n + 1):
for j in range(1, n + 1):
B.append(A[i][j])
B.sort()
print(B[k])
11. 깊이 우선 탐색
12. 조합론
13. 누적 합
14. 비트마스킹
1) 막대기
-
조건을 해보면 결국은 주어진 x를 몇 개의 2의 배수를 사용해 만들 수 있느냐 하는 문제
-
이진수에서 1이 몇 개인지 세는 방법
#option first
import sys
input = sys.stdin.readline
x = int(input())
answer = 0
x = bin(x)
for i in x:
if i == '1': #1의 개수 세기
answer += 1
print(answer)
#option second
import sys
input = sys.stdin.readline
x = int(input())
answer = 0
while x > 0:
#맨 마지막 비트가 꺼짐
#4는 100, 3은 011
#4와 3을 &연산하면 0
x &= (x-1)
answer += 1
print(answer)
#option third
import sys
input = sys.stdin.readline
x = int(input())
answer = 0
while x > 0:
#마지막 비트가 켜져있는지 1과 &연산을 통해 확인
answer += x & 1
x >>= 1 #2로 나누기
print(answer)
2) 집합
#include <iostream>
using namespace std;
int main() {
int N, val;
string cmd;
int sett = 0;
ios::sync_with_stdio(0); cin.tie(0);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> cmd;
if (cmd == "add") {
cin >> val;
sett = sett | (1 << val);
}
else if (cmd == "remove") {
cin >> val;
sett &= ~(1 << val);
}
else if (cmd == "check") {
cin >> val;
if (sett & (1 << val)) cout << 1 << '\n';
else cout << 0 << '\n';
}
else if (cmd == "toggle") {
cin >> val;
sett ^= (1 << val);
}
else if (cmd == "empty") sett = 0;
else sett = (1 << 21) - 1;
}
return 0;
}
#메모리 초과 - 파이썬은 안됨
import sys
input = sys.stdin.readline
m = int(input())
mark = 0
for _ in range(m):
data = input().split()
if data[0] == "all":
mark = (1 << 20) - 1
elif data[0] == "empty":
mark = 0
else:
s = data[0]
n = int(data[1]) - 1
if s == "add":
mark |= (1 << n)
elif s == "remove":
mark &= ~(1 << n)
elif s == "check":
if mark & (1 << n) == 0:
print(0)
else:
print(1)
elif s == "toggle":
mark = mark ^ (1 << n)
3) 가르침
15. 분할 정복
16. 다익스트라
1) 합승 택시 요금
import sys
import heapq
def dijkstra(s, e):
global graph, length
distance = [sys.maxsize]*(length+1)
distance[s] = 0
q = []
heapq.heappush(q, [0, s])
while q:
cost, now = heapq.heappop(q)
if cost > distance[now]:
continue
for i in graph[now]:
node, dist = i, graph[now][i]
dist += cost
if dist < distance[node]:
distance[node] = dist
heapq.heappush(q, [dist, node])
return distance[e]
def solution(n, s, a, b, fares):
global graph, length
answer = sys.maxsize
graph = [{} for _ in range(n+1)]
length = n
for i, j, cost in fares:
graph[i][j] = cost
graph[j][i] = cost
for i in range(1, n+1):
answer = min(answer, dijkstra(s, i) + dijkstra(i, a) + dijkstra(i, b))
return answer
2)
17. 우선순위 큐
18. 투포인터
1) 수들의 합2
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
array = list(map(int, input().split()))
count = 0
left = right = s = 0
while True:
if s >= m:
s -= array[left]
left += 1
else:
if right == n:
break
s += array[right]
right += 1
if s == m:
count += 1
print(count)
n, m = map(int, input().split())
data = list(map(int, input().split()))
cnt = 0
s = 0
end = 0
for start in range(n) :
while s < m and end < n :
s += data[end]
end += 1
if s == m :
cnt += 1
s -= data[start]
print(cnt)
2) 두 용액
import sys
input = sys.stdin.readline
n = int(input())
array = sorted(list(map(int, input().split())))
count = 0
left, right = 0, n - 1
min = abs(array[left] + array[right])
kleft, kright = left, right
while left < right:
temp = array[left]+array[right]
if abs(temp) < min:
kleft, kright = left, right
min = abs(temp)
if min == 0:
break
if temp > 0:
right -= 1
else:
left += 1
print(array[kleft], array[kright])
3) 수열
//투포인터
import sys
input = sys.stdin.readline
n, k = map(int, input().split()) #연속적인 날짜의 수
array = list(map(int, input().split()))
result = -sys.maxsize
right, cur = 0, 0
for left in range(n-k+1):
while right < left + k and right < n:
cur += array[right]
right += 1
result = max(cur, result)
cur -= array[left]
print(result)
//누적합
import sys
input = sys.stdin.readline
n, k = map(int, input().split()) #연속적인 날짜의 수
array = list(map(int, input().split()))
result = -sys.maxsize
part_sum = sum(array[:k])
result_list = [part_sum]
for i in range(0, len(array)-k):
part_sum = part_sum - array[i] + array[i + k]
result_list.append(part_sum)
print(max(result_list))
//시간 초과
import sys
input = sys.stdin.readline
n, k = map(int, input().split()) #연속적인 날짜의 수
array = list(map(int, input().split()))
result = -sys.maxsize
for i in range(n - k + 1):
result = max(result, sum(array[i:i+k]))
print(result)
19. 연결 리스트
20. 트라이
21. 슬라이딩 윈도우
22. 단절점과 단절선
23. 플로이드워셜
24. 위상 정렬
25. 최소 공통 조상
26. 최소 스패닝 트리
27. 에라토스테네스의 체
1) 소수 찾기
import sys
input = sys.stdin.readline
n = int(input())
array = list(map(int, input().split()))
count = 0
for i in array:
r = 0
if i == 1 or i == 0:
continue
for j in range(2, i):
if i % j == 0:
r += 1
if r == 0:
count += 1
print(count)
2) 소수 구하기
// 제곱근 만큼 구하기
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
for i in range(n, m + 1):
flag = 0
if i == 1 or i == 0:
continue
for j in range(2, int(i**0.5)+1):
if i % j == 0:
flag = 1
break
if flag == 0:
print(i)
// 시간초과
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
array = list(range(n,m))
for i in array:
r = 0
if i == 1 or i == 0:
continue
for j in range(2, i):
if i % j == 0:
r += 1
break
if r == 0:
print(i)
3) 에라토스테네스의 체
'''
1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.
'''
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
array = [1] * (n + 1)
count = 0
for i in range(2, n + 1):
for j in range(i, n + 1, i):
if array[j]:
array[j] = 0
count += 1
if count == k:
print(j)
break
28. 가장 긴 증가하는 부분 수열
29. 정수론
30. 조합론
31. 백트래킹
1) N과 M (1)
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
keep = []
def permutation():
if m == len(keep):
for k in keep:
print(k, end = ' ')
print()
return
for i in range(1, n + 1):
if i not in keep:
keep.append(i)
permutation()
keep.pop()
permutation()
2) N-Queen
import sys
input = sys.stdin.readline
n = int(input())
def dfs(arr):
global ans
length = len(arr)
if length==n:
ans+=1
return
candidate = list(range(n)) # 후보가 될 수 있는 자리를 0부터 n-1까지 만들고 제외하는 방법을 사용
for i in range(length):
if arr[i] in candidate: # 같은 가로줄에 있으면 후보에서 제외
candidate.remove(arr[i])
distance = length - i
if arr[i] + distance in candidate: # 같은 '/' 대각선에 있으면 후보에서 제외
candidate.remove(arr[i] + distance)
if arr[i] - distance in candidate: # 같은 '\' 대각선에 있으면 후보에서 제외
candidate.remove(arr[i] - distance)
if candidate:
for i in candidate:
arr.append(i)
dfs(arr)
arr.pop()
else:
return
ans = 0
for i in range(n):
dfs([i])
print(ans)
32. 서로소 집합 자료구조
1) 공항
import sys
g = int(input())
p = int(input())
plane = [int(input()) for _ in range(p)]
def find(x):
if x == parent[x]:
return x
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
x = find(x)
y = find(y)
parent[x] = y
parent = {i: i for i in range(g + 1)}
cnt = 0
for i in plane:
x = find(i) #부모 찾기
if x == 0:
break
union(x, x - 1) #부모 바로 밑으로 이어줌, 도킹되지 않은 가장 큰 게이트 번호 갖는다.
cnt += 1
print(cnt)
2) 여행 가자
import sys
n = int(input())
m = int(input())
parent = {i: i for i in range(n + 1)}
def find(x):
if x == parent[x]:
return x
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
x = find(x)
y = find(y)
if x == y:
return
if x < y:
parent[y] = x
else:
parent[x] = y
for a in range(1, n + 1):
data = list(map(int, input().split()))
for b in range(1, len(data)+1):
if data[b - 1] == 1:
union(a, b)
plan = list(map(int, input().split()))
result = set([find(i) for i in plan])
if len(result) != 1:
print('NO')
else:
print('YES')
For the sake of someone who studies computer science