컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상정렬 알고리즘 문제이다. 아래 링크에 자세한 풀이가 나와있다. https://kimmessi.tistory.com/207 [알고리즘] 위상 정렬 (Topology Sort) - BFS 위상 정렬이란? 순서가 정해져있는 작업을 차례로 수행하여야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프..

https://www.acmicpc.net/problem/2568 2568번: 전깃줄 - 2 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100,000 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결 www.acmicpc.net 문제 해결 알고리즘 LIS알고리즘에서 길이와 수열을 구하는 문제이다. 좀 달랐다면 여기서는 제거해야할 원소의 갯수와 위치를 출력한다는 점인데, 그 부분은 record 배열에서 LIS가 아닌 부분을 출력하면 그만인 문제이다. 아래의 링크에 자세한 설명이 있다. https://kimmessi.tistory.com/191 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 알고리즘을 활용한 문제이다. 작업 시간이 있는 것이 좀 다른데, 이것은 계속해서 결괏값을 먼저 해야할 작업이 걸린 시간 + 현재 해야할 작업이 걸리는 시간과 계속 비교해주면서 더 큰 쪽을 결괏값에 대입해준다. https://kimmessi.tistory.com/194 [위상 정렬] BOJ 2056 작업 https://www.acmicpc.net/prob..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 알고리즘을 활용한 문제이다. 작업 시간이 있는 것이 좀 다른데, 이것은 계속해서 결괏값을 먼저 해야할 작업이 걸린 시간 + 현재 해야할 작업이 걸리는 시간과 계속 비교해주면서 더 큰 쪽을 결괏값에 대입해준다. 아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다. https://kimmessi.tistory.com/207 소스 코드 #in..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 문제이다. 아래의 링크에 위상 정렬 알고리즘에 대한 자세한 설명이 나와있다. https://kimmessi.tistory.com/207 [알고리즘] 위상 정렬 (Topology Sort) - BFS 위상 정렬이란? 순서가 정해져있는 작업을 차례로 수행하여야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순 ki..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 해결 알고리즘 대표적인 백트래킹 문제 아래의 링크에 푸는 방법이 있습니다. https://kimmessi.tistory.com/86?category=871925 [알고리즘] 백트래킹 - n-Queens, 해밀턴회로 되추적 (Back Tracking) 틀린 답에 접근했을 때, 틀리기 전의 상태로 돌아가서 다른 선택을 하는 알고리즘 만약 답이 나올 때까지가 시간 복잡도가 엄청 복잡하게 나올 수도 있지만, 이 답..

다익스트라 알고리즘 (Dijkstra's algorithm) 특정 노드에서 출발해 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘 다익스트라 알고리즘은 음의 간선이 있는 그래프에서는 사용이 불가능하지만 현실 세계에서는 음의 간선이 존재하지 않으므로 현실 세계에서 쓰기에 적합하다. 다익스트라는 그리디로 분류된다. 매상황 가장 비용이 적은 노드를 선택해 임의의 과정을 반복해준다. 동작 과정 1. 출발 노드를 설정해준다. 2. 최단거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택한다. 4. 해당 노드에서 다른 노드로 가는 최단 거리 테이블을 갱신해준다. 5. 3번과 4번을 반복한다. 알고리즘 사례 위와 같은 그래프가 있다고 하자 출발점은 0이다. 이제부터 0번 노드..

최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 수열을 최장 증가 부분 수열이라고 한다. 이 최장 증가 부분 수열 알고리즘을 간단하게 구현하는 방법은 DP를 사용하는 것이다. 다이나믹 프로그래밍을 이용한 최장 증가 부분 수열 for(int i=1;i dp[i]) dp[i] = dp[j] + 1; } result = max(result, dp[i]); } 각 수열의 원소까지의 최장 증가 부분 수열의 크기를 dp배열에 입력을 해주는 알고리즘이다. 처음 원소부터 해당 원소까지 for문을 돌리는데 이때, for문에서 돌리는 원소의 크기보다 해당 원소의 크기가 크고 최장 증가 부분 수열의 크기는 ..

https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 해결 알고리즘 이분 탐색을 이용한 LIS알고리즘을 이용한다. https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 이용해 푼 LIS알고리즘 https://kimmessi.tistory.com/191?category=871925 [알고리즘] 최장 증가 부분 수열(LIS) - DP, 이분 탐색, LIS 출력 최장 증가 부분 수열 (LIS)이란? 어떤 수열에서 수열의 일부 원소를 골라 만든 부분 ..