본문 바로가기

728x90

python38

[TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS) 1. 다익스트라 알고리즘(Dijkstra algorithm) 모든 간선에 대한 가중치가 항상 0이상임을 가정하고 두 꼭짓점 간의 가장 짧을 경로를 찾는 알고리즘 간선 완화(Edge Relaxation) 시작 정점 s에서 다른 정점 v까지의 초기 거리 값을 부여하고 단계를 거듭하여 개선시키는 것 간선 (u, v)를 완화하는 과정 u를 통해 v까지 가는 지금까지 발견된 최단 경로를 개선할 수 있는지 검사 개선할 수 있다면, v의 최단 경로 추정값을 갱신한다. 시간복잡도 O(|E| + |V|log|V|) https://ko.wikipedia.org/wiki/데이크스트라_알고리즘 1. 다익스트라를 이용한 문제 풀이 1. 1916번 - 최소비용 구하기 import sys import heapq N =.. 2023. 4. 24.

[TIL] 그래프 문제 문제 풀이 1. 그래프 문제 풀이(DFS) 1. 1707번 - 이분 그래프 1. 이분 그래프(bipartite graph)란? 모든 정점을 두가지 색으로 칠하되, 모든 변이 두가지 색의 정점을 포함하도록 하는 그래프 위의 이미지에서 보면 모든 간선이 빨강, 초록 정점을 가지고 있다. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어 있는 그래프 https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html 2. 백준 제출 풀이(DFS - 반복) import sys K = int(sys.stdin.readline()) # dfs 반복문으로 구현 def dfs(g, n) : # n 시작 정점 stack.. 2023. 4. 22.

[TIL] Algorithm - 최소 신장 트리 + 그래프 기본 문제 풀이 1. 그래프 기본 문제 풀이 1. 5639번 - 이진 검색 트리 import sys sys.setrecursionlimit(10**6) nums = [] # 입력이 더이상 들어오지 않을 때 오류 발생 # 오류가 나타나면 while문 종료 while True : try : nums.append(int(sys.stdin.readline())) except : break # nums의 시작 인덱스 = start # nums의 끝 인덱스 = end def post(start, end) : if start == end : # start와 end가 같은 경우 # 한가지 경우만 있으니 출력 print(nums[start]) return root = nums[start] # 현재 루트 노드 mid = start for.. 2023. 4. 21.

[TIL] Graph + 트리 순회 1. 문제 풀이 정리 1. 16120번 - PPAP import sys s = sys.stdin.readline().strip() stack = [] ppap = ["P", "P", "A", "P"] for i in s : stack.append(i) # 현재 스택에 PPAP가 있으면 3번 pop하여 P만 남긴다. if stack[-4:] == ppap : stack.pop() stack.pop() stack.pop() # 최종적으로 P만 남을 경우 if stack == ["P"] : print("PPAP") else : print("NP") 문제에서 조건을 보면 PPAP 는 P로 바꿀 수 있고 P 를 PPAP로 바꿀 수 있다. 즉, 어떤 문자열을 받고 이 문자열이 PPAP 문자열인지 확인하려면 PPAP.. 2023. 4. 20.

[TIL] 스택계산기 + Hashing3 1. 스택을 이용한 계산기 1. 식 표기법 전위 표기법(prefix, 폴란드 표기법) : 연산자를 연산 대상의 앞에 쓰는 연산 표기법 ex) *+234 장점 : 프로그래밍 언어의 인터프리터에 의해 수학적 표현식에 대한 문법으로써 사용되는 경우, 곧바로 추상 문법 트리로 구문 분석되며, 사실 동일하게 전단사 함수를 정의할 수 있다. 단점 : 사람의 눈으로 쉽게 이해하거나 계산하기 힘들다. 중위 표기법(infix) : 연산 대상 사이에 연산자를 쓰는 연산 표기법 ex) (2+3)*4 장점 : 사람에게 친숙하다. 단점 : 우선 순위 규칙에 따라 연산 순서를 결정하여 괄호로 연산이 수행되는 의도된 순서를 가리키는데 필수적이다. 컴퓨터로 구문 분석하기 어렵다. 후위 표기법(postfix) : 연산자를 연산 대상의.. 2023. 4. 19.

[TIL] 분할 정복 연습문제 풀이 + Hashing2 1. 분할 정복 연습문제 1. 10830번 - 행렬 제곱 import sys N, B = map(int, sys.stdin.readline().split()) p = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 두 행렬을 곱하는 함수 def mul (a, b) : result = [[0] * N for _ in range(N)] for r in range(N) : for c in range(N) : for i in range(N) : result[r][c] += a[r][i] * b[i][c] result[r][c] %= 1000 return result # 제곱근을 분할하는 함수 def getResult(p, b) : if b .. 2023. 4. 18.

