알고리즘

[알고리즘] 위상 정렬 Topological Sort

위상 정렬(Topological Sort) 위상 정렬이란 어떤 일을 하는 순서를 찾는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 알고리즘이다. 위상 정렬(Topological Sort)의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Topological Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. 위상 정렬(Topological Sort)을 이용한 기본적인 해결 방법 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을..

[백준 / Java] 1504번 : 특정한 최단 경로

문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지..

다익스트라(Dijkstra) 알고리즘

다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍를 활용한 최단 경로(Shortest path) 탐색 알고리즘이다. 흔히 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 다익스트라 알고리즘이 다이나믹 프로그래밍을 활용하는 이유는 '최단 거리는 다양한 루트가 존재하기 때문'이다. 그렇기에 기존에 하나의 최단 거리를 구할 때 까지 모든 루트를 그대로 사용한다. 아래의 그래프에서 1에서 다른 정점으로 가는 최단 거리를 구한다고 해보자. 1에서 각 정점으로 한 번에 가는 최단 거리는 각 3, 6, 7이다. 이 때 한 번에 가는 것이 아닌 2를 거쳐 정점 3과 정점 4로 간다면 3 > 1과 3 > 1 >..

[프로그래머스 / Javascript] 전력망을 둘로 나누기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 송전탑의 연결 상태를 파악한 후 모든 전선을 한번씩 잘라보며 각 전원의 송전탑의 수의 차이를 구하는 문제이다. 문제를 풀 때 송전탑의 연결을 송전탑의 오브젝트에 넣어두어 연결 상태를 확보한 후 끊긴 이 후 송전탑의 수를 구했다. 글보다 코드를 보면 이해가 쉬울 것 같다. function countLink (link,start) { let answer = 0; const..

[프로그래머스 / C++] 롤케이크 자르기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/132265 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 같은 토핑 가짓수로 나눌 수 있는 방법의 수를 반환하는 문제이다. 그렇기 때문에 모든 케이스를 확인해볼 필요가 있었다. 이때 모든 자르는 방법 마다 양쪽의 토핑 수를 카운트하면 시간 초과가 날 것 같았다. -> 시간 복잡도는 n^n이므로 최대 100000^100000이다. 그렇기에 초기 값을 구한 후 순서대로 올라가며 계산된 map에서 right -> left으로 값..

[프로그래머스 / C++] 모음 사전

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 최대 연산이 1만 이하인 케이스를 제시하고 있다. (모음 5개를 1에서 5자리 사이로 배치하는 경우 이므로) 그렇기에 DFS로 완전 탐색을 진행하면서 타겟 단어와 서치중인 단어가 같을 경우의 count를 반환하면 정답이 나온다. #include #include #include using namespace std; vector dic = {"A","E","I","O","..