Ikjo's Technology blog

문제 설명 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 접근 방법 해당 문제는 누적합을 이용하여 해결할 수 있었습니다. 사실 처음 문제에 접근했을 때는 누적합을 생각하지 못하고 주어진 수열 상의 구간 길이 1부터 구간 길이 N까지의 부분합을 일일이 구해주면서 S 이상인 최소 구간을 구하도록 했었습니다. (결과는 당연히 시간 초과..😂) 이러한 방식은 반복문을 3개나 타기 때문에 매우 비효율적인 방법이었습니다. (반복문 하나는 구간 길이를 1부터 N까지 증가시키는 반복문, 다른 하나는 구간을 ..

문제 설명 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 해당 문제는 DFS(깊이 우선 탐색)를 통해 해결할 수 있었습니다. 이 문제를 풀기 전까지만 해도 깊이 우선 탐색하면 주로 인접 행렬 방식으로 접근했었습니다. 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식으로 연결이 되지 않은 노드 정보들까지도 배열 상에 포함되어 있다고 볼 수 있습니다. 이러한 인접 행렬 방식의 단점은 메모리가 불필요하게 낭비된다는 점입니다. 앞서 언급했듯이 연결되지 않은 노드들의 정보들도 포함되기 때문입니다. 해당 문제에서는 노드의 개수 N이 최대 10만개로, ..

문제 설명 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 접근 방법 해당 문제는 투 포인터 알고리즘을 통해 해결할 수 있었습니다. 최초 용액 정보를 받은 데이터를 오름차순으로 정렬해줍니다. (내림차순으로 정렬해도 무방합니다.) 이후 오름차순된 해당 데이터 상 시작점과 끝점을 투 포인터로 삼아 두 점의 합을 구하는데, 이 합이 최대한 0에 가까운 경우의 두 용액의 값을 결과값으로 저장하도록 합니다. 이때 시작점과 끝점을 투 포인트로 삼은 이유는 최솟값과 최댓값을 합쳤을 때 0..

문제 설명 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 방법 해당 문제는 이름에 맞게 스택 자료구조를 이용하여 해결할 수 있었습니다. 문제에서 주어진 예시로 스택 자료구조를 직접 그려보면서 접근해보니 수월하게 해결할 수 있었습니다. 우선 최초 스택 자료구조가 비어있다고 가정했을 때, 최초 4라는 숫자를 만난다면 1 ~ 4의 숫자를 스택에 push 하고 마지막 숫자 4를 pop 시켜야 합니다. 이때 스택 자료구조는 다음과..

문제 설명 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 접근 방법 해당 문제는 그리디 알고리즘 기법을 이용하여 해결할 수 있었습니다. 사실 이 문제를 처음 봤을 때 시간 제한이 2초이길래 A에 있는 N개의 수를 재배열할 수 있는 모든 경우의 수에 대해 완전 탐색하여 구해도 되겠다는 생각을 했었습니다. 그리하여 백트래킹을 통해 각각의 경우에 수에 대해 최솟값을 구하도록 했으나, 결과는 시간 초과였습니다. 😅 N은 50보다 작거나 같은 자연수이긴 하지만 이들을 순열로 재배열한다는 것은 50!라는 엄청난..