[TIL] 자료구조 - 우선순위 큐 1. 우선순위 큐(Priority Queue) 우선순위 큐는 추상적인 개념으로 힙이나 다양한 다른 방법을 이용해 구현된다. 각 원소들은 우선순위를 갖고 우선순위 큐에서 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리된다. 즉, 임의의 순서로 삽입되지만, 정해진 순서로 삭제된다. push() : 하나의 원소를 우선순위를 지정하여 추가 pop() : 가장 높은 우선순위를 가진 원소를 큐에서 제거 후 반환 1. 우선순위 큐 구현해보기(최소힙으로 구현) class PriorityQueue : def __init__(self) : # 여기서 사용할 리스트는 완전 이진트리를 구현 # 0번 인덱스를 사용하지 않기 위해 0번에 None 삽입 self.items = [None] def __len__.. 2023. 4. 17.

[TIL] 백준 풀이 정리2 ※ 평일에 풀지 않고 넘긴 문제 풀이 ※ 1. 8983번 - 사냥꾼 import sys # M : 사대 개수 # N : 동물의 수 # L : 사정거리 M, N, L = map(int, sys.stdin.readline().split()) gun = list(map(int, sys.stdin.readline().split())) # 사대의 위치 gun.sort() animal = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 동물들의 위치 def hunt(gun, animal) : count = 0 # 동물의 위치를 반복 for x, y in animal : min_idx, max_idx = 0, len(gun)-1 # 동물을 잡을 .. 2023. 4. 16.

[TIL] 자료구조 - Queue + Hashing이란? 1. 스택 연습 문제 (10000번 - 원 영역) import sys # https://wonyoung2257.tistory.com/79 참고 N = int(sys.stdin.readline()) circles = [] for i in range(N) : x, r = map(int, sys.stdin.readline().split()) circles.append((x-r, '(')) # 중점을 기준으로 왼쪽에 있는 좌표 circles.append((x+r, ')')) # 중점을 기준으로 오른쪽에 있는 좌표 # x좌표 순으로 오름차순 정렬 & 같을 경우 ')' 문자를 가진 값이 앞으로 오도록 # 아스키 코드 : '(' = 72, ')' = 73 circles.sort(key = lambda x: (x[0].. 2023. 4. 15.

[TIL] Algorithm - 분할정복 + 스택 1. 이분 탐색 개념을 이용한 문제 풀이 (11053번 - 가장 긴 증가하는 부분 수열) import sys # A의 크기 N = int(sys.stdin.readline()) # 수열 A = list(map(int, sys.stdin.readline().split())) # https://namu.wiki/w/최장%20증가%20부분%20수열#s-3.2 참고 def LIS() : # d[i] = A[i]를 마지막 값으로 가지는 가장 긴 증가부분 수열 길이 d = [A[0]] for i in range(1, len(A)) : # d에 저장된 가장 마지막 값보다 현재 값이 크면 if d[-1] 0 ~ len(d)-1 사이.. 2023. 4. 14.

[TIL] Algorithm - 이분탐색(Binary Search) + 직접 주소 테이블이란? 1. 이분탐색 또는 이진검색 정렬된 리스트를 계속해서 반으로 나눠 원하는 값의 위치를찾는 알고리즘 Wiki 장점 : 검색이 반복될 때마다 목표값을 찾을 확률이 2배가 되므로 속도가 빠르다. → 시간복잡도 O(logN) 단점 : 정렬된 리스트에서만 사용이 가능하다. 이진 탐색 과정 참고 사이트 https://blog.penjee.com/binary-vs-linear-search-animated-gifs/ Binary Vs Linear Search Through Animated Gifs Average Case Worst Case Binary Search Best Case Binary Search If you're into searching, maybe you're also into sorting! Check.. 2023. 4. 13.

[TIL] 백준 풀이 정리 ※ 시험을 앞두고 Week01주차에 공부했던 알고리즘을 연습한다. ※ 1. 완전 탐색 연습 문제 (14888번 - 연산자 끼워넣기) import sys N = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readline().split())) plus, minus, multiply, divide = map(int, sys.stdin.readline().split()) # sys상 가장 큰수를 저장 resultMax = -sys.maxsize resultMin = sys.maxsize ''' count : 현재 접근하는 nums 인덱스 total : 앞의 연산 결과 plus, minus, multiply, divide : 각 연산이 가지고 있는 개수 .. 2023. 4. 12.

