알고리즘
1.[알고리즘] DFS, BFS
의미 그대로 깊이 우선 탐색하는 알고리즘이다.DFS에서는 그래프에서 깊이를 우선적으로 하여 가장 깊은 곳까지 확인하고 다른 루트를 확인한다. 하나의 루트를 정해 막다른 길을 만나면 다른 루트를 찾는 미로찾기라고 생각하면 쉽다.현재 노드에 인접한 노드 중에서 방문하지 않
2.[알고리즘] 이분 탐색
정렬되어있는 배열에서, 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신, 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법이분 탐색은 O(lonN)의 시간복잡도를 가지므로, 선형 탐색에 비해 빠르다는 장점이 있다.정렬된 배열을 기준으로 탐색을 진행한다.st
3.[알고리즘] 그리디
최적해를 구하는 데에 사용되는 근사적인 방법으로, 현재를 기준으로 가장 최적의 상황을 골라가며 해답을 찾는 알고리즘이다.이전의 선택이 이후의 선택에 영향을 주지 않는다.문제에 대한 최적해를 구하는 방법은, 문제를 부분적으로 쪼갰을 때도 그 부분의 최적해를 찾게 해준다.
4.[알고리즘] 그래프
그래프는 모든 것(정점, vertice)에 대한 관계(간선, edge)를 나타내는 자료구조이다.edge의 유형에 따라 유향 그래프, 무향 그래프로 나뉜다.위의 그래프는 edge의 방향이 ORD -> PVD로 명확하다. 이는 유향 그래프이다.아래의 그래프는 edge의 방
5.[자료구조] 우선순위 큐(python)
큐는 데이터를 선입선출(FIFO)로 관리하는 자료구조이다. 파이썬에서 collections 패키지를 이용해 구현할 수 있다.이렇게 구현하면 deque에서 앞에서 나오고 뒤로 들어가는 구조라고 생각할 수 있다.우선순위 큐는 어떤 요소를 제거할 때, 즉 pop할 때 특정한
6.[알고리즘] Red-Black Tree
다음의 조건을 만족시키는 Binary Tree를 Binary Search Tree로 정의한다.각 노드에는 key값이 저장되어 있다.모든 노드에 대해, key값은 left subtree의 모든 key값보다 크다.모든 노드에 대해, key값은 right subtree의 모
7.[알고리즘]Transitive Closure, All-Pairs Shortest Paths
어떤 그래프 G가 있을 때, reachable한 vertex 사이에 직접적인 edge를 추가해 준 그래프를 말한다.예를 들어 그래프 G에 A->B->C path가 존재하면, A는 C까지 reachable하므로 G의 transitive closure G\*에는 A->C
8.[알고리즘] Greedy Algorithms(Prim, Kruskal, Dijkstra)
Optimization Problem 알고리즘 문제는 크게 Decision Problem, Optimization Problem으로 나뉜다. Decision Problem은 문제에 대한 답을 yes / no로 대답할 수 있는 문제이다. 예를 들면, "그래프에서 a->
9.[프로그래머스] lv2. 조이스틱
https://school.programmers.co.kr/learn/courses/30/lessons/42860작년에 알고리즘 고득점 kit를 풀다가 포기한 기억이 있다.이번에도 혼자서는 못풀어서, 다른 사람들의 풀이를 참고했다.우선 정답을 받은 코드는 다음
10.[백준] 23288 주사위 굴리기 2
문제는 다음과 같다.14499번 주사위 굴리기 문제와 유사하다.dir이라는 변수에 방향 정보를 저장한다. 0, 1, 2, 3이 각각 동, 남, 서, 북을 나타낸다.(시계방향 순서)모든 방향에 대해서도 똑같이 구하면, 주사위를 굴리는 roll 함수는 아래와 같이 작성할