거의 알고리즘 일기장

https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a www.acmicpc.net 1. 풀이방법 전형적인 union - find 문제다 2. 코드 #include #include using namespace std;..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 www.acmicpc.net 1. 풀이방법 이 문제를 푸는 방식에는 여러가지가 있는것 같지만 나는 dfs 백트랙킹으로 풀었다. 이때 가지를 잘치는 것이 중요하다..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 문제 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일직선으로 이은 형태이다. 모든 별들은 별자리 위의 선을 통해 서로 직/간접적으로 이어져 있어야 한다. 별들이 2차원 평면 위에 놓여 있다. 선을 하나 이을 때마다 두 별 사이의 거리만큼의 비용이 든다고 할 때, 별자리를 만드는 최소 비용을 구하시오. 입력 첫째 줄에 www.acmicpc.net 1. 풀이 방법 최장신장트리를 만드는 문제다. 조금 다른 점이 있다면 가중치가 주어지는게 아니라 만들어야한다는것만 주의하면된다. 내..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 가중치 C인 간선으로 연결되어 있다는 의미이다. C는 음수일 수도 있으며, 절댓값이 1,000,000을 넘지 않는다. 그래프의 정점은 1번부터 V번까지 번호가 매겨져 있고, 임의의 두 정점 사이에 경로가 있다. 최소 스패닝 www.acmicpc.net 1. 풀이방법 이 문제는 그리디적으로 풀어야 한다. 내가 한 풀이 순서대로 써보자면 1) 우선순위 큐에 간선의 데이터를 다넣고 c..

https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 문제 상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다. 이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 도시들을 여행할 수 있도록 도와주자. 상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다. 입력 첫 번째 줄에는 테스트 케 www.acmicpc.net 1. 풀이방법 문제를 보자마자 정점-1을 출력하면 되지않나? 라는 의문이 들었고 정답처리가 되긴했다. 하지만, 정점 -1 출력은 너무..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 1. 풀이방법 이 문제는 dp를 활용해서 가장 긴 증가하는 부분 수열의 개수와 수열을 출력하는 문제이다. 그러므로 원래 LIS보다 저번에 방문했던 인덱스를 저장할 배열이 하나 더 필요하다. 하지만, 나는 그냥 dp를 pair로 만들어서 ( 지금까지의 수열의 개수, 전에 방문한 인덱스 ) 이렇게 만..

https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다. www.acmicpc.net 1. 풀이방법 그래프의 단절점 알고리즘의 기본적인 연습문제이다. 단절점을 찾는 방법을 예시로 들면 ex) 1) dfs스패닝 트리를 만든다. ( 찾은 순서를 기록한다 ) 2) 각 정점에서의 역방향간선을 한번 이용하여 갈수있는..

https://programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 풀이 방법 이 문제는 정확성 테스트밖에 없으므로 크게 시간에 구애받지않고 풀어도 되어 두가지 방법으로 풀어보았다. 1) 무식하게 dfs돌려서 나온 그 노드의 최단거리와 노드값을 모두 한 벡터에 몰아두고, 마지막에 거리의 오름차순 정렬시켜 정답 출력하기 ( O(V+ E) ) ? 2) 다익스트라를 써서 최단경로를 구하고, 마지막에 최단거리 배열값에 있는 값중에 가장 먼 노드들 찾아 출력하기 ( O(E*log..

https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 플로이드 와샬 알고리즘 ( V^3 ) 4) 구한 이차배열을 순회하며 갔다올때 가장 적은 경로를 가지는 값 출력 ( V*( V - 1 ) ) 2. 코드 #include #include #include #define INF 987654321 using namespace std; int floyed[402][402]; int v, e; //이어진노드, 거리 vector edge; int main() { cin >> v >> e; edge.resize(v + 2); //folyed init for(int i =1; i a >> b >> c; edge[a].push_back..

https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다. 초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, www.acmicpc.net 조건 1) 인천에서 LA까지 M원 이하로 사용하면서 도착할 수 있는 가장 빠른 길 2) 공항의 수 N (2 ≤ N ≤ 10..