DevKim

[ 재귀 ] -> 귀납적 사고가 가능한가? * 절차적 사고를 버리고 귀납적으로 접근하는 것이 중요* 01. 함수정의 - 함수가 어떤 역할을 수행해야하는지/어떤 인자를 받아야하는지 02. base condition - 종료조건 03. 재귀식 - 말로 풀어쓰고, n에 대한 식으로 작성 [다이나믹 프로그래밍 DP] -> 이거 완전탐색인데? 근데 경우의 수가 너무 크다! -> 메모이제이션 가능한가? 겹치는 부분 문제를 해결할 수 있는가? -> 매 순간 최선의 선택을 해야하는가? * 상태값을 정하는 것이 핵심* [ 연습문제 ] (1) 피보나치 수열 [조건 충족] 1. 귀납적으로 사고가능? 1,2,3,4,5...N => N일때 fibo(N)=fibo(N-1)+fibo(N-2) 2. 겹치는 부분 문제? => yes ..

01. 문제 풀이 단계 - 문제 이해, 조건씩 꼼꼼하게 체크 (반례 케이스 고려) - 어떤 알고리즘, 자료구조를 사용해야 할지 체크 - 스스로 로직 먼저 만들어보기 - 작성한 로직 코드로 옮기기 - 시간 초과 발생시, 시간복잡도와 N의 범위 체크 [ 참고 ] https://yeon-woo-kim.tistory.com/102?category=1170787 시간 제한과 시간 복잡도 wiki.python.org/moin/TimeComplexity TimeComplexity - Python Wiki This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Pytho...

1. 백트랙킹 과 DFS - DFS는 무한히 깊은 곳을 찾아야할 때 효과적이다. 하지만 DFS는 모든 곳을 방문하기 때문에, 굳이 목표지점이 있지 않는 경로로 빠져서 비효율적인 결과를 초래할 수 있다 - 이렇게 비효율적인 경로를 차단하고 목표지점에 도달할 수 있는 가능성이 있는 루트를 검사하는 방법이 백트랙킹 => DFS에 pruning을 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법 [ 4가지의 절차 ] 1. DFS 수행 - DFS를 수행하여 노드를 찾는다 2. 유망한 노드 검토 - 유망한 노드이면 서브트리로 이동. 그렇지 않으면 백트랙킹 3. 서브트리 이동 - 방문한 노드의 하위로 이동하여 다시 DFS 수행 4. 백트랙킹 수행 - 방문한 노드로 가지치기하고, 상위 노드로 백트랙킹 한..

[1] Union-find [ 개념 ] - 서로소 집합을 찾는 것 = 공통 원소가 없는 두 집합을 의미함 - Union = 합집합 - Find = 찾기 [ 과정 ] 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인한다 A와 B의 루트 노드 A',B'를 각각 찾는다 A'을 B'의 부모 노드로 설정한다 반복 [ 최적화 ] - find 함수를 최적화하기 위해, 경로 압축을 이용한다 - find 함수를 재귀적으로 호출한 뒤에, 부모 테이블 값을 바로 갱신 [ 응용 ] - "무방향" 그래프 내에서의 사이클 판별시 - 두 노드의 루트 노드가 서로 같다면 cycle(사이클)이 발생한 것임 [ 코드 ] def find_parent(parent,x): if parent[x]!=x: parent[x..

- '하나'의 정점에서 다른 모든 정점으로 가는 최단 경로 [ 조건 ] - 음의 간선이 존재하지 않음 [ 기존의 선형탐색 방법의 다익스트라 ] - O(n^2) 의 시간 복잡도를 가짐 - 문제점은 노드의 개수가 10,000개가 넘어가는 문제라면 시간초과 가능성이 높음 [ 우선순위 큐를 이용한 다익스트라 ] - 힙을 이용하여 구현 - python 에선 heapq 라이브러리로 구현되어있음 - O(NongN) 의 시간복잡도 [ 과정 ] 최단거리 테이블을 초기화(자기 자신은 0, 직접 연결되어있지 않는건 무한대로 초기화) 처음엔 가장 가중치가 작은 값을 선택함 하나의 노드를 선택하고 해당 노드를 거쳐서 가는 경우를 모두 고려하여 가장 최소인 값으로 업데이트 (이때, 값이 새로 갱신된 경..

[1] 합병 정렬 merge sort *서로 떨어져있는 원소를 교환하는 것이 아니므로, 안정적임 *merge : 정렬을 마친 두 배열을 비교하여 합침 O(n) *전체 시간 복잡도 = O(n log n) (1) sorted 함수 사용하기 -> 정렬을 마친 상태가 아니더라도 적용가능하지만, 빠르지 않음 c=list(sorted(a+b)) (2) heapq 모듈의 merge() 함수 사용하기 ->속도가 빠름 c=list(heapq.merge(a,b)) [2] 퀵 정렬 quick sort 퀵 정렬은 가장 잘 알려진 빠른 정렬 알고리즘이다. pivot을 이용하여 분할 정복 해나가는 알고리즘으로, pivot을 어떤 식으로 정할지가 성능에 크게 영향을 미친다. 평균 시간 복잡도는 O(NlogN) 이며, 만약 매번 1..

1> 단순 선택 정렬 O(n^2) : 말그대로 가장 작은 애 부터 선택해서 순서에 맞는 위치로 옮기며 작업 반복 def select_sort(List): n=len(List) for i in range(n-1 ): min=i for j in range(i,n): if List[min] > List[j]: min=j List[i],List[min]=List[min],List[i] return List List=list(map(int,input().split())) print(*select_sort(List)) 2> 단순 삽입 정렬 O(n^2) : 노드를 하나씩 선택해서 알맞은 위치에 삽입함 def insert_sort(List): k=0 n=len(List) for i in range(1,n): k=i f..

버블정렬은 단순 교환 정렬이다. 1. 일반적인 버블정렬 2. 교환이 한번도 일어나지 않은 경우 stop하는 개선 1 3. 교환이 일어나지 않는 부분을 마지막 지점으로 두는 개선 2 이렇게 3가지로 정리해봤다. 셰이커 정렬(양방향 버블정렬)은 이런경우에 이렇게 사용되는 알고리즘이다. 9 1 3 4 6 7 8 처럼 정렬이 거의 완료되었지만 9가 맨앞에 있으므로 버블 정렬로는 오래걸림 홀수 패스에서는 가장 작은 원소를 맨 앞으로 (뒤에서 앞으로 확인 후 정렬) , 짝수 패스에서는 가장 큰 원소를 맨 뒤로 이동 (앞에서 뒤로 확인 후 정렬) 오름차순임 import time def bubble_sort(List): n=len(List) cnt=0 for i in range(n-1): for j in range(n..