알고리즘||코딩테스트

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 사용한 알고리즘 : 위상정렬(Topological Sorting) 풀이전략 위상정렬에 대해 먼저 알아야하는데 아래 유튜브 링크를 참조하여 개념을 작성했다. https://www.youtube.com/watch?v=xeSz3pROPS8 위상정렬 : 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 위와 같은 방향 그래프가 주어졌을 ..

https://www.acmicpc.net/problem/17205 17205번: 진우의 비밀번호 진우는 비밀번호 조합을 a, aa, aaa, aaaa, aaaaa, aaaaaa, aaaaab, aaaaac, ..., azzzzx, azzzzy, azzzzz, b 순서로 시도한다. www.acmicpc.net 사용한 알고리즘 : 수학, 중복순열 풀이전략 3 ca 위와 같은 입력이 주어졌다고 생각해보자. 그러면 비밀번호 시도 순서는 아래와 같을 것이다. a aa aaa ~ aaz - 26개 ab aba ~ abz - 26개 ... az aza ~ azz - 26개 b ba baa ~ baz ~26개 bb bba ~ bbz - 26개 ... bz bza ~ bzz - 26개 c ca -------------..

https://www.acmicpc.net/problem/1354 1354번: 무한 수열 2 첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다. www.acmicpc.net 사용한 알고리즘 : Map 데이터 구조를 사용한 풀이 풀이 전략 Map 데이터구조를 이용하여 이미 구해놓았던 값은 다시 연산하지 않도록 했다. static Map map = new HashMap(); // 전역 변수로 선언되어있음 map.put(0L,1L); // main 함수에서 정의되었음 static long func(long num){ if(map.containsKey(num)) return map.get(num); if(num

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 사용한 알고리즘 : LIS(Longest Increasing Subsequence), 이분 탐색 풀이전략 LIS를 구하기 위한 전략은 아래와 같다. 위 그림처럼 입력받은 수가 수열의 최우측 원소와 비교했을 때 더 작다면 기존에 입력된 수열에서 같거나 더 크지만 가장 작은 수와 교체한다. 만약 입력받은 수가 수열의 최우측 원소보다 크다면, length의 길이를 1 늘리고 수열 최우측 바로 옆 인덱스..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 사용한 알고리즘: DP 풀이전략 펠린드롬수는 쉽게 말해서 앞으로 읽으나 뒤로 읽으나 같은 수를 뜻한다. 문제 해결 접근 방식으로 질문이 주어질 때마다 해당 수가 펠린드롬 수인지 파악하려고 한다면 최악의 경우 1,000,000번의 펠린드롬 수 판단 연산을 수행해야 한다. 수열의 크기가 최대 2000까지 가능하므로 최악의 경우 2000 * 1,000,000 = 2,000,000,000(20억)번 연산이 필요하다. 이는 JAVA가 초당 1억..

https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 사용한 알고리즘: 모노톤 스택(Monotone Stack) 풀이전략 https://justicehui.github.io/medium-algorithm/2019/01/01/monotoneStack/ monotone stack monotone stack은 몇몇 문제들의 시간 복잡도를 O(n)정도로 줄어주는 강력한 테크닉입니다. justicehui.github.io 먼저 문제를 풀기위해서는 mo..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 사용한 알고리즘 : DP 풀이전략 1. 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이 (실패, 메모리초과) 처음엔 우선순위 큐를 이용한 다익스트라 알고리즘을 사용하여 문제를 풀이했다. 그런데 메모리 초과 문제가 발생했다. 문제에서 주어진 메모리 제한은 128MB인데, 내가 선언한 클래스를 원소로 가지는 우선순위 큐는 노드 하나 당 8 byte를 차지했다. 그런데..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 사용한 알고리즘 : 이분 탐색 풀이전략 두 용액에서와 달리 이번 문제는 세 용액의 합이 0에 가까워야 한다. 저번 두 용액에서는 입력받은 용액들을 오름차순으로 정렬시키고, 최좌측 인덱스 start와 최우측 인덱스 end에 속하는 양 끝값의 합을 구하고 이 합이 0보다 크면 총합의 값을 줄이기위해 end=end-1, 합이 0보다 작으면 총합의 값을 늘리기 위해 start=..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 사용한 알고리즘 : DP 풀이전략 위의 문제에서 주어진 입력을 표로 나타내면 아래와 같다. 이중배열 d[i][j]는 i와 i번 째 이전에 입력된 동전들로, 수 j를 만들 수 있는 경우의 수를 저장한다. d[i][0]은 공집합인 상태로, 공집합 또한 하나의 경우의 수를 가지므로 1을 가진다. d[0][j]은 d[i][j]의 규칙성을 찾아낸 식에서 d[i-1][j]의 i-1에서 IndexOutOf..

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 사용한 알고리즘 : LCS (Longest Common Subsequence) 풀이전략 LCS란 최장 공통 부분집합으로 문자열 X, Y가 주어졌을 때, X와 Y에서 공통으로 나타나는 부분 문자 집합 중 길이가 최대가 되는 부분 집합을 의미한다. 예로 X = ACAYKP Y = CAPCAK 라고 할 때, 두 문자열의 LCS 는 ACAK이다. 만약..