Algorithm Study/이론
[알고리즘] DFS 구현
# V개의 노드, E개의 간선이 주어질 때 V, E = map(int, input().split()) graph = [[] for i in range(V+1)] # 그래프 구성 for e in range(E): u, v = map(int, input().split()) graph[u].append(v)# 단방향일 때 #graph[v].append(u)# 양방향일 때 # 방문 정보를 저장할 공간 visited = [0] * (V+1)# 인덱스 에러(혼동)을 방지하기 위해 V+1만큼 메모리 생성 # DFS 함수 구성 def dfs(v): # 해당 정점을 방문 visited[v] = 1; # print(v, end=" "); # 방문 정보가 궁금할 때 확인 가능 # v의 방문하지 않은 인접 정점을 탐색 for..
[알고리즘] 패턴 매칭 알고리즘 소스코드
- 한번만 찾는 경우 # 패턴이 있을 수 있는 가능한 시작 위치 for i in range(n-m+1): # 패턴의 길이 만큼 비교 for j in range(m): # 일치하지 않으면 다음으로 넘어감 if p[j] != t[i+j]: break else: # 매칭 성공 break - 모든 패턴을 찾을 때 : 방법1 i = 0 while i
[파이썬] 시프트 연산자 이용
※ 일반적으로 시프트 연산자를 이용해 구한 값은 일반적인 수식을 이용해 계산한 값보다 빠르게 처리된다 (기계어) 홀수 / 짝수 판별 if 10 & 1: # 홀수 pass else: # 짝수 pass 10은 이진법에서 1010, 1은 이진법에서 000 & 연산으로 묶여있기 때문에 위 코드는 False가 도출된다 True일 경우 홀수, False일 경우 짝수이므로 결과값은 짝수이다 → 10에 다른 값을 넣어주어서 홀수/짝수 판별에 이용할 수 있다 정수형의 2의 제곱, 2의 제곱근 # 2의 n제곱 print(10n) 10 * 2^n과 같은 연산이 수행된다. 만약 10
[알고리즘] 문자열 패턴 매칭
패턴 매칭에 사용되는 알고리즘 고지식한 패턴 검색 알고리즘(=Brute Force) 카프-라빈 알고리즘 KMP 알고리즘 보이어-무어 알고리즘 고지식한 패턴 검색 (Brute Force) 문자열을 처음부터 끝까지 차례대로 순회, 패턴 내의 문자들을 일일이 비교 텍스트에서 패턴이 존재하는 모든 위치를 찾는 문제 시간복잡도 : O(MN) M: 패턴의 길이, N: 텍스트의 길이 최악의 경우 텍스트의 모든 위치에 대해 패턴을 비교해야 함 패턴 매칭 알고리즘의 중요 포인트 일치하는 경우 ( t[i] == p[j] ) i, j를 증가시켜서 다음 문자를 비교 불일치하는 경우 다음 매칭의 시작위치로 i, j 값을 설정 ※ 자주 사용되는 대치어 텍스트 패턴 기본 t p 인덱스 i j 길이 m n KMP 알고리즘 불일치가 ..
[확률과 통계] 순열과 조합
순열(nPr) 서로 다른 n개 중 r개를 선택하는 경우의 수 순서가 중요할 때 $$ _nP_r = \frac{n!}{(n-r)!} $$ 3명 중 2명을 뽑아 처음 사람에게 밥을 주고, 두 번째 사람에게 음료를 준다. 이때의 경우의 수는? a, b // b, a 는 서로 다른 경우 : 순서가 중요하다 조합(nCr) 서로 다른 n개 중 r개를 선택하는 경우의 수 순서가 중요하지 않을 때 $$ _nC_r = \frac{n!}{(n-r)!r!} $$ 3명 중 2명을 뽑아서 밥을 주려고 할 때, 경우의 수는? a, b // b, a 는 같은 경우 : 순서가 중요하지 않다 같은 것이 있는 순열 같은 것의 개수만큼 팩토리얼로 나눠준다 case 1: aaabb를 나열하는 경우의 수 case 2 : 원순열 case 3 ..
[이코테 자료구조] 5. 이진 탐색
이진 탐색 알고리즘 by 나동빈님 링크 https://www.youtube.com/watch?v=94RC-DsGMLo&t=319s 순차 탐색 : 리스트 안에 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용해서 탐색 범위를 설정 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2 N에 비례 이진 탐색은 탐색 범위를 절반씩 줄이며 시간복잡도는 O(logN)을 보장 소스코드 이진 탐색 : 재귀적 구현 # 이진 탐색 : 재귀적 구현 def binary_search(array, target, start, end): if start>end: r..
[이코테 자료구조] 4. 정렬 알고리즘
정렬 알고리즘 by 나동빈님 링크 https://www.youtube.com/watch?v=KGyK-pNvWos 정렬 : 데이터를 특정한 기준에 따라 순서대로 나열하는 것 문제 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용됨 선택 정렬 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array..
[이코테 자료구조] 3. 스택/큐 자료구조, 재귀함수, DFS & BFS
DFS / BFS by 나동빈님 링크 https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 탐색 : 많은 양의 데이터 중 원하는 데이터를 찾는 과정 DFS, BFS는 탐색 알고리즘에 해당 코딩 테스트에서 자주 등장하는 유형 스택 자료구조 선입후출 : 먼저 들어온 데이터가 나중에 나가는 형식 입구와 출구가 동일한 형태 ex) 박스 쌓기, 플링글스 통 구조 삽입과 삭제로 진행, 시간복잡도 : O(1) stack = [] stack.append(n) stack.pop(n) 최상단 원소부터 출력하려면 stack을 역순으로 출력 큐 자료구조 선입선출 : 먼저 들어온 데이터가 먼저 나가는 형식 입구와 출구..
[이코테 자료구조] 2. 그리디 알고리즘 & 구현
그리디 알고리즘 by 나동빈님 링크 : https://www.youtube.com/watch?v=2zjoKjt97vQ 그리디 알고리즘(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 풀이의 정당성 분석이 중요 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다 많은 코딩 테스트에서 제시되는 문제 유형 중 하나 ※ 예시 문제 : [거스름 돈, 곱하기 혹은 더하기, 모험가 길드] 최적의 해를 빠르기 구하기 위해 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적..
[이코테 자료구조] 6. 다이나믹 프로그래밍
다이나믹 프로그래밍 by 나동빈님 링크 : https://www.youtube.com/watch?v=5Lu34WIx2Us&t=144s 메모리를 적절히 사용해서 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하는 것을 방지 두 가지 방식(탑다운, 바텀업)으로 구성 동적 계획법이라고도 부른다 다이나믹 프로그래밍의 '다이나믹'은 큰 의미 없이 사용된 단어 조건 문제가 다음의 조건을 만족 할 때 사용할 수 있다 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있을 때 중복되는 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 할 때 피보나치 수열의 모든 가능성을 계산하려면 굉장히 많은 연산과정을..