[TIL] 백준 코드 풀이 & Computer System 1. 백준 - 어려웠던 문제 정리 & 풀이 공부 1. N-Queen (9663번) import sys n = int(sys.stdin.readline()) # row 리스트에서 인덱스 = 행번호 / row[i] 값은 열번호 row = [0] * n result = 0 # https://seongonion.tistory.com/103 참고 # https://lighter.tistory.com/m/26 참고 # 퀸을 놓을 수 있는 위치인지 여부 판단 def isPromising(x) : for i in range(x) : ''' 1. 같은 열에 있는지 확인 row[x] == row[i] : x번 행과 i번 행에 놓여있는 퀸의 열 번호가 같은 경우 2. 대각선에 존재하는지 확인 row[x]-row[i] : 세.. 2023. 4. 11.

[TIL] Algorithm - 정렬3 + git 사용법 정리 1. 병합 정렬(merge sort) 배열의 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘 # 병합 정렬 구현 def merge_sort(list) : # 재귀적으로 실행할 함수 def _merge_sort(list, left, right) : if left < right : middle = (left + right) // 2 _merge_sort(list, left, middle) # 배열의 앞부분 정렬 _merge_sort(list, middle+1, right) # 배열의 뒷부분 정렬 ''' 앞에서 이미 정렬된 배열 2개를 병합하기 위한 변수들 p : 현재 buff가 채워져 있는 정도를 저장하는 변수 / 즉, buff[p-1]까지 채워져있다. j : 병합할 .. 2023. 4. 10.

[TIL] Algorithm - 정렬2 1. 시간 복잡도 특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간 Big-O(빅-오) 표기법 : 최악의 경우를 계산하는 방식 Big-O description $$ O\left ( 1 \right ) $$ 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸린다. $$ O\left ( log_{2}n \right ) $$ 입력데이터의 크기가 커질수록 처리시간이 로그만큼 짧아진다. $$ O\left ( n \right ) $$ 입력데이터의 크기에 비례하여 시간이 증가한다. $$ O\left ( n log_{2}n \right ) $$ 데이터가 많아질수록 로그배 배만큼 시간이 증가한다. $$ O\left ( n^{2} \right ) $$ 데이터가 많아질수록 급수적으로 시간이 증가한다. $$ O\left.. 2023. 4. 9.

[TIL] Algorithm - 정렬 ⏰ 2023.04.08 ⏰ 1. Sorting key 를 항목 값의 대소 관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업 데이터를 교환, 선택, 삽입하면서 정렬을 완료한다. ★ 정렬 알고리즘의 안전성 ★ 값이 같은 원소의 순서는 정렬한 후에도 유지되면 안정적인 정렬 알고리즘이다. 안정적인 정렬 알고리즘 버블 정렬, 삽입 정렬, 병합 정렬, 도수 정렬(계수 정렬) 안정적이지 않는 정렬 알고리즘 선택 정렬, 퀵 정렬, 힙 정렬, 2. 버블 정렬(bubble sort) 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘 ( = 단순 교환 정렬 ) 시간복잡도 O(n^2) 1. 기본 구현 # 기본 버블 정렬 def bubble_sort(list) : n = len(list).. 2023. 4. 8.

[Python] Stack과 Queue사용해보기 1. Stack LIFO(Last In First Out) = FILO(First In Last Out) 나중에 들어온 값이 먼저 나가는 자료구조 ★ list를 이용하여 간단하게 스택 사용해보기 ★ # 파이썬에서 스택은 리스트로 구현한다. stack = [] # 스택에 값 추가하기 stack.append(1) stack.append(2) stack.append(3) print("stack에 삽입한 후 : ",stack) # 스택에서 값 제거하기 print("첫번째 pop : ",stack.pop()) print("pop한 후 스택 : ", stack) print("두번째 pop : ",stack.pop()) print("pop한 후 스택 : ", stack) print("세번째 pop : ",stack... 2023. 3. 21.

[Python] 리스트(List) 개념 정리 https://wikidocs.net/book/1 점프 투 파이썬 이 책은 파이썬이란 언어를 처음 접해보는 독자들과 프로그래밍을 한 번도 해 본적이 없는 사람들을 대상으로 한다. 프로그래밍을 할 때 사용되는 전문적인 용어들을 알기 쉽게 풀어서 … wikidocs.net 리스트(List) listName = [요소1, 요소2, 요소3, ...] 리스트를 만들 때는 위에서 보는 것과 같이 대괄호([ ])로 감싸 주고 각 요솟값은 쉼표(,)로 구분해 준다. 또는 list() 함수를 사용하여 생성할 수 있다. # list() 함수를 사용하여 생성 listFunction = list("python") print(listFunction) # 비어있는 리스트 -> emptyList = list() 로 생성가능 emp.. 2023. 3. 20.

이전 1 2 3 다음

728x90

티스토리툴바