KMF

참고: https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 주어진 수들의 연산(+, -) 결과가 배열의 마지막 수가 되는 경우의 수를 구하는 문제입니다. 일단 문제에서 주어진 단서들을 나열합니다. 수의 범위는 0이상 20이하이고, 배열의 크기는 3이상 100 이하 입니다. 그리고 올바른 등식의 개수의 범위가 2^63 - 1까지 입니다. 여기서 얻을 수 있는 힌트는 배열의 크기가 그리 크지 않으므로 이중 for문 정도는 사용할 수 있고, 정답..

참고: https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net n * m 크기의 배열에서 1로된 가장 큰 정사각형의 크기를 구하는 문제입니다. DP를 사용하여 해결할 수 있습니다. 이미 DP로 분류되어있는 것을 알았기 때문에, 저는 바로 DP로 접근했습니다. 하지만 문제 유형에 대한 단서가 주어지지 않았다면 해결 방법을 찾는데 시간을 좀 더 많이 소비 했을 것 같습니다. 다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해 뒀다가 나중에 큰 문제의 결과와 합하여 푸는 알고리즘입니다. 이러한..

참고: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 부분 수열 (LCS: Longest Common Subsequence) 문제입니다. 문제를 처음 보면 모든 가능한 수열을 구해서 비교하는 브루트포스 알고리즘이 떠오를 수 있습니다. 하지만 순열(Permutation) 알고리즘은 O(N!) 시간 복잡도를 가지기 때문에 적절한 해법이 아닌 것 같습니다. 그렇다면 다이나믹 프로그래밍으로 풀 ..

참고: https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 다이나믹 프로그래밍을 공부했다면 한 번쯤 풀어 봤을 배낭 문제입니다. 사실 배낭 문제는 두 가지 유형으로 나눌 수 있습니다. 하나는 배낭에 들어갈 물건을 나눌 수 있는 '분할 가능 배낭 문제' 이고, 다른 하나는 물건을 나눌 수 없는 '0-1 배낭 문제' 입니다. 위 문제는 0-1 배낭 문제에 해당하며, 분할 가능 배낭 문제..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 각 수업의 시간이 겹칠 경우 강의실이 추가된다. 단, 한 수업의 끝 시간과 시작 시간이 동일하면 겹치지 않는 것으로 한다. 먼저 수업들을 시작 시간을 기준으로 정렬한다. 그리고 이미 시작한 수업을 끝나는 시간을 기준으로 우선순위 큐에 삽입한다. 이미 시작한 수업의 끝 시간과 다음에 시작할 수업의 시작 시간을 비교하며 수업이 겹치지 않는 경우, 우선순위 큐에서 수업을 제거한다. 최종적으로 우선순위 큐에는 수업 시간이 겹치는 수업들만 남아있게된다...

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 각 트리 노드의 열 번호를 구하고, 레벨에 따라 저장한다. 그 후 레벨에 따라 열 번호의 최소, 최대 값을 구해 연산하면 전체 트리의 최대 너비를 구할 수 있다. 레벨에 따라 트리 노드의 열 번호를 저장 해야하기 때문에 Map 자료 구조를 사용해야한다. 그리고 아래 제시된 그림을 보면, 각 노드의 열 번호가 중위 순회에 따라 부여된다는 것을 알 수 있다. 따라서 트리를 중위 순회..

https://leetcode.com/problems/palindrome-pairs/ Palindrome Pairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 단어 리스트의 단어 조합 중 팰린드롬이 되는 모든 인덱스의 조합을 구하는 문제이다. 단순히 가능한 모든 조합을 구하고 팰린드롬인지 확인할 경우 해결은 가능하겠지만 시간이 오래걸린다. 따라서 문자열의 효율적인 탐색 자료구조인 트라이(Trie)를 사용해야한다. 데이터를 어떻게 저장해야할까? 일반적인 문..

중위 순회와 후위 순회가 주어지고 전위 순회를 구하는 문제이다. 알고리즘 자체는 어렵지 않지만 메모리와 시간 초과로 인해 최적화가 조금 필요 했다. 참고: https://white-board.tistory.com/129 최적화가 필요한 부분은 후위 순회 결과에서 선택한 원소를 중위 순회 결과에서 인덱스를 구하는 부분인데, 이는 파이썬의 딕셔너리를 사용해서 O(1) 시간에 찾을 수 있도록 헀다. Python

브루트포스 알고리즘으로 해결할 수 있다. 처음엔은 백트래킹을 통해 해결하려 했으나 시간초과가 발생했다. 해결 방법을 생각해내지 못해 다른 사람의 풀이를 참고헀더니 단순한 반복문으로 해결할 수 있는 문제였다. 먼저 주어진 높이를 카운팅하고 최대 높이를 구한다. 0 ~ 최대 높이까지 반복문을 통해 제거할 블럭의 개수와 추가할 블럭의 개수를 구한다. 만약 초기 가지고 있던 블럭 + 제거한 블럭 >= 추가할 블럭인 경우 시간과 높이를 갱신한다. Python

영화 제목에 '6'이 적어도 3개 이상 연속된 경우를 숫자의 크기대로 찾아 N번째인 경우를 반환해야한다. 가장 간단한 해결방법은 666에서 시작해서 1씩 증가시킨다. 만약 6이 연속해서 3회 이상 등장한 수인 경우 카운트를 1씩 늘리고, 카운트가 N이 된경우 그 수를 반환한다. 하지만 수를 문자로 변환시키고 파이썬 내장 함수인 count()를 사용하게 된다면 상당히 비효율적이다. 따라서 더 효율적인 코드를 위해서 숫자를 문자열로 변환하지 않고 6이 3회 이상 연속되는 경우를 찾아야한다. 숫자 i를 가지고 666이 들어가는 수를 만든다고 생각해보자. i = 0 : 0 * 1000 + 666 = 666 i = 1 : 1 * 1000 + 666 = 1666 ... i = 6 : 6 * 1000 + 666 = ..