CS 지식/자료구조와 알고리즘(Java)

이번 시간에는 백트래킹 알고리즘에 대해서 알아보도록 하겠습니다. 1. 백트래킹이란? 백트래킹(BackTracking)은 해를 찾는 도중 해가 아니라서 막히면, 뒤로 되돌아 가서 다시 해를 찾아 나가는 방법입니다. 또한 다음과 같이 풀어서 설명하기도 합니다. 재귀적으로 문제를 하나씩 풀어가다가 현재 재귀를 통해 확인 중인 노드가 제한 조건에 의해 위배 되고 있지는 않은지 판단하고(이 과정이 유망한지를 판단하는 과정), 그러한 경우에 해당 노드를 제외하고 돌아가서 다음 단계로 나아가는 방식이다. 여기서 중요한 점은 특정 노드는 제외하고 진행을 이어간다는 점입니다. 부르트 포스는 무작정 그냥 모든 방법에 대하여 가능한 해를 나열하는 것이라면 백트래킹은 모든 조합의 수를 살펴보되 단 조건이 만족할 때만 살펴보는..

이번 시간에는 분할 정복 알고리즘(Divide & Conquer Algorithm)에 대해서 알아보도록 할 것입니다. 1. 분할 정복 알고리즘이란? 분할 정복(Divide and Conquer)는 여러 알고리즘의 기본이 되는 핵심 해결 방법으로 다음과 같은 정의를 내리고 있습니다. 문제를 즉각 해결할 수 있을 때까지 재귀적 방식을 통해 두 개 이상의 하위 문제(Sub-problems)들로 나누고(Divide 과정), 문제를 해결한 다음(Conquer 과정) 그 결과를 바탕으로 다시 전체 문제로 돌아가 합치면서 해결해 나가는 과정. 말 그래도 분할했다가 정복하는 알고리즘 인 것입니다. 다음 그림이 그 예시를 보여줍니다. 사실 분할 정복 알고리즘은 굉장히 많이 쓰는 알고리즘으로 이 수업에서도 몇 번 다룬 적..

이번 시간에는 완전 탐색(브루트 포스)에 대해서 배워보도록 할 것입니다. 1. 완전 탐색 알고리즘이란? 한때 유명했던 초등 학교 수학 문제 풀이가 있습니다. 문제가 의도한 대로 푼 풀이는 아니지만 문제가 원하는 답을 얻기 위해서 접근한 과정은 꼭 틀리다 볼 수는 없습니다.(근데 답은 틀렸다. ) 이처럼 완전 탐색은 모든 경우의 수를 전부 다 체크해서 정답을 찾는 방법입니다. 즉, 다시 말해서 무식하게 모든 경우의 수를 하나하나 다 해보겠다는 방법인 것입니다. 이러한 방식이 굉장히 무식하다고 하여 "Brute Force" 라는 이름이 붙여졌고 모든 알고리즘 중에서 가장 단순하고 직관적인 방법이라고 할 수 있습니다. 예를 들어, 금고의 4자리 비밀번호를 풀려고 할 때, 이 알고리즘으로 푸는 방법은 0000부..

이번 시간에는 자료구조 트라이에 대해 알아보도록 하겠습니다. 1. 트라이(Trie)란? 효율적인 문자열 저장 및 탐색이 가능하도록 만든 자료구조 형태 중 하나입니다. 코딩을 하다 보면 수많은 문자열을 저장한 후에 어떤 문자열을 입력 받았을 때, 해당 문자열이 내가 저장한 구조에 포함된 문자열인지의 여부를 알아야 할 때가 있을 것입니다. 이때 사용하는 방식은 다음과 같은 것들이 있습니다. ① 단순 비교 전체 문자열을 맨 앞부터 끝까지 각 문자를 비교 하는 방식 ②이진 탐색(Binary Search) 전체 문자열을 사전 순으로 배열 저장 후, 중간 값과 비교하여 정렬을 진행하는 방식 ③ 트라이(Trie) 이번 시간에 배울 내용 K-진 트리 구조를 통해 문자열을 저장하는 방식 English Dictionary..

이번 시간에는 쉘 정렬(Shell Sort)에 대해서 배워볼 것입니다. 1. 셸 정렬이란? 셸 정렬은 삽입 정렬의 성질을 이용하고 이를 보완한 삽입 정렬의 일반화 버전이라고 볼 수 있습니다. 삽입 정렬의 설명은 이곳을 참조 삽입 정렬의 특징은 다음과 같은 것이 있었습니다. 입력되는 초기 리스트가 거의 정렬되어 있을 경우에만 효율적으로 사용 가능하다. 한 번에 한 요소의 위치만 결정 되기 때문에 비효율적이다. 이러한 삽입 정렬의 장점은 뽑아 먹고 단점은 보완한 것이 셸 정렬입니다. 그래서 셸 정렬은 기존의 삽입 정렬을 수행하기 전에 전체 데이터를 거의 정렬된 상태로 만들면 기존의 삽입 정렬을 그대로 처음부터 사용하는 것보다 더 좋은 성능을 발휘할 수 있다는 점에서 착안된 것입니다. 우선 셸 정렬은 Memo..

