백준 알고리즘 문제풀이를 진행하면서 vector 자료구조를 선택하여 사용하는 경우가 많았는데, 경우에 따라 vector를 사용해야할 때와 vector를 사용하면 오히려 불리한 경우가 존재했다. 세 가지 자료구조를 알아보고 상황에따라 적절히 사용해보자! 1. Vector include 배열 기반의 컨테이너로, 메모리가 자동으로 heap에 할당되는 배열이다. vector는 각 원소에 대해 iterator로도 접근이 가능하지만, 배열 기반으로 이루어져있기 때문에 index로도 접근이 가능하다. 또한, 동적으로 메모리 확장/삭제가 가능항 Dynamic Array로 구현되어 있다. 연속된 메모리 공간에 저장되기 때문에 deque, list에 비하여 개별 원소에 대한 접근 속도가 빠르다. [O(1)] 배열기반이기 ..

https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 1. 문제 분석 처음에는 문제를 읽고, 쇠막대기가 겹쳐있고.. 자기보다 길이가... 이런 긴 설명때문에 잠시 문제를 읽기가 싫어졌지만 다시 집중해서 읽어보니 복잡한 내용은 아니었다. 레이저와 쇠막대기의 배치를 '(', ')' 괄호를 이용한 한줄의 문자열로 주어지는데, 이를 해석해서 잘린 쇠막대의 총 개수를 알아내는 문제이다. 문제를 풀기 위해서는 먼저, 주어진 괄호가 쇠막대인지, 레이저인지 구분할 수 있어야..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 1. 문제 분석 정리하자면, 테스트 데이터로 '('와 ')'가 반복되는 랜덤한 배열이 주어지는데, 이것이 VPS인지 아닌지를 판단하는 문제! 그러면 어떤 경우에 VPS가 가능한건지 혹은 불가능 한것인지 예시를 통해 알아보자. 위의 예시들을 통해 VPS여부를 판단하는 두 가지 규칙을 확인할 수 있었는데, 첫 번째, 모든 과정이 종료된 이후, 짝을 짓지 못한 괄호가 한개..

더보기 백준 정렬문제를 쭈욱 풀면서 10989 번 문제를 풀게 되었는데, 이전의 풀이 식으로 문제를 풀이하니 전혀 메모리초과.. 와 같은 문제가 발생했다 ㅜ.ㅜ 나와 같은 문제를 겪는 사람들이 있을까 하여 질문글들을 찾아보니, 이런 문제의 경우에는 카운팅정렬을 사용할 것을 추천하는걸 보고 '카운팅정렬' 알고리즘을 공부 !_! '빠른 속도'를 자랑하는 정렬 알고리즘으로는 시간복잡도가 O(N*logN)의 속도를 가지는 퀵정렬, 병합정렬, 힙 정렬 등이 있다. 하지만, 이보다 더 빠른속도의 정렬 알고리즘이 필요하다면? 특정한 조건을 만족하는 상황에서 시간복잡도가 무려 O(n)인 빠른 정렬 알고리즘인 '카운팅정렬(Counting Sort)'를 정리하고자 한다. 1. 카운팅 정렬 정렬하고자하는 모든 데이터가 특정..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 문제 설명이 조금 길고 복잡해 보이지만, 전형적인 DP문제이다! 문제풀이를 위해 필요한 부분만 정리하자면 아래와 같다. "최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다." 예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 임의의 수열에서 '연속'된 '몇개'의 수를 선택해서 구할 수 있는 합 중 가장 큰 값을 구하는 문제이다. (최소 하나 이상 선택) 수열의 길이가 n이고 입력받은 수열을 배열 arr[100001]에 arr[1]부터 arr[n]까지 차례대로 입력받는다고 할 때, dp[100001]은 arr[i]를 끝값으로 가지는 연속된 수열합의 최대값을 저장한다. 첫번째 예제에서와 같이 입력받았을 경우를 살펴보자! 10 10 ..