00/algorithm (55) 썸네일형 리스트형 우선순위 큐 (priority queue), 힙 정렬 (heap sort) 우선순위 큐 (priority queue)- 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나가게 된다.- 배열, 연결 리스트 등의 여러 가지 방법으로 구현이 가능한데, 가장 효율적인 구조는 heap이다. 배열을 사용하는 방법 1. 정렬이 안 되어 있는 배열의 경우삽입 시간 복잡도 \(O(1)\)삭제 시간 복잡도 \(O(n)\) 2. 정렬이 되어 있는 배열의 경우삽입 시간 복잡도 \(O(n)\)삭제 시간 복잡도 \(O(1)\) 연결 리스트를 사용하는 방법 1. 정렬이 안된 리스트- 삽입 시에 첫번째 노드로 삽입시키는 것이 유리하다. 다른 노드를 이동할 필요가 없다. 포인터만 변경하면 된다. 삽입 시간 복잡도 \(O(1)\)- 삭제 시에 포인터를 따라서 모든 노드를 뒤져보아야 한다. 삭제.. 정렬 알고리즘 (sorting algorithm) 정리 순차탐색(sequential search)- 시간복잡도 : O(n)- 데이터가 정렬되어 있지 않아도 사용할 수 있다. 이진탐색(binary search)- 시간복잡도 : O(logn)- 데이터가 순서에 맞게 정렬되어 있어야 한다. 알고리즘 Best Average Worst Stable Memory 버블 정렬 (n^2) (n^2) (n^2) True 선택 정렬 (n^2) (n^2) (n^2) False 삽입 정렬 (n) (n^2) (n^2) True 셸 정렬 (nlog_2n) (n^{1.5}) (n^2\) False 퀵 정렬 (nlog_2n) (nlog_2n) (n^2\) False 히프 정렬 (nlog_2n) (nlog_2n) (nlog_2n) False 합병정렬 (nlog_2n) (nlog_2n) (n.. 백준 1918번 후위표기식 (Python) 문제 https://www.acmicpc.net/problem/1918 풀이 스택의 가장 위에있는 요소보다 우선순위가 낮은 연산자가 들어오면 스택을 비운다. 괄호를 만나면 괄호를 닫을 수 있을 때까지 스택을 비운다.어제 푼 문제인데 오늘 그래픽스 수업에서 교수님이 말하셔서 놀랬다.. 역시 자료구조가 기본이다~ 1234567891011121314151617181920212223242526272829303132333435363738394041424344def priority(x) : if x == "*" or x == "/" : return 2 elif x == "+" or x == "-" : return 1 elif x == "(" or x == ")" : return 0 return -1 def solv.. 백준 5052번 전화번호 목록 (Python) 문제https://www.acmicpc.net/problem/5052 풀이시간초과 주의!input() 쓰지말자. 123456789101112131415161718192021222324252627import sysinput = sys.stdin.readline def solve(contacts) : contacts.sort() st = contacts[0] for contact in contacts[1:] : if st in contact : return "NO" else : st = contact return "YES" for i in range(int(input())) : n = int(input()) contacts = [] for j in range(n) : contacts.append(input(.. 백준 7576번 토마토 (Python) 문제 인접한 곳에 놓여있는 토마토는 하루가 지나면 익는다. 이 때 모든 토마토가 익는데 몇일이나 소요되는가?모든 토마토가 익을 수 없으면 -1을 출력한다.(0: 안 익은 토마토, 1: 익은 토마토, -1: 없음.) 풀이 간단히 bfs로 풀면된다.python list에서 .pop(0) 실행시 첫번째 요소를 제거하고 두번째 요소를 첫번째로, 세번째 요소를 두번째로... 이동하는 작업을 하기때문에 시간이 O(N)만큼 소요된다고한다. collections 라이브러리의 queue 모듈을 사용하자. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455import sysimport coll.. Kickstart Round A 2018 Problem A 문제Supervin 이 특별한 계산기를 가지고 있다. 현재 N이 계산기에 표시되어있다. Supervin은 홀수를 싫어한단다. 계산기를 +,- 버튼만을 눌러서 짝수 번호만 표시되게 하려면 최소 몇번을 눌러야하는가? 풀이일단 나는 재귀함수로 구현을 했다. 홀수인 수의 자릿수를 찾고나서 그 다음 자릿수들의 값을 (1) 더해서 자릿수를 바꾸거나 (2) 빼서 자릿수를 바꾸고 그 결과값을 비교한 후 더 작은 값을 반환하는 방식으로 풀었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950T = int(input())max_n = 10**16 def findOddNumber(n, cnt, t): eo =.. 백준 2644번 촌수계산 (Python) 간단하게 BFS를 이용해서 풀면 되는 문제. 12345678910111213141516171819202122232425262728n = int(input())a, b = map(int, input().split())m = int(input()) arr = list([0]*(n) for i in range(n))v = list([0]*(n)) def bfs(x) : que = [x] while que : cur = que.pop(0) for i in range(n) : if arr[cur][i] == 1 and v[i] == 0 : v[i] = v[cur] + 1 que.append(i) for i in range(m) : x, y = map(int, input().split()) arr[x-1][y-1].. 백준 3273번 두수의 합 (Python) 문제n개의 서로 다른 양의 정수들로 이루어진 수열이 있다. ai + aj= x (1 ≤ i x : j -= 1 else : i +=.. 이전 1 ··· 3 4 5 6 7 다음
