코딩테스트 공부

코딩테스트에서 나오는 문제 중 하나인 LCS 구하기에 대해 공부해 보았다. 이 글의 내용은 Do it! 알고리즘 코딩테스트를 참고하였다. 최소 공통 조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라고면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 '최소 공통 조상' LCA(Lowest common ancestor) 이라고 한다. 최소 공통조상을 구하는 방법은 2가지가 있다. 일반적으로 구하는 방법과 빠르게 구하는 방법이다. 일반적으로 구하는 방법은 Depth를 하나씩 거슬러 올라가야 해서 모든 Depth를 탐색해야 할 수 도있다. 그래서 시간 복잡도가 크다. 하지만 빠르게 구하는 방법은 2의 K승 씩 올라가서 비교하면서 빠르게 구할 ..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 설명 결론은 가로선을 추가해 세로선의 결과가 자신의 번호가 나오게 해야 한다는 것이다. 그때 추가한 가로선의 개수를 출력하는 문제이다. 단 추가할 수 있는 가로선은 최대 3개이다. 문제에 대한 아이디어 및 구 이렇게 어떤 것을 추가하고 빼는 문제들은 브루트 포스를 사용해서 모든 경우를 검사해 보는 경우가 많다. 그래서 나도 이 문제를 풀 때 2차원 배열로 사다리를 만들고 하나씩 추가해 가면..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명 총합 classic {500, index = 0} {150, index = 2 } {800, index =3} 1450 pop {600, index = 1} {2500, index =4} 3100 pop이 더 인기가 많았으므로 pop부터 실린다. 단, 실행한 곡이 많은 순으로 실려야 하므로 4, 1 순서이다. 그 다음 classic은 순서가 3, 0, 2이지만 2곡만 실려야한다 했으므로 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제설명 5 1 3 5 10 7 4 9 2 8 중 부분합으로 15 이상인 수열 중 가장 길이가 짧은 것을 찾는 것이다. {5, 10} {10, 7}이 제일 짧다. 문제에 대한 아이디어 부분합과 수열의 길이를 구하라는 것에서 투 포인터를 써야겠다고 생각했다. 제일 처음 시작 할 때, First = 0, Second = 0; sum =0; count =0;이다. 1. sum < s 이면..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 설명 그래프가 주어졌을 때, 최소 신장 트리를 구현하고 가중치의 합을 구하는 문제이다. 문제에 대한 아이디어 최소 신장 트리를 구현하는 문제이다. 최소 신장 트리를 구하는 대표적인 알고리즘인 크루스칼 알고리즘으로 이 문제를 풀었다. 크루스칼 알고리리즘은 O(|E|log|E|)안에 최소신장트리를 만들 수 있다. 왜냐 하면 모든 edge를 탐색하는데..

주문량이 많은 아이스크림들 조회하기 https://school.programmers.co.kr/learn/courses/30/lessons/133027 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr select distinct A.flavor from first_half as A join (select july.flavor, sum(july.total_order) as TOTAL_ORDER from july group by flavor) as B on A.flavor = B.flavor order by A.TOTAL_ORDER + B.TOTAL_ORDER..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 문제 설명 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 것이다. 그래프 간 가중치가 음수가 존재한다. 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래전으로 되돌릴 수 있다면 -1을 출력 도시 순서대로 걸린 시간을 출력 해당 도시로 가는 경로가 없다면 -1을 출력 문제에 대한 아이디어 최단거리를 ..

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 문제 설명 일부 학생의 키를 비교하여 줄을 세우는 프로그램을 작성하는 것이다. 입력을 보면 1은 3보다 앞 2도 3보다 앞이다. 그래서 1 2 3 이 되는 것이다. 문제에 대한 아이디어 각 학생들을 노드라고 생각하면 노드들의 순서를 구하는 문제이다. 그래프에서 노드들의 순서를 구할 때 사용 하는 알고리즘은 위상정렬이다. 단, 그래프는 사이클이 존재하면 안..