코딩테스트/알고리즘

1. Stack이란?스택은 '쌓는다'라는 이름의 어원처럼 먼저 입력한 데이터를 제일 나중에 꺼내는 FILO(Last In, First Out)의 구조를 가진 자료구조를 의미합니다. 일상 생활에서도 많이 확인할 수도 있는 형태인데, 차례대로 쌓인 접시라던지 혹은 곽티슈에 담긴 휴지라던지 확인할 수 있습니다. 혹은 프로그램 내부에서도 이런 구조를 확인할 수 있는데 함수를 호출하게 되면 프로그램을 호출된 순서에 따라서 차곡차곡 저장하고, 함수가 종료될때마다 가장 나중에 호출된 함수부터 차례대로 해제됩니다.위 구조로 잘 이해가 가지 않는다면 아래와 같은 그림을 이해하면 더 쉽게 이해할 수 있습니다.. 예를 들어 어떤 데이터를 1, 2, 3 순서대로 넣었다면 가장 나중에 넣었던 3부터 차례대로 2, 1 순서로 꺼..

1. DP란? 동적 계획법은 간단히 말하면 전체 문제 혹은 큰 문제를 한 번에 해결하는 것이 아니라 작은 부분 문제들로 나눠서 해결하고 이것들을 활용해 전체 문제를 해결하는 방법이다. 말만 들어보면 다른 알고리즘인 분할정복과 유사하게 보인다. 다만 DP를 효율적으로 사용하기 위해서는 2가지 조건을 만족해야한다. 큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장해야 한다.(중복 부분 문제) 큰 문제의 해결책은 작은 문제의 해결책의 합으로 구성할 수 있어야 한다.(최적 부분 구조) 분할정복과 DP 모두 부분 문제로 나눠서 해결한 뒤 원래 문제의 해답을 얻지만, 분할정복은 반복되는 작은 문제가 없다. 반면에 위에서 살펴본 것처럼 DP는 반복되는 작은 문제가 있을 때 사용하는 알고리즘이다. ..

1. 탐욕(Greedy) 이란? 그리디 알고리즘은 문제 해결 과정에서 결정하는 순간마다 눈 앞에 보이는 최선의 선택을 하는 알고리즘을 뜻한다. 즉 해결 과정 전체, 혹은 미래의 상황을 고려하지 않고 당장의 순간에 최선의 선택을 고려하는 알고리즘이다. 다른 알고리즘에 비해 구현하기가 쉬움 실행 속도가 빠름 특정한 상황에서만 적용 가능. 그리디는 위에서 설명했듯이 모든 순간에 적용 가능한 알고리즘은 아니다. 그리디 알고리즘을 사용할 수 있는 특정한 상황은 다음과 같다. 최적 부분 구조 : 순간마다의 부분 최적해들의 합이 곧 전체 문제의 해답과 동일할 때만 사용 가능. 그리디 선택 속성 : 이전의 선택이 이후의 선택에 영향을 끼치지 않음. 2. 대표 예시 그리디의 대표적인 예시는 거스름돈 문제다. 다음 설명을..

1. 그래프란? 그래프는 '노드 (Node) 와 각각의 노드를 연결하는 간선(Edge)'으로 구성된 자료구조이다. 쉽게 설명하면 각각의 객체들과 그것을 잇는 선들의 집합이라고 생각하면 된다. 실생활에서 우리가 대표적으로 보는 그래프 형태의 이미지는 지하철 노선도를 떠올릴 수 있다. 각각의 역과 역을 잇는 선들의 집합으로 그래프의 형태를 이루고 있다고 이해하면 알기 쉽다. 그래프는 또한 다음과 같은 다양한 특성을 지닌다. 노드(Node)는 다른 이름으로 정점(Vertex)라고도 불린다. 연결 방향에 따라서 양방향, 단방향, 무방향이 될 수 있다. 넓은 범위에서는 트리 역시 그래프의 일종이다. 인접 : 두 개의 노드가 간선으로 직접 연결되어 있는 상태를 말한다. 가중치 : 간선에 따라 할당된 값 또는 비용을..