백준 바로가기 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이분 탐색 마지막 문제입니다. 시험이 있어 참여하지 못한 주차에 스터디원들이 진행한 개념이 이분 탐색인데, 그 때 다루지 않은 문제를 제가 맡아 풀게 되었습니다. 이분 탐색은 시간 복잡도를 log2n으로 낮춰줍니다. 범위를 절반으로 나눠 타겟값이 들어있는 한쪽에서 탐색이 진행되기 때문이죠. 이 문제 접근방식은 '해결하는 목적이 무엇인지 알고 접근하라.' 입니다. LIS 배열을 구현해내는 것이 아니라 길이(size)만 출력하면 된다는 것이 포인트입니다..

백준 바로가기 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 오랜만에 알고리즘 문제를 업로드 합니다. 정처기 시험이 끝나고 처음이네요. 우선순위 큐라는 알고리즘인데, 문제에선 힙(Heap) 자료구조를 구현하도록 되어있습니다. 힙을 간략하게 알아보자면 완전 이진트리의 일종 반정렬 상태(완전히 정렬된 상태가 아님)이며, 완전 이진트리와는 다르게 중복값이 허용 힙의 삽입과 삭제의 시간 복잡도는 최악의 경우 최하단 노드로부터 최상단 노드까지 스왑이 필요하게 됩니다. 따라서 O(log N)의 시간 ..

백준 바로가기 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀다가 시간이 모자라 다른 분의 풀이를 보고 해석한 문제입니다. 많이 어렵진 않은 문제라 설명이 짧습니다. 1. 배열생성 앞, 뒤에서 문자 뽑는 함수가 있으므로 Deque 사용 Deque = Double End Queue 빈 배열일 때 D(Delete)될 수 없기 때문에 error 처리 StringTokenizer로 입력받은 배열을 Deque에 저장 2. 함수 실행 R일 경우 boolean r을 false로 바꿈 D일 경우 r이 false면 pollLast(맨 뒤 index 뺌), true면 pollFi..

백준 바로가기 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 스택을 활용해 정해진 수열을 만드는 문제입니다. 바로 이해가 되지 않았던 문제인데, 숫자 n이 주어지면 1~n까지 숫자들을 오름차순으로 정렬된 스택에 저장하면서 push와 pop으로 주어진 수열을 반환해주면 됩니다. 저는 for문으로 접근했다가 중첩 시 조건에 맞추기가 어려워 못풀었습니다. 풀이를 보니 반복 조건을 넣을 수 있는 while문을 사용해야 되더군요. 또한..

백준 바로가기 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 거스름돈 최소 동전 개수로 구하는 문제를 이전에 풀어봤기 때문에 어렵진 않았다. 하지만 혼자 틀린 반례를 상상하느라 이상한 조건을 넣어줘 한 번 틀렸다. 주어지는 동전 가치는 i번째 동전이 i-1번째 동전의 배수이기 때문에 만일 target 동전 값이 700일 때 500과 300이 동시에 존재할 수는 없다. 만일 300이 있다면 500보다 300을 넣고 나머지를 1로 채워줘야 한다. 음..

백준 바로가기 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net DP 알고리즘 내 LIS(Longest Increasing Subsequence) 최장 증가 수열 문제입니다. 이해하는데 하루 꼬박걸렸으며 이해까지 도달하는데 효과적인 매체는 아래 유튜브 강의였습니다. 설명이 영어라도 그림만 봐도 이해되는 강의라 보심을 추천드립니다. 링크 출처: https://www.youtube.com/watch?v=CE2b_-XfVDk&list=LL&index=8&t=311s 풀이의 골자는 주어진 수열을 중첩 반복문으로 돌면서 각 index 값을 ..