Algorithm
위상정렬 Topology Sort (위상 정렬 백준 문제)
위상 정렬(Topology Sort)은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용한다. -> 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열한다. 이 말을 책에서 보고 이해가 되지 않았다. 예시를 보면 바로 이해할 수 있다. 라면을 끓여 보자. 이 과정을 먹기, 물 끓이기, 스프 넣기, 면 넣기로 나누어 보겠다. 우선 물을 끓여야 면을 넣든 수프를 넣든 하고 그 과정이 일어나야 먹을 수 있다. 이렇게 작업들을 먼저 일어나야 하는 일을 차례대로 정렬해야 한다. 위상 정렬을 보기전에 진입차수라는 개념을 알아야 한다. 진입 차수는 한 노드로 들어오는 간선의 개수이다. 즉 본인을 향하고 있는 화살표의 수를 의미한다. 아래 그림에서 면 넣기의 진입 차수는 2이다. 위의 그래..
크루스칼 알고리즘 (Kruskal Algorithm, 그래프 이론, 서로소 집합 자료구조)
크루스칼 알고리즘(Kruskal Algorithm)은 최소 신장트리 알고리즘이다. 신장트리 신장트리는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프이다. 왼쪽 그래프의 신장 트리들을 찾으면 오른쪽 그래프도 그중 하나이다. 어느 노드에서 시작해도 다른 어떤 노드로 가는 방법이 있는 부분 그래프이다. 사이클이란 아래 그림의 초록색 부분이 사이클이다. 최소 신장 트리 신장 트리는 부분 그래프이기 때문에 여러 개의 경우의 수가 나온다. 최소 신장 트리는 신장 트리들 중 비용이 제일 적게 나오는 신장 트리이다. (간선들에 부여되어있는 거리 같은 비용의 총합이 제일 작은 트리) 그래서 네트워크, 인터넷 망 연결하는 알고리즘 문제에 크루스칼 알고리즘을 사용한다. 서로소 집합 자료..
에라토스테네스의 체(소수 구하기)
https://www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 백준 문제 풀고 다른 사람들 풀이 구경하다가 소수(1과 자기 자신 외에는 나눌 수 없는 수)를 구하는 빠른 방법을 알게 되어서 작성해 본다. (전에 배웠었을 수도 있는데 일단 기억에 없다. 그러므로 정리해 두자.) 내가 사용한 방법 n이 소수인지 판별하는 방법 중 가장 우선 생각할 수 있는 쉬운 방법은 n을 반목문을 사용해 2~(n-1)로 나누어 보는 것이다...
최단 경로 알고리즘 (다익스트라 알고리즘, 플로이드 워셜 알고리즘)
말 그대로 최단 경로를 찾는 알고리즘이다. 길 찾기 문제라고도 불린다 한다. 노드와 간선으로 이루어진 그래프 상황에서 유용하다. 정의는 어려운 것 없으니 바로 본론으로 들어가 보겠다. 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘은 출발 노드를 정하여 시작해서 다른 특정 지점까지의 최단 경로를 찾는 알고리즘이다. 출발 기준 갈 수 있는 노드의 거리를 1차원 리스트에 저장한다. 처음에 리스트의 모든 값은 무한대(INF = int(1e9)로 선언)로 값을 할당한다. 끝났을 때 값이 INF인 인덱스는 시작 노드에서 갈 수 있는 방법이 없는 것이다. 시작 노드 번호의 인덱스는 처음에 0 으로 바꾸고 진행한다. 기본적인 개념은 시작 노드에서 갈 수 있는 노드의 거리를 리스트에 최신화..
Defaultdict, Counter, bisect
Defaultdict from collections import defaultdict counter = defaultdict(int) 기본 dict는 해당 키 값이 있는지 없는지 확인을 해야 한다. ex) if 2 not in dict: dict[2] =0 , 하지만 defaultdict는 위의 코드처럼 생성자를 사용해 매개 변수를 주면 들어오는 값이 존재하지 않으면 알아서 0으로(매개변수에 int를 주었기 때문에) 초기화된다. 아무 값을 저장하지 않고 counter[1]을 출력하면 0이 나온다. 매개변수에 list 등도 줄 수 있다. Counter from collections import Counter counter = Counter(l) l 리스트의 원소들의 수를 카운트해서 딕셔너리로 저장한다. l..
선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬
정렬은 파이썬에서 라이브러리 함수가 존재하므로 간단하게 정리하고 넘어가겠다! 그래도 계수 정렬은 처음 보는 방법이었다. 선택 정렬 주관적인 생각으로 가장 원초적인 방법이다. 왼쪽부터 (맨 앞부터) 가장 작은 숫자를 찾아서 맨 앞으로 위치를 바꾼다. 그다음 방금 바꾼(현재 가장 왼쪽에 있는) 원소 다음부터 가장 작은 숫자를 찾아서 두 번째로 위치를 바꾼다. 마지막까지 반복한다. 느리다. 삽입 정렬 첫 번째 숫자는 정렬이 되어있다 생각하고 두 번째부터 진행한다. 첫 번째보다 작으면 왼쪽으로 크면 그대로 둔다. 그다음 세 번째 숫자를 자신의 왼쪽에 있는 숫자들과 비교하며 적절한 위치에 둔다. 무한 반복. 조금 두리뭉실한 것 같아 예시로 설명하면 ex) 3,2,6,7,4,1 이 있다고 하자 두 번째인 2부터 시..
BFS, DFS (너비 우선 탐색, 깊이 우선 탐색)
구현 관련 알고리즘만 풀다가 드디어 시작했다... 바로 레츠고~ 우선 BFS, DFS는 그래프 형태에서 탐색을 진행하는 방법이다. 노드(node)와 간선(edge)의 구성으로 이루어진 그래프 형태에서 사용한다. 이때 그래프는 2차원 행렬을 사용해서 연결 노드를 표시하거나(list[1][3] = 8 -> 1번 3번 노드는 거리가 8이다. 연결되어있지 않은 노드 사이에는 0, 본인 노드는 list[1][1]은 INF 쓰레기값을 넣는다.) 인접 리스트 방식으로 (graph[0].append((1,7)) -> 0번 노드는 1번 노드와 거리 7이다.) 표현한다. 2차원 행렬은 연결되어 있지 않은 노드들도 표현하며 인접 리스트는 연결이 되어 있는 정보만 갖고 있는다. BFS(너비 우선 탐색) 가까운 노드부터 탐색하..
[Python] 알고리즘을 위한 문법 복습 - map(), filter(), set()
map() - 리스트 내 각 요소들에 동일하게 간단한 연산을 적용할 때 사용. (형변환, 동일한 값 덧, 뺄셈) 주로 람다 함수로 연산을 정의하고 이를 각 요소에 적용하도록 하는 형태가 많이 사용 됨. 이때 람다 함수의 인자 개수는 반드시 1개만 가능하다. a = [1,2,3,4,5] list(map(str,a)) # result >> ['1','2','3','4','5'] lsit(map(lambda x:x+1,a)) # result >> ['2','3','4','5','6'] filter() - 리스트 내 요소들을 특정 기준으로 필터링 할 때 사용. 람다 함수로 filtering 기준 판단 연산을 정의하고 이를 각 요소에 적용하는 형태로 많이 사용. a = [1, 2, 3, 4, 5] list(fil..
[Python] 알고리즘을 위한 문법 복습 - 문자열 & Dictionary & Counter
문자열 ''를 사용하여 선언. 리스트와 동일하게 인덱싱하여 사용 가능. '+' 사용해서 문자열 접합 가능!!! 이거 좀 유용해. 문자열 리스트를 ''.join(list)를 사용해서 문자열로 병합 가능하다. ''안에 문자 사이에 넣을 문자 작성 가능. * 사용하여 반복 가능 내장 메소드 lower(), upper(), swapcase(), capitalize(), title(), islower(), isupper(), count(s), find(s) -없으면 -1 반환, index(s) -없으면 오류, isalnum(), isalpha(), isnumeric(), split(s) - s를 기준으로 문자열을 분리해서 리스트로 반환 Dictionary 인덱스를 key로 대체. d=dict(), d={}로 선언..
[Python] 알고리즘을 위한 문법 복습 - list & enumerate()
list 배열과 비슷한 개념 a=[], a=list() 형식으로 선언. 여러 타입 데이터 동시에 저장. 가능 슬라이싱 가능 ex a[1:3] (start