https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 설명 입력값 4 -5 1 -3 2 -9 5 -8 7 2 2 -11 -6 3 7 4 -1 A, B, C, D중 하나씩 골라서 총 합이 0이 되는 조합의 수를 구하여라!! 문제에 대한 아이디어 및 구현 시간제한과 메모리 시간제한이 12초 메모리 제한이 1024MB라는 점에서 처음에는 어떻게든 답을 구하면 되겠다고 생각했다. 근데 생각해보니 A B C D의 갯수의 최대가 4000..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제설명 제일 처음 그림 1처럼 2차원 배열에 빙산의 현재 상태를 알려준다. 비어있는 부분은 모두 0이다. 빙산은 1년이 지날 경우 주변에 0의 갯수만큼 줄어든다. 즉 상하좌우에 0의 갯수가 2개라면 그 빙산은 2만큼 크기가 줄어든다. 문제에 대한 아이디어 처음에 생각한 방법 2차원 배열에서 0인 부분은 넘어간다. 0이 아닌부분은 상하좌우에 0의 갯수를 count한 뒤 그만큼 빼준다.(만약 ..

문제 설명 N = 3 이고 K = 7이 주어줬을 때, 문제에 대한 아이디어 시간복잡도 생각해보기 k의 범위가 최대 10의 9승이므로 시간 복잡도가 N의 2승인 알고리즘은 사용할 수 없다. 상수시간이나 NlogN시간안에 문제를 해결해야 한다. 그때 필요한 것이 이진 탐색이다. 실패한 방법 처음에는 처음부터 N*N 크기의 일차원 배열을 만든 뒤, 거기에 i*j를 하나씩 넣었다. 그 뒤 sort함수를 사용하고 k 번째 수를 찾았다. 제일 보편적으로 생각할 수 있는 방법이지만 i*j의 수를 일차원배열에 집어 넣을 때 N제곱 반복문을 사용하므로 당연히 시간초과가 났다. 성공한 방법 그래서 생각한 방법이 이진 탐색이다. 이 문제가 이진 탐색 분류에 있어 이진 탐색을 쉽게 생각했지만 만약 그냥 이 문제를 만났다면 이..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 문제 설명 -1 -8 2 1 3 6 -5 0 1 이 주었다고 가정하자. (-8 * -5) + (-1 * 0) + 1 + 1 + 2 + (3 * 6) = 62 이다. 문제에 대한 아이디어 이 문제는 그리디 알고리즘으로 풀어야 하는 이유가 매 순간 제일 최대의 값을 구해야 하기 때문이다. 실패한 아이디어 제일 처음 문제를 풀 때는 엄청 간단하게 생각했다. 오름차순으로 배열을 정렬 시킨 뒤 맨 뒤에서..

탐욕 알고리즘이란? 탐욕 알고리즘은 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 방식이다. 더보기 5개의 도시를 모두 한 번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것 "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다" (그리디 알고리즘) 탐욕 알고리즘이 문제를 해결하는 방법 1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다. 2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다. 3. 해답 검사(Solution C..

https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 설명 문제는 간단하다. 특정 이진 트리에 대한 인오더와 포스오더가 주어지면 이것을 토대로 프리오더로 구하는 것이다. 참고 자료 트리를 순회하는 방법은 크게 3가지가 있다. 프리오더(Pre-order) : 전위 순회 인오더(In-order) : 중위 순회 포스트오더(Post-order) : 후위 순회 프리오더(Pre-order) 프리오더는 그래프의 DFS와 순서가 같다. 루트노드 방문 왼쪽 자식 노드를 루트로 하는 서브..