0.개요
2024년도 제11회 한국기술교육대학교 프로그래밍 경시대회준비용으로 만든 알고리즘 예시
1.자바
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public void solution() throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringBuilder sb = new StringBuilder();
int n = Integer.parseInt(br.readLine());
for (int i=0; i<n; ++i) {
StringTokenizer st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
for (int j=0; j<s; ++j) {
int data = Integer.parseInt(st.nextToken());
sb.append(data).append('\n');
}
}
br.close();
bw.write(sb.toString());
bw.flush();
bw.close();
}
public static void main(String[] args) throws Exception {
new Main().solution();
}
}
다이나믹 ←점화식찾아라
public static int fibonacci(int n) {
if (n <= 1)
return n;
else
return fibonacci(n - 2) + fibonacci(n - 1);
}
투포인터← 처음에는 start=end=0(다를수도) 이고, 조건은 항상 두 포인터들의 관계는 start<=end이다.
슬라이딩 윈도우← 앞에뺴고 뒤에 더하고 하면서 하는거
Math
// 1. 최대 최소
Math.max(10, 2);
Math.min(10, 2);
// 2. 절대값
Math.abs();
// 3. 올림 내림 반올림
Math.ceil(-3.2); // -3
Math.floor(-3.2); // -4
Math.round(-3.26); // -3 첫째자리에서 반올림
// 3-1. 소수 둘째, 셋째 자리에서 반올림 하고 싶다면
double a = 1.23456;
String b = String.format("%.1f", a); // .1f는 둘째자리에서 반올림
// 4. 제곱 제곱근
Math.pow(2, 2); // 2^2 = 4
Math.sqrt(4); // 2
BFS
import java.util.*;
public class BFSExample {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt(); // 노드 수
int M = scanner.nextInt(); // 간선 수
int R = scanner.nextInt(); // 시작 노드
// 방문 기록 및 그래프 초기화
int[] visited = new int[N + 1];
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 1; i <= N; i++) {
graph.put(i, new ArrayList<>());
}
// 그래프 입력
for (int i = 0; i < M; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
graph.get(a).add(b);
graph.get(b).add(a);
}
// BFS 수행
Queue<Integer> needVisit = new LinkedList<>();
needVisit.add(R);
int number = 1;
while (!needVisit.isEmpty()) {
int n = needVisit.poll();
if (visited[n] == 0) {
visited[n] = number++;
// 인접 노드 정렬
List<Integer> neighbors = graph.get(n);
Collections.sort(neighbors, Collections.reverseOrder());
// 방문할 노드 추가
needVisit.addAll(neighbors);
}
}
// 결과 출력
for (int i = 1; i <= N; i++) {
System.out.println(visited[i]);
}
scanner.close();
}
}DFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static Map<Integer, ArrayList<Integer>> grape = new HashMap<Integer, ArrayList<Integer>>();
static int N;
static int[] visited;
static int count = 1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int start = Integer.parseInt(st.nextToken());
for(int i = 1; i <= N; i++) {
grape.put(i, new ArrayList<Integer>());
}
visited = new int[N + 1];
int a, b;
for(int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
grape.get(a).add(b);
grape.get(b).add(a);
}
for(int i = 1; i <= N; i++) {
Collections.sort(grape.get(i), Collections.reverseOrder());
}
dfs(start);
StringBuilder sb = new StringBuilder();
for(int i = 1; i <= N; i++) {
sb.append(visited[i]).append("\n");
}
System.out.println(sb);
}
public static void dfs(int node) {
visited[node] = count;
count++;
for(int n : grape.get(node)) {
if (visited[n] == 0) {
visited[n] = visited[node] + 1;
dfs(n);
}
}
}
}위상정렬
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
// 첫 번째 줄에서 N(노드 수)과 M(간선 수) 입력
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int M = Integer.parseInt(input[1]);
StringBuffer sb = new StringBuffer(); // 결과를 저장할 StringBuffer
// 그래프와 진입 차수를 위한 리스트 및 배열 초기화
List<List<Integer>> graph = new ArrayList<>();
int[] linked = new int[N + 1]; // 각 노드의 진입 차수 저장
// 그래프 초기화
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
// 간선 정보 입력
for (int i = 0; i < M; i++) {
String[] input2 = br.readLine().split(" ");
int start = Integer.parseInt(input2[0]); // 시작 노드
int target = Integer.parseInt(input2[1]); // 도착 노드
linked[target] += 1; // 도착 노드의 진입 차수 증가
graph.get(start).add(target); // 그래프에 간선 추가
}
// 진입 차수가 0인 노드를 찾기 위한 큐 초기화
Queue<Integer> queue = new LinkedList<>();
// 모든 노드를 검사하여 진입 차수가 0인 노드를 큐에 추가
for (int i = 1; i < linked.length; i++) {
if (linked[i] == 0) {
queue.add(i);
}
}
// 위상 정렬 수행
while (!queue.isEmpty()) {
Integer current = queue.poll(); // 큐에서 노드 꺼내기
sb.append(current + " "); // 결과에 추가
List<Integer> nodeList = graph.get(current); // 현재 노드의 인접 노드 리스트
for (Integer node : nodeList) {
// 해당 노드의 진입 차수를 감소시키고, 진입 차수가 0이 되면 큐에 추가
if (--linked[node] == 0) {
queue.add(node);
}
}
}
// 결과 출력
bw.write(sb.toString());
bw.close(); // BufferedWriter 닫기
br.close(); // BufferedReader 닫기
}
}다익스트라
import java.io.*;
import java.util.*;
public class Main {
static final int INF = (int) 1e9; // 무한대를 나타내는 값
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine().trim()); // 노드 수
int M = Integer.parseInt(br.readLine().trim()); // 엣지 수
List<List<int[]>> graph = new ArrayList<>(N + 1); // 그래프 초기화
for (int i = 0; i <= N; i++) {
graph.add(new ArrayList<>());
}
// 그래프에 엣지 추가
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine().trim());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.get(a).add(new int[]{b, cost}); // (목적지 노드, 비용)
}
st = new StringTokenizer(br.readLine().trim());
int start = Integer.parseInt(st.nextToken()); // 시작 노드
int end = Integer.parseInt(st.nextToken()); // 도착 노드
// 시작 노드와 도착 노드가 같을 경우 0 출력
if (start == end) {
System.out.println(0);
return;
}
int[] V = new int[N + 1]; // 최단 경로 저장 배열
Arrays.fill(V, INF); // 모든 값을 무한대로 초기화
V[start] = 0; // 시작 노드의 비용은 0
// 우선순위 큐 초기화
PriorityQueue<int[]> hq = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
hq.add(new int[]{start, 0}); // 시작 노드 추가
while (!hq.isEmpty()) {// 다익스트라 알고리즘 수행
int[] current = hq.poll(); // 현재 노드와 비용 가져오기
int now = current[0];
int cost = current[1];
// 도착 노드에 대한 최단 경로 비용이 현재 비용보다 작거나 같을 경우 continue
if (V[end] <= cost) continue;
if (graph.get(now).isEmpty()) continue; // 현재 노드에 연결된 노드가 없을 경우
// 인접 노드들에 대해 최단 경로 업데이트
for (int[] next : graph.get(now)) {
int nextNode = next[0]; // 다음 노드
int nextCost = next[1]; // 다음 노드로 가는 비용
if (V[nextNode] > nextCost + cost) { // 새로운 비용이 더 작을 경우 업데이트
V[nextNode] = nextCost + cost; // 최단 경로 갱신
hq.add(new int[]{nextNode, nextCost + cost}); // 우선순위 큐에 추가
}
}
}
System.out.println(V[end]); // 도착 노드의 최단 경로 비용 출력
}
}유니온파인드
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
private static int n, m;
private static int[] parent;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); //n : 집합의 수
m = Integer.parseInt(st.nextToken()); //m :연산의 수
parent = new int[n+1];
//배열 초기화
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
for (int i = 1; i <= m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
//결과 출력
if(a == 1){
boolean equals = equalsparent(b, c);
if(equals == true) bw.write("YES" + "\n");
else bw.write("NO" + "\n");
//a == 0 : 집합 합침
}else{
union(b, c);
}
bw.flush();
}
bw.close();
br.close();
}
//집합 합치기
private static void union(int a, int b) {
int x = find(a);
int y = find(b);
if (x < y) {
parent[y] = x;
} else {
parent[x] = y;
}
}
//최상위 부모 찾기
private static int find(int a) {
if (parent[a] == a)
return a;
return parent[a] = find(parent[a]);
}
//같은 집합인지 확인
private static boolean equalsparent(int a, int b) {
int x = find(a);
int y = find(b);
return x == y;
}
}정렬
List<Type> list = Arrays.asList(value1, value2, ...);
Collections.sort(list); // 오름차순 정렬
Collections.sort(list, Collections.reverseOrder()); //내림차순
int[] array = {value1, value2, ...};
Arrays.sort(array); // 오름차순 정렬
Integer[] array = {value1, value2, ...};
Arrays.sort(array, Collections.reverseOrder()); //내림차순
이진탐색
int[] array = {1, 3, 5, 7, 9}; // 정렬된 배열
int index = Arrays.binarySearch(array, 5); // 5의 인덱스를 찾음
List<Integer> list = Arrays.asList(1, 3, 5, 7, 9); // 정렬된 리스트
int index = Collections.binarySearch(list, 5); // 5의 인덱스를 찾음
문자열
char charAt(int index) 특정 위치의 문자를 리턴합니다.
boolean equals(Object anObject) 두 문자열을 비교합니다.
int indexOf(String str) 문자열 내에서 주어진 문자열의 위치를 리턴합니다.
int length() 총 문자의 수를 리턴합니다.
String replace(1,2) target 부분을 replacement로 대치한 새로운 문자열을 리턴합니다.
String substring(int beginIndex) beginIndex 위치에서 끝까지 잘라낸 새로운 문자열을 리턴합니다.
String toLowerCase() 알파벳 소문자로 변환한 새로운 문자열을 리턴합니다.
String toUpperCase() 알파벳 대문자로 변환한 새로운 문자열을 리턴합니다.
String trim() 앞뒤 공백을 제거한 새로운 문자열을 리턴합니다.
String valueOf(int i)
str.equals(String) 비교
valueOf(double d) 기본 타입 값을 문자열로 리턴합니다.
boolean contains(CharSequence s)
주어진 문자열이 해당 문자열에 포함되어 있는지 여부를 리턴합니다.
String[] split(String regex)
주어진 정규 표현식에 따라 문자열을 분리하고, 그 결과를 문자열 배열로 리턴합니다.
int compareTo(String anotherString)
두 문자열을 사전 순으로 비교합니다.
String join(CharSequence delimiter, CharSequence... elements)
주어진 구분자를 사용하여 여러 문자열을 하나의 문자열로 결합합니다.
String repeat(int count)
현재 문자열을 주어진 횟수만큼 반복한 새로운 문자열을 리턴합니다.
boolean matches(String regex)
문자열이 주어진 정규 표현식과 일치하는지 여부를 리턴합니다.
String replaceAll(String regex, String replacement)
주어진 정규 표현식과 일치하는 모든 부분을 다른 문자열로 대체한 새로운 문자열을 리턴합니다.
String strip()
문자열의 앞뒤 공백을 제거한 새로운 문자열을 리턴합니다.
CharSequence subSequence(int start, int end)
주어진 시작과 끝 인덱스 사이의 부분 문자열을 리턴합니다.
자료구조
ArrayList<String> list = new ArrayList<>();
- add(Object element): 요소를 끝에 추가.
- add(int index, Object element): 지정된 위치에 요소 추가.
- get(int index): 인덱스의 요소 반환.
- set(int index, Object element): 인덱스의 요소 수정.
- remove(int index): 인덱스의 요소 삭제.
- remove(Object element): 해당 요소 삭제 (첫 번째 일치).
- size(): 리스트 크기 반환.
- isEmpty(): 리스트가 비었는지 확인.
- clear(): 모든 요소 삭제.
- contains(Object element): 요소가 포함되어 있는지 확인.
- indexOf(Object element): 요소의 첫 번째 인덱스 반환.
- lastIndexOf(Object element): 요소의 마지막 인덱스 반환.
- toArray(): 배열로 변환.
- toString(): 문자열
Stack<String> stack = new Stack<>();
- push(Object element): 스택의 맨 위에 요소 추가.
- pop(): 스택의 맨 위 요소 제거 및 반환.
- peek(): 스택의 맨 위 요소 반환 (제거 안 함).
- isEmpty(): 스택이 비어 있는지 확인.
- search(Object element): 요소의 위치 반환 (맨 위에서부터).
Queue<String> queue = new LinkedList<>();
- add(Object element): 큐의 끝에 요소 추가.
- offer(Object element): 큐에 요소 추가 (실패 시 예외 발생 안 함).
- poll(): 큐의 첫 번째 요소 제거 및 반환 (비어 있으면 null).
- remove(): 큐의 첫 번째 요소 제거 및 반환 (비어 있으면 예외 발생).
- peek(): 큐의 첫 번째 요소 반환 (제거 안 함, 비어 있으면 null).
- element(): 큐의 첫 번째 요소 반환 (비어 있으면 예외 발생).
- isEmpty(): 큐가 비었는지 확인.
Deque<String> deque = new LinkedList<>();
- addFirst(Object element): 덱의 앞에 요소 추가.
- addLast(Object element): 덱의 끝에 요소 추가.
- offerFirst(Object element): 덱의 앞에 요소 추가 (실패 시 예외 발생 안 함).
- offerLast(Object element): 덱의 끝에 요소 추가 (실패 시 예외 발생 안 함).
- removeFirst(): 덱의 첫 번째 요소 제거 및 반환 (비어 있으면 예외 발생).
- removeLast(): 덱의 마지막 요소 제거 및 반환 (비어 있으면 예외 발생).
- pollFirst(): 덱의 첫 번째 요소 제거 및 반환 (비어 있으면 null).
- pollLast(): 덱의 마지막 요소 제거 및 반환 (비어 있으면 null).
- peekFirst(): 덱의 첫 번째 요소 반환 (제거 안 함, 비어 있으면 null).
- peekLast(): 덱의 마지막 요소 반환 (제거 안 함, 비어 있으면 null).
- isEmpty(): 덱이 비었는지 확인.
HashMap<String, Integer> map = new HashMap<>();
- put(Key, Value): 키와 값을 맵에 추가하거나 수정.
- get(Key): 지정된 키에 대한 값을 반환 (없으면 null).
- remove(Key): 지정된 키와 그에 대한 값을 제거.
- containsKey(Key): 키가 존재하는지 확인.
- containsValue(Value): 값이 존재하는지 확인.
- keySet(): 모든 키를 반환.
- values(): 모든 값을 반환.
- size(): 맵에 있는 키-값 쌍의 개수 반환.
- isEmpty(): 맵이 비었는지 확인.
- clear(): 모든 키-값 쌍 제거.
// 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>();
// 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자)
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());
add() : 우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생
offer() : 우선순위 큐에 원소를 추가. 값 추가 실패 시 false를 반환
poll() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 null 반환
remove() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
isEmpty() : 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생
clear() : 우선순위 큐를 초기화
size() : 우선순위 큐에 포함되어 있는 원소의 수를 반환
백트래킹
public class Main {
static int[][] list;
static boolean[] check;
public static void main(String[] args) throws IOException {
list = new int[][]{{2, 4, 3}, {1, 3, 7}, {6, 5, 6}}; //3X3 행렬
check = new boolean[]{false, false, false}; //조건 판별 체크
backTracking(0,0);
}
static void backTracking(int row, int score) {
if (row == 3) { //재귀함수 마치는 조건
System.out.println(score);
return;
}
for (int i = 0; i < 3; i++) {
if (check[i] == false) {
check[i] = true;
backTracking(row+1, score + list[row][i]); //자식노드 방문
check[i] = false; //자식노드 방문했으면 부모노드 다시 방문기록지움
}
}
}
}
PYTHON
append() O(1) Counter
print(cnt) cnt.element() : 요소 반환
sort() cnt.update()
reverse() cnt.items() : 원소와 그 개수 반환
insert() O(N) cnt = Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
count()
remove() O(N)
key_list = data.keys()
value_list = data.values()
import sys
sys.stdin.readline().rstrip()
sum(result) #iterable 객체가 들어왔을 때 (반복 가능한 객체) 리스트, 사전자료형, 튜플자료형 등
min(7,3,5,2)
max(7,3,5,2)
result = eval( "(3+5) * 7" )
result = sorted([9,1,8,5,4]) # 오름차순 정렬
result = sorted([9,1,5,1,4], reverse=True) # 기존 객체는 변경되지 않으며 return 값이 존재한다.
result.sort() # void 문이다 result가 변경된다.
data = [('홍길동', 35), ('이순신', 17), ('아무개', 88)]
result = sorted(data, key = lambda x : x[1], reverse = True)
print(result)
data.sort(key = lambda x: x[1], reverse = True)
print(data)
data = ["23", "59", "59"]
print(":".join(data))
itertools
permutations (순열)
combinations (조합)
product (중복을 허용하는 순열)
result = list(permutations(data,3)) # 모든 순열 구하기리
result = list(combinations(data,2)) # 2개를 뽑는 모든 조합 구하기
result = list(product(data,repeat = 2)) # 2개를 뽑는 모든 순열 구하기 (중복 허용)
import bisect
bisect_left(literable, value) # 왼쪽 인덱스를 구하기
bisect_right(literable, value) # 오른쪽 인덱스를 구하기
print(math.factorial(5)) # 5 팩토리얼 출력
print(math.sqrt(7)) # 7의 제곱근 출력
print(math.gcd(21,14)) # 21과 14의 최대 공약수 , 7
DFS
import sys
from collections import deque
visited=[]
need_visit=deque()
N,M,R=map(int,sys.stdin.readline().rstrip().split(" "))
visited_dic={i:0 for i in range(1,N+1,1)}
graph={i:[] for i in range(1,N+1,1)}
for i in range(M):
a,b=map(int,sys.stdin.readline().rstrip().split(" "))
graph[a].append(b)
graph[b].append(a)
need_visit.append(R)
number=1
while True:
n=need_visit.pop()
if(visited_dic[n]==0):
visited_dic[n]=number
number+=1
qq=list(graph[n])
qq.sort()
need_visit.extend(qq)
if(not need_visit):break
for i in range(1,N+1,1):
sys.stdout.write(str(visited_dic[i])+"\n")BFS
import sys
from collections import deque
visited=[]
need_visit=deque()
N,M,R=map(int,sys.stdin.readline().rstrip().split(" "))
visited_dic={i:0 for i in range(1,N+1,1)}
graph={i:[] for i in range(1,N+1,1)}
for i in range(M):
a,b=map(int,sys.stdin.readline().rstrip().split(" "))
graph[a].append(b)
graph[b].append(a)
need_visit.append(R)
number=1
while True:
n=need_visit.popleft()
if(visited_dic[n]==0):
visited_dic[n]=number
number+=1
qq=list(graph[n])
qq.sort(reverse=True)
need_visit.extend(qq)
if(not need_visit):break
for i in range(1,N+1,1):
sys.stdout.write(str(visited_dic[i])+"\n")
백트래킹
import sys
def back(n,li):
if(n==M):
answer.append(li)
return
for j in range(1,N+1,1):
if(V[n]<j):
V[n+1]=j
back(n+1,li+[j])
V[n+1]=0
N,M=map(int,sys.stdin.readline().rstrip().split(" "))
V=[0]*(N+1)
answer=[]
back(0,[])
for i in answer:print(*i)누적합
import sys
N,M=map(int,sys.stdin.readline().rstrip().split(" "))
li=list(map(int,sys.stdin.readline().rstrip().split(" ")))
li2=[0]
sm=0
for i in li:
sm+=i
li2.append(sm)
for i in range(M):
a,b=map(int,sys.stdin.readline().rstrip().split(" "))
sys.stdout.write(str(li2[b]-li2[a-1])+"\n")투포인트
import sys
n=int(sys.stdin.readline().rstrip())
li=list(map(int,sys.stdin.readline().rstrip().split(" ")))
correct=int(sys.stdin.readline().rstrip())
li.sort()
left_p=0
right_p=n-1
count=0
while True:
if(li[left_p]+li[right_p]==correct): #같을때
left_p+=1
count+=1
elif(li[left_p]+li[right_p]<correct): #합이 더 작음
left_p+=1
elif(li[left_p]+li[right_p]>correct): #합이 더 큼
right_p-=1
if(left_p>=right_p):break #끝
print(count)힙(우선순위큐)
import heapq
hq=[]
heapq.heappush(hq,1)#minheap형태로 1push
heapq.heappush(hq,2)#minheap형태로 1push
heapq.heappop(hq) #1pop
hq=[]
heapq.heappush(hq,(-1,1))#maxheap형태를 음수를 활용하여 만든다
heapq.heappush(hq,(-2,2))#maxheap형태를 음수를 활용하여 만든다
heapq.heappop(hq)[1] #2pop
그리디
import sys
import heapq
sum=0
hq=[]
for i in range(int(sys.stdin.readline().rstrip())):
heapq.heappush(hq,int(sys.stdin.readline().rstrip()))
sum=0
if(len(hq)==1):print(0)
else:
while hq:
a=heapq.heappop(hq)
b=heapq.heappop(hq)
sum+=(a+b)
heapq.heappush(hq,a+b)
if(len(hq)==1):break
print(sum)동적계획법
def fibonacci(n):
f[1]=f[2]=1
for i in range(3,n+1,1):
f[i]=f[i-1]+f[i-2]
유니온파인드
import sys
sys.setrecursionlimit(1000000)
def getparent(n):
if(dic[n]==n):return n
else:
dic[n]=getparent(dic[n])
return dic[n]
def unionparent(a,b):
n1=getparent(a)
n2=getparent(b)
if(n1>n2):dic[n1]=n2
else:dic[n2]=n1
def findparent(a,b):
if(getparent(a)==getparent(b)):print("YES")
else:print("NO")
N,M=map(int,sys.stdin.readline().rstrip().split(" "))
dic={}
for i in range(N+1):dic[i]=i
for i in range(M):
li=list(map(int,sys.stdin.readline().rstrip().split(" ")))
if(li[0]==0):unionparent(li[1],li[2])
else:findparent(li[1],li[2])
위상정렬
import sys
from collections import deque
dq=deque()
N,M=map(int,sys.stdin.readline().rstrip().split(" "))
entry={i:0 for i in range(1,N+1)}
dic={i:[] for i in range(1,N+1)}
for _ in range(M):
a,b=map(int,sys.stdin.readline().rstrip().split(" "))
dic[b].append(a)
entry[a]+=1
start=[]
for i in range(1,N+1):
if(entry[i]==0):
start.append(i)
dq.extend(start)
answer=deque()
while dq:
n=dq.popleft()
answer.append(n)
for i in dic[n]:
entry[i]-=1
if(entry[i]==0):dq.append(i)
while answer:print(answer.pop(),end=" ")
데이크스트라(최소거리)
import sys
from collections import deque
import heapq
INF = int(1e9)
V,E=map(int,sys.stdin.readline().rstrip().split(" "))
start=int(sys.stdin.readline().rstrip())
hq=[]
#거리
distance=[INF]*(V+1)
#방문,현재 최소길이
visited=[0 for i in range(V+1)] #1~V까지 0은 안써
graph={i:[] for i in range(1,V+1,1)}
for i in range(E):
a,b,c=map(int,sys.stdin.readline().rstrip().split(" "))
graph[a].append((c,b)) #(거리,정점)
heapq.heappush(hq,(0,start))
while hq:
length,now=heapq.heappop(hq) #[0] 거리 [1] 정점
#이미 있는값이 더 짧음
if(distance[now]<length):continue
#지금 온게 더 짧음(선택됨)
for i in graph[now]:
cost=length+i[0]
if(cost<distance[i[1]]):
distance[i[1]]=cost
heapq.heappush(hq,(cost,i[1]))
for i in range(1,V+1,1):
if(i==start):sys.stdout.write("0\n")
elif(i!=start and distance[i]==INF):sys.stdout.write("INF\n")
else:sys.stdout.write(str(distance[i])+"\n")'Computer Science > Algorithm&DataStructure' 카테고리의 다른 글
| [Algorithm] 최장 공통 문자열(Longest Common Subsequence) (0) | 2024.05.01 |
|---|---|
| [Algorithm] 유니온 파인드(Union-Find) (0) | 2024.05.01 |
| [Algorithm] 이진탐색(Binary Search) (0) | 2024.05.01 |