이번 시간에는 위상정렬에 대해서 배워 보도록 하겠습니다. 1. 위상 정렬이란? 어떤 일을 하는 순서를 찾는 알고리즘으로 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점(vertex)을 나열하는 것을 말합니다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능합니다. 비순환 방향 그래프(DAG: Directed Acyclic Graph)에서 정점을 선형으로 정렬하는 것(순서대로 출력) 즉, 순서가 있는 task에서 순서를 찾아주는 알고리즘으로 보시면 됩니다. 그래프 방문 결과가 순서대로 출력 되어야 하기 때문에 그래프의 시작 지점과 방향이 존재해야 하고, 그래프에 cycle이 있으면 위상 정렬로 sorting(정렬)하는 것이 불가능합니다. 리스트와 같은 경우 그 자..

이번 시간에는 그리디 알고리즘에 대해서 배워 볼 것입니다. 1. 그리디(탐욕) 알고리즘이란? 단어에서 알 수 있듯이 'Greedy'라는 단어가 '탐욕스러운', '욕심 많은' 이라는 뜻을 내포하고 있습니다. 그래서 말 그래도 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종 답에 도달하는 알고리즘입니다. 최적해를 구하는 데 사용되는 근사적인 방법이며, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각이 드는 것을 선택해 나가는 방식입니다다. 매 선택에서 현재 당장 최적인 값이다. 그렇지만 그리디 알고리즘은 전체에서 최적값을 언제나 구할 수는 없습니다. 다음과 같은 그래프를 봅시다. A에서 출발하여 E에 가야한다고 할 때 경우의 수는 다음과 같습니다. 먼저 B or C or ..

이번 시간에는 그래프 탐색 방법 중 너비 우선 탐색(BFS)에 대해서 배워볼 것입니다. 1. 그래프 탐색이란 하나의 정점으로붙 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 EX) 특정 도시에서 다른 도시로 갈 수 있는 지 없는 지, 전자 회로에서 특정 단자와 단자가 서로 연결 되어 있는 지 그래프는 탐색하는 동안 동일한 정점으로 다시 이동할 수 있는 싸이클이 있을 수 있습니다. 그래서 동일한 정점이 다시 처리되지 않도록 하려면 처리 후 정점을 방문(visited)했다는 표시를 함으로써 중복 방문을 피하도록 하는 것이 그래프 탐색의 핵심입니다. Queue를 이용하여 구현 2. BFS (Breath-First Search, 너비 우선 탐색 ) DFS는 그래프의 개념이 반드시 선행되어야 하기 때문에 ..

이번 시간에는 다익스트라 라는 최단 거리를 알아내는 알고리즘에 대해 배워 보도록 하겠습니다. 1. Dijkstra Algorithm - 다익스트라 알고리즘이란? 그래프에서 최단 경로를 찾아내는 알고리즘은 많이 나와있지만 그 중에서 가장 기본이 되는 알고리즘을 뜻함. 다른 최단 거리 알고리즘은 다익스트라를 기반으로 나온 알고리즘입니다. 다익스트라 알고리즘에 대해 미리 조금 살펴보자면 다음과 같은 것들이 존재합니다. 한 vertex에서 다른 vertex까지의 최단 경로이다. Edge의 가중치(weight)은 양수만 가능(음수 불가능)하다. 가중치에 음수가 있는 경우에는 Bellman-Ford's algorithm(벨만-포드 알고리즘) 혹은 Floyd-Warshall(플로이드-워셜) 알고리즘을 사용한다. 대부..

이번 시간에는 다이나믹 프로그래밍(동적 계획법 ,DP)에 대해서 배워 보도록 하겠습니다. 1. 다이나믹 프로그래밍이란? Dynamic Programming 줄여서 DP(또는 동적 계획법)는 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법입니다. 위의 말을 쉽게 풀자면 아래와 같이 정리할 수 있습니다. 하나의 큰 문제를 여러 개의 작은 문제로 나누어 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두었다가 재활용(기억하며 풀기) 2. 왜 DP를 쓰는 것일까? 사실 일반적인 재귀(Naive Recursion)방식 또한 DP와 매우 유사하다고 볼 수 있는데, 차이점은 일반적인 재귀를 단..