https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net # 조건 VPS를 판별하는 문제이다. VPS란, 괄호가 짝이 맞는 경우를 말하는데, (())와 같이 괄호안에 올바른 괄호가 들어가 있는 경우도 포함이다. 첫 째줄에는 테스트 케이스 수 N, 그 이후에는 괄호 문자열이 주어진다 # 접근 방법 및 SOLUTION 전형적인 STACK문제라고 생각이 들었다. 여는 괄호가 온다면 괄호 리스트에서 POP과 동시에 STACK에 넣..

백준 5557_1학년 # Problem 줄 지어있는 숫자 들이 있을 때 아래의 조건을 지키며 등식을 완성하여라 마지막 두 숫자 사이에는 '=', 나머지 숫자 사이에는 '+'또는 '-' 이 때, 왼쪽부터 계산을 할 때, 중간 결과값이 모두 0이상 20이하여야 한다. 올바른 등식의 수를 구하는 프로그램 작성 # 접근 방법 모든 경우의 수를 구하게 되면 2^100의 경우의 수가 생기므로 dp로 풀어야 될 것 같다. bottom-up 방식으로 DP TABLE 이용 DP TABLE의 경우 최댓값이 20이 넘어가면 안된다는 조건이 있기 때문에 21개만 만들어주면 된다. 점화식 equation[i][j+number[i]] += equation[i-1][j] equation[..

https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net # 조건 - D km 길이의 고속도로를 지나는데 이 고속도로는 심각하게 커브가 많아 운전하기 힘들다. - 이 고속도로에는 지름길이 존재하는데 - 모든 지름길은 일방통행이며, 고속도로 역주행은 불가 - 운전해야하는 최소 거리를 구하여라 # 접근 방법 및 풀이 과정 - 문제를 읽으며 드는 생각은 거리를 기록해둔 후 이를 통하여 최소 값을 구하면 될 것같다. - 내가 이용하는 지름길의 거리와..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net # 조건 정수 4를 1,2,3의 합으로 나타내는 방법은 총 7가지 합을 나타낼 때는 수를 1개이상 사용 정수 n이 주어졌을 때, 1,2,3의 합으로 나타내는 방법의 수를 구하라 # 나의 접근 방법 1,2,3으로 나타낼 수 있는 경우의 수를 구하는 문제이므로 6의 경우 1,1,1,1,1,1 에서 3,3 까지 오면된다. 1만 이용하는 방법에서 총 1의 개수 = 주어지는 n 이 때, 1,2,3으로 이루어진 길이 n의 중복순열을 구한 후 합이 n과 같다면 카운트 해준다. 길이 n은 2가 1개 들어갔을 ..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net # 조건 - 크기가 있는 상자들이 주어질 때, 앞의 상자가 뒤의 상자보다 크기가 작다면 뒷 상자에 앞의 상자 넣을 수 있다. - 예) 1 - 6 - 2 - 5- 7의 크기를 가진 상자가 주어질 때, 1- 6 -7 (3개) 또는 1-2-5-7 (4개)의 방법으로 상자를 넣을 수 있다. - 한 번에 최대 많은 상자를 넣었을 때의 개수를 구하여라. # 접근 방법 넣을 수 있는 모든 경우의 수를 구한다면 시간 초..

저번에 배웠던 버블, 선택 정렬은 비교와 교환에 기반한 정렬 방식이었고 카운팅 정렬은 비교환 방식이었다. 이번엔 분할 정복 알고리즘에 기반한 퀵 정렬과 합병 정렬에 대해서 알아보자. # 합병 정렬 컴퓨터에 관해 일을 한다면 꼭 알아야 되는 '존 폰 노이만'이 제안한 방법 일반적으로 구현 시 중복된 값을 입력 순서와 동일하게 정렬하는 '안정 정렬' 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법 과정 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 보고 그렇지 않다면 리스트를 절반으로 자른다. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬하고 다시 하나의 정렬된 리스트로 합병 추가적인..

지난 시간의 배열도 그렇고 오늘 배울 정렬은 대체 어떤 것을 위해 배우는 것일까? 그걸 알기 위해 '인덱스'에 대해 조금 알아보고 가자. 인덱스 인덱스라는 용어는 데이터베이스에서 유래했으며, 테이블에 대한 동작 속도를 높여주는 자료 구조이다. Database 분야가 아닌 곳에서는 Look up table 등의 용어를 사용하기도 한다. 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다. 왜냐하면 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문이다. 배열을 사용한 인덱스 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다. 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용 정렬 2개 이상..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net # 조건 자연수 N이 주어진다. 다음 줄에는 N개의 정수 A[1] ---- A[N]이 주어지고 다음 줄에는 M 그 다음 줄에는 M개의 수들이 주어지는데, M개의 수들이 A안에 존재한다면 1, 아니면 0 출력 # 접근 방법 처음엔 리스트로 받아서 contain method in을 이용하여 제출 시간초과가 나서 이분탐색으로 접근하였다. 정렬을 해준 후,..

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 10828 스택문제와 마찬가지로 Queue의 기본 기능을 구현하는 문제였다. # 조건 push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 ..