![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fdw8bdS%2FbtrM6XCkCgD%2Fd0eSAYd6qGqnMBH3LfRkN0%2Fimg.png)
자료구조 : 힙(heap)
2022. 9. 27. 00:10
컴퓨터/알고리즘&자료구조
우선순위 큐를 구현한 완전 이진 트리의 일종 우선순위 큐 스택 - 가장 최근에 입력된 데이터부터 추출 큐 - 가장 먼저 입력된 데이터부터 추출 우선순위 큐 - 가장 우선순위가 높은 데이터부터 추출 우선순위 큐를 힙, 배열, 연결리스트로 구현할 수 있는데, 그중 힙으로 구현한 것이 가장 효율적 우선순위 큐 구현 입력 추출 순서 없는 배열 O(1) O(n) 순서 없는 연결리스트 O(1) O(n) 순서대로 정렬된 배열 O(n) O(1) 순서대로 정렬된 연결리스트 O(n) O(1) 힙 O(log n) O(log n) 특징과 종류 - 여러 값 가운데 최솟값이나 최댓값을 빠르게 찾을 수 있다 - 반정렬 상태(느슨한 정렬 상태) - 중복값 허용 - 계산의 편리를 위해 첫번째 인덱스가 1부터 시작함 - 종류 - 최대 ..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fbt4S2g%2FbtrM37FOuqY%2FU1OKIDYPhLGQG6aYxwL0c0%2Fimg.png)
최단 경로 문제: 다익스트라 알고리즘
2022. 9. 26. 23:40
컴퓨터/알고리즘&자료구조
최단 경로 문제란? 벨만포드 알고리즘을 다룬 여기 문서 참고 다익스트라 알고리즘 - 하나의 시작점에서 도착점으로 가는 최단 경로를 찾는 알고리즘 - 간선이 음의 값을 가져선 안 된다 1. graph, weight, start 가 주어진다 2. start(자기 자신)까지의 거리는 0으로 상정한다 3. 모든 vertex 들을 queue에 넣고 반복한다 - queue에 들어간 v 중에서 가장 작은 값을 찾아 뽑는다 - 뽑힌 v에 대해서 relaxation 수행 예제 현재 Q에서 가장 작은 값을 찾는다 --> $s$ $s$의 인접 노드 중에서 더 작은 $y$ 선택 $y$에서 relaxation 시행, 가장 작은 $z$ 선택 $z$에서 relaxation 시행, Q에서 가장 작은 $t$로 다시 돌아감 $t$에서 ..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FqMTJI%2FbtrM8lWmRBI%2FFHNNUBFz7a5J6LB6HPr8F1%2Fimg.png)
최단 경로 문제: 벨만포드 알고리즘
2022. 9. 26. 18:36
컴퓨터/알고리즘&자료구조
최단 경로 문제란? - 정점 $u$에서 정점 $v$까지의 경로 중에서 경로의 값이 가장 작은 경로를 찾는다 - $\delta (u, v)$ 벨만포드 알고리즘 음수 간선의 값(negative-weight edges) 이렇게 생긴 경로 그래프가 있고, $s$ 에서 $g$로 가는 경로를 구하려고 한다. 총 세 가지 경로를 생각해볼 수 있는데, (1) $ab$ 를 거쳐가는 경로 (2) $cd$ 를 거쳐 가는 경로 (3) $ef$ 를 거쳐 가는 경로다. (1) $ab$ 를 거쳐가는 경로 길이 하나 뿐이므로 경로의 값을 모두 더해서 구하면 된다 -> $3$ (2) $cd$ 를 거쳐 가는 경로 $c$ 와 $d$ 사이가 싸이클 형식으로 되어 있으므로 $cd$ 안에서 싸이클을 돌고 이동할 수 있다 단 이 경로의 경우 싸..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FChpRR%2FbtrMUL30Am1%2FZSkfGFrCYISRJt0SgPTyH1%2Fimg.png)
빅오표기법(Big-O notation)과 시간복잡도
2022. 9. 25. 23:41
컴퓨터/알고리즘&자료구조
빅오표기법과 시간복잡도 정의 - 인수가 특정 값이나 무한으로 향할 때 함수의 극한 행위(limiting behavior)를 표현해주는 수학적 표기 -> 데이터가 늘어날 때 알고리즘 성능이 어떻게 바뀌는가? - 알고리즘의 효율성을 상한선 기준으로 표기해준다 -> "최악의 시나리오" 복잡도 시간복잡도와 공간복잡도 - 시간복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수 ("데이터 원소가 N개일 때 알고리즘에 몇 단계가 필요한가") - 공간복잡도 : 알고리즘이 실행될때 사용하는 메모리의 양 수학적 정의 $n \geq n_{0}$ 인 모든 $n$ 에 대해 $f(n) \leq cg(n)$ 인 양수 $c,\ n_{0}$ 가 존재한다면, $f(n)$ 을 $O(g(n))$ 이라고 나타낼 수 있다 $n$은 $O(n..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FtWF9A%2FbtrMUGoa4hQ%2FXD7PZiSxV7JTk3fnCpL6fK%2Fimg.png)
[백준/약점체크] 1806번: 부분합
2022. 9. 25. 22:27
컴퓨터/코딩테스트
[문제] [내 코드] 먼저 시간 초과 오류가 떴던 코드다 N, S = map(int, input().split()) li = list(map(int, input().split())) def finder(answer): while True: for start in range(N): end = start+answer if sum(li[start:end]) >= S: return answer answer += 1 return 0 print(finder(0)) - answer를 두 인덱스의 간격으로 두고, 슬라이싱하여 합을 구했다 - 시간 초과 오류!! 그 다음, 통과한 코드다 N, S = map(int, input().split()) data = list(map(int, input().split())) sta..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbpjuMR%2FbtrMYTMyezx%2FTduZUfZ4ZFRWHe8tNYhfqk%2Fimg.png)
[백준/약점체크] 1700번: 멀티탭 스케줄링
2022. 9. 24. 23:17
컴퓨터/코딩테스트
[문제] [내 코드] -> 틀렸습니다!! N, K = map(int, input().split()) usage = list(map(int, input().split())) plug = [] res = 0 for i in range(K): if usage[i] in plug: continue elif len(plug) < N: plug.append(usage[i]) else: wait = [] for j in usage[i:]: if j in plug: wait.append(j) if len(wait) == N: break if set(plug) - set(wait): obj = (set(plug) - set(wait)).pop() else: obj = wait[-1] plug[plug.index(obj)..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcU4dKQ%2FbtrMUgitqzO%2FIHdHFSCU3W8MQoByD2N0q1%2Fimg.png)
[백준/약점체크] 1062번: 가르침
2022. 9. 24. 21:55
컴퓨터/코딩테스트
[문제] [내 코드] N, K = map(int, input().split()) words = [input() for _ in range(N)] basics = ['t', 'i', 'c', 'a', 'n'] if K < len(basics): print(0) elif K == 26: print(len(words)) else: result = 0 unlearned = list(set([w for word in words for w in word if w not in basics])) # unlearned 중에서 r개를 새로 배운다 n = len(unlearned) r = K - len(basics) def dfs(idx, ls): global result if len(ls) == r: tmp = 0 lea..
![thumbnail](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcdRMV0%2FbtrMozPg7SS%2FvKEXi9wHxP4Cp9PQpg5Ii0%2Fimg.png)
[백준/약점체크] 14719번: 빗물
2022. 9. 18. 19:22
컴퓨터/코딩테스트
[문제] [내 코드] H, W = map(int, input().split()) blocks = list(map(int, input().split())) result = 0 for i in range(1, H+1): level = [] for j in range(len(blocks)): if i > blocks[j]: level.append(0) else: level.append(1) for l in range(len(level)): before = sum(level[:l]) after = sum(level[l:]) if (before>0) and (after>0) and (level[l] == 0) : result+=1 print(result) - 굉장히 어거지로 풀었다.. 층마다 0과 1로 블럭을 쌓..