알고리즘/알고리즘5 다익스트라 Djikstra 최단경로 알고리즘 (C++코드, Java코드) 다익스트라 알고리즘은 가장 기본적인 최단경로 알고리즘이다. 가장 기본적이란 말은 이외에도 벨만 포드, 플로이드 와샬 알고리즘이 있는데, 상대적으로 다익스트라가 대회에 많이 출제되기도 하고, 셋 중에 시간복잡도가 가장 빠른 알고리즘이기 때문에 꼭 숙지하는 것이 좋다. (참고로 시간복잡도는 각각 다익스트라 O(ElogV) / 벨만포드 O(VE) / 플로이드 와샬 O(V^3), 각각 사용되는 상황이 다름) 다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지의 최소비용(최단거리)을 구하는 알고리즘이다. 내가 다익스트라를 사용하는 문제 유형은 다음과 같다. 1. 최단거리 / 최소비용 문제이다. 2. 문제를 읽었을 때, 문제의 의도가 한두 개의 적은 수의 출발점을 강조한다. (만약 모든 출발점이라면 플로이드와샬).. 2021. 5. 19. 반복과 재귀 : DFS 문제를 재귀로 구현하면 편리한 이유 For문과 재귀함수 for문과 재귀함수는 '반복'을 실행할 때 사용한다는 점에서 공통점을 가지고 있다. 처음 반복문을 배울 때 대부분 for문으로 배우기 때문에, 나중에 재귀함수에 익숙해지기란 쉽지 않다. 그럼에도 재귀를 알아야하는 이유는 '함수호출과 스택 메모리' 때문일 것이다. 재귀는 '스택 메모리'를 활용한다는 특징 때문에 깊이우선탐색(DFS)과 같은 특정 알고리즘 문제를 해결할 때 유용하게 쓰이는데, 그 이유에 대해서 알아보자. 고급 프로그래밍 언어에서 함수를 호출하게 되면, 운영체제는 스택 메모리라는 곳에 그 함수만 사용할 메모리 공간을 할당해준다. 그 함수 안에서 또 함수를 호출하면, 스택 메모리에 재귀적으로 호출된 함수들의 메모리 공간이 계속 쌓이게 된다. 즉, 가장 먼저 불린 함수는 자기 .. 2021. 5. 6. Trade-off란? Trade-off란? Trade-off 관계는 컴퓨터 이론수업을 듣다보면 정말 많이 등장하는 개념이 아닌가 싶다. Trade-off 관계를 쉽게 설명하자면, 어떤 문제를 해결할 때 두 가지 방법이 존재할 때, 한 방법이 A측면에서 유리하고 B측면에서는 불리하면, 다른 방법은 B측면에서 유리하고 A측면에서 불리한 두 방법을 Trade-off 관계라고 말한다. 2021. 5. 6. [C++ 알고리즘] 오일러 회로 / 오일러 경로 (Euler ciruit / Euler trail) 오일러 회로 문제 : 그래프의 모든 간선을 한 번씩만 지나면서, 모든 정점을 들린 뒤 시작점으로 돌아오는 문제. 다른 조건은 만족하되, 시작점으로 돌아오지 않아도 되는 문제는 오일러 경로 문제이다. 어떠한 양방향 그래프가 주어졌을 때, 오일러 회로 또는 경로가 존재할 수 있는지 판단할 수 있는 필요충분조건 두 가지가 존재한다. 양방향 그래프에서 오일러 회로 또는 경로가 존재하기 위한 필요충분조건 1. 모든 정점이 하나의 컴포넌트 안에 속해 있는가? 이를 확인하기 위해서 사용할 수 있는 방법 중 하나는, 한 정점에 대하여 dfs 또는 bfs를 사용해서 탐색을 한 번 마친 뒤, 방문하지 않은 정점이 존재할 경우 두 개 이상의 컴포넌트가 존재함을 알아낼 수 있다. int chk[N]; int adj[N][N].. 2021. 3. 1. JLIS(합친 최대 증가 부분수열) 풀이, 오답노트 algospot.com/judge/problem/read/JLIS algospot.com :: JLIS 합친 LIS 문제 정보 문제 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 algospot.com 문제) 어떤 수열에서 0개 이상의 숫자를 지운 결과를 원 수열의 부분 수열이라고 부릅니다. 예를 들어 '4 7 6'은 '4 3 7 6 9'의 부분 수열입니다. 중복된 숫자가 없고 오름 차순으로 정렬되어 있는 부분 수열들을 가리켜 증가 부분 수열이라고 부르지요. 예를 들어 '3 6 9'는 앞의 수열의 증가 부분 수열입니다. 두 개의 정수 수열 A 와 B 에서 각각 증가 .. 2021. 1. 16. 이전 1 다음
