CSE 전공노트

1. 완전 탐색이란? 완전 탐색은 컴퓨터의 계산 능력을 이용하여 가능한 모든 경우의 수를 테스트해봄으로써 답을 찾는 방법을 의미합니다. 예를 들어 친구의 생일을 맞추는 프로그램을 짠다면, 친구의 생일에 대해 아무런 정보가 없다는 가정하에 1월 1일부터 12월 31일까지 모든 날짜가 같은 확률로 생일일 수 있습니다. 이런 문제는 결국 1월 1일부터 12월 31일까지 모든 경우의 수를 테스트해보는 것이 가장 좋다는 것이죠. 무식하게 처음부터 끝까지 모두 테스트해보기 때문에 알고리즘도 이해하기 쉽고, 결괏값을 정확하게 얻어내기도 쉽습니다. 하지만 모든 경우의 수를 탐색하는 완전 탐색의 특성상, 답이 될 수 있는 경우의 수가 너무 많은 경우에는 사용하기 힘듭니다. 특히 코딩 테스트나 백준 문제에서 무턱대고 완전..

코라사주 알고리즘은 SCC(Strongly Connected Component) 문제를 해결하기 위한 알고리즘입니다. SCC란 강한 연결 관계라고 번역될 수 있습니다. 1. 강한 연결 관계? SCC는 그래프에서 노드 간의 연결 관계가 주어질 때, 정점들의 최대 부분 집합으로, 부분 집합에 들어있는 서로 다른 노드 u와 노드 v에 대하여, u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 뜻합니다. 위의 그래프에서 1, 2, 3번 노드는 각각 서로의 노드로 갈 수 있는 노드가 모두 존재합니다. 예를 들어, 1번 노드에서 3번 노드로 가는 경로가 존재하고, 3번 노드에서 1번 노드로 가는 경로도 존재하죠. 하지만 4번과 5번의 경우, 1, 2, 3번 노드로부터 갈 수는 있으나 4 또는 ..

1. 백트래킹(Backtracking) 가장 대표적으로 알고 있는 완전 탐색 알고리즘으로는 DFS를 꼽을 수 있습니다. 하지만 DFS는 정말 완전히 모든 경로를 탐색하므로, 때때로 비효율적일 수 있습니다. 여기서 백트래킹이라는 개념이 등장합니다. 바로 가능성이 있는 부분만 탐색한다는 것입니다. 즉, 어떤 노드를 탐색할 때, 목표로 가는 가능성이 없는 노드라면, 과감하게 배제하고 되돌아갑니다. 이를 가지치기(Pruning)이라고 합니다. 이해를 돕기 위해 예시를 이용해 설명을 더 해보도록 하겠습니다. 백트래킹을 설명할 때 가장 많이 사용하는 예시는 바로 N-Queen입니다. 2. N-Queen N-Queen 문제는 다음과 같이 설명할 수 있습니다. "크기가 N*N인 체스판 위에 퀸 N개를 서로 공격할 수 ..

다익스트라 알고리즘(Dijkstra Algorithms)은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 다른 노드로 가는 최단 경로를 구해주는 알고리즘으로, 각각의 노드들 간의 가중치 (비용) 값이 음수가 아닐 때만 제대로 동작합니다. 다익스트라 알고리즘은 기본적으로 매번 가장 비용이 낮은 간선을 선택하기 때문에 그리디 알고리즘을 따른다고 볼 수 있습니다. 다익스트라 알고리즘은 기본적으로 다음과 같은 단계를 거칩니다. 1. 출발 노드를 설정한다. 2. distance 배열을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 3번과 4번 과정을 반복한다. 위에서도 알 수..

KMP(Knuth-Morris-Pratt) 알고리즘은 두 문자열 s1과 s2가 주어지고, s1가 s2보다 길 때, s1 안에 s2가 포함되어 있는지를 탐색하는 알고리즘입니다. 1. 필요성 가장 기초적으로 브루트 포스를 이용해 s1에 s2가 포함되는 지를 확인하기 위해서는 아래와 같은 단계를 거쳐야 합니다. 2중 반복문을 통해 한 칸씩 옆으로 이동하며 비교를 해야 하기 때문에 시간 복잡도는 O(s1.length * s2.length)가 나오게 됩니다. 이를 개선하기 위해 등장한 알고리즘이 바로 KMP 알고리즘입니다. 위의 사진에서 첫 비교 부분만 분리해서 가져와 보겠습니다. 이미 앞에 세 자리는 같다는 것을 확인했고, 네 번째 자리에서 불일치가 발생했습니다. 그렇다면 '앞에서 이미 연산을 한 세 자리 정보..

다이나믹 프로그래밍(Dynamic Programming)은, 핵심부터 설명하자면, 한 번 수행한 연산을 저장시켜두어, 다음에 해당 연산을 또 해야 할 때 기존의 연산 결과를 이용함으로써, 연산의 중복 수행을 막는 알고리즘입니다. 수행한 연산의 결과를 메모리에 저장시켜 둠으로써, 메모리를 조금 더 사용하긴 하지만 그로 인해 연산 속도를 비약적으로 증가시킬 수 있습니다. 다이나믹 프로그래밍 사용의 가장 대표적인 예시가 바로 피보나치 수열 문제입니다. 피보나치 수열이란, 이전 두 항의 합을 현재의 합으로 사용하는 특징을 가지는 수열입니다. 아래의 예시가 바로 피보나치 수열입니다. 우선 수학적으로 접근하여 재귀함수로 피보나치 함수를 구현하면, 간단하게 구현이 가능합니다. 1 2 3 4 5 6 7 8 9 10 1..

그리디 알고리즘(Greedy Algorithms)은 이름 그대로 번역하면 '탐욕법'이라고 해석됩니다. 이 이름 그대로, 어떤 문제에 대해서 탐욕적으로 문제를 푸는 방법이 바로 이 그리디 알고리즘입니다. 탐욕적이라는 말을 조금 더 듣기 좋게 풀어보자면, '현재 상황에서 최선의 선택을 하는 방법'이라고 할 수 있습니다. 즉, 매 순간 여러 선택지 중 가장 좋아 보이는 선택지를 고르고, 이 선택이 추후에 미칠 영향은 고려하지 않습니다. 추후에 미칠 영향을 고려하지 않는다는 말은, 결과적으로는 최적의 해가 아닐 수도 있다는 것을 뜻합니다. 그래서 항상 어떤 문제와 마주치면, 이 문제를 그리디를 이용해 풀어도 되는 것인지에 대해 생각을 해 보아야 합니다. 하지만 만일 그리디로 접근해도 되는 문제라면, 그리디를 사..