코딩테스트 - 이론

자료구조 중에서 Stack과 Queue, Deque이 있다. 이 세가지는 얼핏 비슷한 듯 보이면서도 엄연히 서로 다른 자료구조로, 주로 사용되는 분야나 문제도 다르다. Stack : 스택 Stack이란, '쌓아 올린다'는 의미가 있다. 즉, 스택은 책을 쌓는 것처럼

순열과 조합은 확률과 통계에서 경우의 수를 공부할 때 배운 것 같다. 내가 이거를 코테를 준비하면서 다시 배울줄이야.. 순열 = Permutations 리스트 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 경우를 순열이라 한다. 즉, 조합의 중복

자주 사용되는 탐색 알고리즘에 하나로 깊이 우선 탐색, 너비 우선 탐색이 있다. 코딩 테스트 준비를 하면서 꼭 알아야 할 알고리즘이라고 생각되는데 이름과 쓰임이 헷갈린다 흔히 깊이 우선 탐색은 BFS, 너비 우선 탐색은 DFS로 불린다. 이 두가지를 알기 위해서는 스택

동적 프로그래밍(Dynamic Programming = DP)은 동적계획법이라고도 한다. DP는 DFS / BFS 못지 않게 많이 사용되는 알고리즘인 것 같다. 코딩 테스트를 대비하면서 문제를 풀고 있는데 DP를 응용해서 푸는 문제도 종종 봤다. 물론 DP가 아니더라도

사실 재귀함수에 대해서는 코딩테스트 대비 - DFS / BFS에서 살짝 다룬 적이 있다. 하지만 재귀함수만 따로 코드로 구현하지는 않았기에 이번 글에서 다시 설명하고 코드로 구현하고 설명해보려 한다. 재귀함수는 반복적인 것을 해결할 때 좋은 방식이다. '재귀적이다'라

코딩테스트를 준비하다보니 정렬을 정리하면 좋을 것 같다는 생각을 했다. 정렬 정렬이란, 데이터를 특정 기준에 맞춰서 나열하는 것을 말한다. 사실 코딩테스트 문제에서는 정렬되어 있는 경우가 많다. 하지만, 그렇지 않은 경우도 있고 기존에 정렬되어 있는 데이터를 새로운

그래프란, 자료구조의 하나로 정점(vertex 혹은 node)와 간선(edge)로 이루어져 있다. 그래프 관련 용어 |용어|뜻| |:-:|:-:| |정점| 데이터를 저장하는 위치 | |간선| 정점을 연결하는 선 | |인접 정점| 간선으로 연결되어있는 정점 | |단순

백트래킹(BackTracking)은 문제를 해결하기 위해 모든 해결책(모든 가능성)을 시도하는 것이 아니라, 해결책에 대한 후보군을 구성해서 해당 후보군이 문제의 조건을 만족하는지 여부를 확인해가며 해답을 찾는 알고리즘이다. 즉, 해를 찾는 도중에 해가 아니라면 이전

최단 경로와 관련된 문제를 풀어보다가 bfs만으로는 해결이 안되는 문제가 있었다. 인터넷을 찾아보니 bfs가 아닌 다익스트라 알고리즘 혹은 플로이드 워셜 알고리즘으로 푼 사람들이 많았다. 이 둘다 모르는 나에게는 애시당초 풀 수 없는 문제였다. 그래서 다익스트라와 플로

다익스트라 알고리즘에서도 언급했듯이 플로이드 워셜은 음수를 갖는 간선에서도 최단거리를 구할 수 있는 알고리즘이라고 한다. 플로이드 워셜 다익스트라 알고리즘은 특정 노드에서 시작해서 다른 노드까지의 최단경로를 구하는 알고리즘이다. 하지만 플로이드 워셜은 모든 정점으로부

이번에는 자료구조 중에서 heap에 대해서 글을 써보려 한다. 그리고 heapq라는 python 라이브러리(모듈)에 대해서도 조금 써보려 한다. 사실 나는 heap이라는 것을 사용해본 경험이 아예 없다 공부를 좀 해보니 트리에 대해서도 설명해주면 좋을 것 같아서 트리와

그리드 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 가장 좋은 것(현재 고를 수 있는 선택 중에서 가장 최적인 것)을 골라 최종 해답에 도달하는 것을 의미한다. 즉, 현재의 선택이 나중 선택에 미칠 영향을 고려하지 않는 것이다. 따라서, 일반적인 상황에서 그리드 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서는 대부분의 탐욕법 문...

이진 탐색은 탐색 알고리즘 중에 하나이다. 분명히 프로그래밍 수업할 때 배운 것 같은 기분이 든다... 데이터에서 탐색 범위를 줄여나가면서 원하는 데이터를 탐색하는 알고리즘이라고 한다. 이때 중요한 것은 찾고자 하는 데이터가 정렬되어 있어야 한다는 점이다. 즉, 정렬된

Counter는 collections 모듈(라이브러리) 안에 존재하는 클래스다. collections 모듈은 기본 제공하는 모듈로 별도의 다운로드 없이 바로 사용 가능하다. Counter는 이름에서도 알수있듯이 데이터나 항목을 세는 기능을 제공한다. 리스트나 문자열에서 각 원소(요소)의 갯수를 세는 작업을 한다. 딕셔너리와 동일한 형태이다. 출력 위에 ...