알고리즘 개념 정리

큐(Queue)는 선입선출의 자료구조이다. (선입후출은 스택(Stack))우선순위 큐(Priority Queue)는 말 그대로 우선순위가 높은 자료가 먼저 나가는 큐를 말하는 것이다.파이썬에서는 우선순위 큐를 구현하기 위해 일반적으로 힙큐(heapq)를 사용한다.힙은

이진탐색(binary search)은 '오름차순'으로 정렬된 리스트에서 사용할 수 있는 탐색법이다.그림처럼 절반씩 줄여가면서 절반의 값과 탐색해야할 값을 비교해가면서 탐색하는 방식이다.이진탐색은 최대 O(log N) 의 시간복잡도를 가졌다.기본적인 형태는 아래와 같다

https://www.acmicpc.net/problem/5582이 문제처럼 두 문자열에서 공통 부분 문자열을 구하는 문제들이 있다.이러한 종류의 알고리즘 문제는 이차원 그래프로 DP를 적용시키면 쉽게 해결할 수 있다.KABDE와 ABDXY의 공통 부분 문자열

defaultdict 는 딕셔너리를 만드는 서브클래스이다.딕셔너리의 기본값 타입을 미리 지정할 수 있다. (int, list, set 등등)기본값을 list로 지정한 예시defaultdict 가 유용한 이유는 예를 들어서 리스트 내부의 알파벳의 갯수를 센다고 할때 딕셔

투포인터는 배열에서 원하는 값을 찾는 알고리즘이다.물론 단순히 반복문을 중첩하여 값을 찾을 수 있지만 메모리와 시간효율을 위해 투포인터를 사용한다.투포인터는 크게 두가지 방식으로 사용된다.양쪽에서 가운데로 좁혀지는 방식한쪽에서 두 점 모두 출발하는 방식배열 S에서 두

누적합은 1차원이나 2차원 배열을 주고 일정한 범위에 속한 원소의 합을 구하는 개념이다.반복문으로 풀었을때의 시간복잡도를 줄여줄 수 있다.https://www.acmicpc.net/problem/116591차원 배열에서의 누적합, 부분합은 간단하다.배열을 반복

파이썬 알고리즘 문제에서 깊은복사, 얕은 복사는 막 입문한 사람들을 헷갈리게 하는 개념이다.얕은 복사는 주소값을 복사하는 것이고깊은 복사는 그 값을 가져오는 것이다.B라는 변수를 = 을 활용하여 A를 복사했다.그런데 B의 값을 바꾸면 A도 바뀐다.B가 A의 주소값을 가

LCA 알고리즘은 트리에서 최소 공통 조상을 찾는 알고리즘이다.공통 조상을 찾기위해서는 트리의 깊이를 이용한다.루트 노드에서 dfs로 순회하며 전체의 부모노드와 깊이를 구한다.최소 공통 조상을 두 노드를 입력받는다.3-1. 만약 두 노드의 깊이가 다르다면, 깊이가 깊은

super() 함수는 쉽게 말해서 자식 클래스에서 부모 클래스의 요소를 사용하고 싶을때 사용하는 함수이다.예를 들어서 이런 클래스들이 있다고 하자.juice는 drink를 상속받는 자식클래스이다.juice 에서 test를 정의할때, super().taste() 라는 것

알고리즘 개념은 아니지만 가끔 코드의 실행 속도를 조절할 필요가 있는데 이럴때 쓸 수 있는 패키지가 바로 time 이다.본래 pip 패키지였지만 파이썬이 3버전으로 오면서 내장되어 따로 설치할 필요는 없다.속도를 조절할 구간에time.sleep(sec) 를 입력해주면

정렬 알고리즘을 간단하게 정리한다.버블 정렬 : 앞에서부터 인접한 두 수를 비교해가면서 큰 수를 뒤로 보내며 정렬하는 방식선택 정렬 : 앞에서부터 가장 작은 수와 위치를 바꿔가며 정렬하는 방식삽입 정렬 : 정렬 범위를 1칸씩 늘려가면서 새로운 정렬 대상을 기존 값과 비