문제 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 설명 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 정점의 개수가 N, 간선의 개수가 M, 시작하는 정점의 번호가 V이다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점..

백트래킹 이란? 완전 탐색을 하던 도중, 현재의 탐색이 무의미한 경우 되돌아가는 알고리즘을 의미한다. 말 그대로 모든 경우의 수에 대해서 탐색을 하던 도중, 조건과 맞지 않을 경우에 대해서는 탐색을 하지 않고 돌아간다는 뜻이다. 유명한 문제로 N-Queens 문제가 존재한다. 특징 모든 경우의 수를 탐색하지 않기 때문에 완전탐색보다 시간적으로 효율적이다. 탐색 중 조건에 맞지 않는 경우 이전 과정으로 돌아가야 하기 때문에, 재귀를 사용해야 하는 경우가 많다. 조건에 맞지 않는 다면, 이전의 어떤 지점으로 돌아갈 지 정하는 것이 중요하다. 가지치기를 어떻게 구성하느냐에 따라 코드의 효율이 달라진다. 주로 백트래킹을 구현하다 보면, void함수와 전역 변수를 쓰면 쉽게 풀리는데 이는 다른 알고리즘에서 자중하..

병합 정렬(Merge Sort) [의미] 전체 원소를 하나의 단위로 분할한 후 분할한 원소들을 다시 병합하는 정렬 [특징] 분할 단계와 병합 단계로 나뉘어져 있으며, 분할 단계는 시간복잡도에 포함하지 않음. Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬) [Big O] Best - O(nlog₂n) Worst - O(nlog₂n) [장점] 데이터의 분포에 영향을 적게 받음. 크기가 큰 레코드를 정렬할 경우 연결 리스트(Linked List)를 사용한다면, 링크 인덱스만 변경됨으로 데이터의 이동이 엄청나게 적어지고 In-Place정렬로 구현할 수도 있다. [단점] 레코드를 배열(Array)로 구현하면 Not-In-Place 정렬이 되며 추가적인 별도의 메모리를 필요로 하게 된다. [구현] ..

정렬 알고리즘 [의미] 무작위로 섞여있는 데이터를 어떠한 기준에 맞추어 정리하는 알고리즘. [사용하는 경우] 각종 데이터의 목록을 정리하고 싶을 때 분포도의 중위값을 알아내고 싶을 때 데이터에서 중복 값을 파악하고 싶을 때 이진 탐색을 하려고 할 때 [공부하는 이유] 기본적으로 제공되는 시스템 정렬(sort 매서드)이 항상 좋은 퍼포먼스를 보장하지는 않음. 환경과 상황에 걸 맞는 정렬을 사용하는 것이 중요하기 때문. 버블 정렬(Bubble Sort) [의미] 인접한 두 개의 데이터에 크기를 비교한 후 대소관계에 따라 두 값의 교환여부를 판단하는 알고리즘. [특징] N번째 정렬 회차가 끝나면, 뒤에서 n번째 자리의 데이터가 확정됨. Stable한 정렬 (중복된 데이터의 순서가 바뀌지 않는 정렬) [Big ..

[ String 타입만 받는 Stack ] interface Stack { readonly size: number; push(value: string): void; pop(): string; } type StackNode = { readonly value: string; readonly next?: StackNode; } class Stack_Impl implements Stack { private _size: number = 0; private head?: StackNode; constructor(private capacity: number) {} get size() { return this._size; } push(value: string) { if (this.capacity === this.size..