DevKim

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] 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..

오픈 주소법은 충돌이 발생했을때 재해시 (rehashing) 를 통하여 빈 버킷을 찾아나서는 방법이다. 오픈 주소법은 빈 버킷이 나올때까지 해싱을 반복하기 때문에 선형 탐사법이라고 불리기도한다.. 암튼 주의해야할 점은 버킷에 따로 속성을 부여해줘야한다.! 1. 이 버킷이 데이터가 저장되어있는지 2. 이 버킷이 비어있는지 3. 원래는 뭔가 있었는데, 삭제 명령으로 삭제된 버킷인지 이렇게 총 3가지의 속성을 부여해줘야한다. *재해시 함수를 +1 한 후에 기존의 해시법을 적용하는 방법으로 가정하고 코드를 작성했다. from enum import Enum import hashlib #버킷의 속성지정 class status(Enum): OCCUPIED=0 #데이터가 저장되어있음 EMPTY=1 #버켓이 비어있음 D..

해시법 중에 충돌 대처하는 방법 중 하나인 체인법을 이용하여 구현해보았다. 체인법은 간단하게 해시값이 같은 원소를 연결리스트로 관리하는 방법이다. >> hashlib.sha256(str(key).encode()).hexdigest(),16 이 코드는 처음 알게된 부분이라 따로 etc 카테고리에 issue를 정리할 예정. import hashlib #노드 생성 class Node: #초기화 def __init__(self,key,value,next_v): self.key=key self.value=value self.next=next_v class chaining: def __init__(self,size): self.size=size #테이블의 사이즈 self.table=[None]*self.size #..