컴공과고씨

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제를 먼저 이해하면 탑이 서있을 때 오른쪽 탑부터 왼쪽으로 레이저를 쏴서 자신보다 높이가 같거나 높은쪽에 부딪치면 수신하는 탑이 되고 없다면 0을 출력하는 것이다. 내가 생각한 문제 접근 방식을 소개하면 일단 처음 입력 받은 탑들을 스택에 넣어준다. 스택에 넣어주는 이유는 오른쪽 탑부터 레이저를 쏘기 때문이다. 이 때 스택에 저장하는 값은 pair를 이용해서 첫번째는 탑의 높이 두번째는 순서를..

https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 이 문제 같은 경우는 2개의 케이스로 나누어서 풀어주었다. 첫 번째는 트럭이 올라갈 때 다리의 무게가 버틸 수 있어 트럭이 올라갈 수 있는 경우와 트럭이 다리를 다 건넌 경우로 나누어 주었다. 트럭이 출발하면 큐에 넣을 건데 이 때 그 트럭의 무게와 언제 다리를 다 건너는지 도착 시간을 pair를 이용해서 넣어주는 것이 핵심이다. 큐를 쓰는 이유는 ..

https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 이 문제 같은 경우 각 줄마다 누루고 있는 음을 저장하는 스택배열을 선언해서 풀면 쉽게 풀 수 있다. 음을 누를경우 스택에 넣어준다. 이유는 먼저 누른 음은 항상 나중에 뗄 것이기 때문이다. 만약 5를 누루고 10을 누루고 11을 눌렀다고 치고 6을 누르려고 하면 손가락을 뗄 때는 마지막에 누른 음부터 손가락을 떼게 된다. 11->10까지 떼주고 6을 눌러준..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 이 문제를 보고 일단 어떤 수를 제곱수로 나타내야 하니 어떤 수가 주어졌을 때 주어진 수보다 작거나 같은 제곱수 까지 구해서 배열에 저장해놓고 그 배열안에 수를 이용해서 합이 n이 되도록 찾는 식으로 풀어 주었다. 배열에 저장하지 않고 연산을 계속하면서 찾을 경우 당연히 연산 시간이 오래걸려 시간초과가 난다. 합이 n이 되도록 할 때 최소 개수의 수로 만들어야 ..

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 이 문제를 보고 처음에는 당연히 queue를 떠올리기 어려울 수 있지만 한 번 직접 괄호 지우다 보면 queue가 떠올라야한다. 이런식으로 앞에 나온 ( 가 있다면 ) 나왔을 때 (을 지워주는 형식으로 할 것이다. 그런데 만약 남아있는 ( 있거나 ( 가 나오지 않았는데 ) 나온다면 그것도 잘못된 괄호이다. 그래서 큐를 이용하는 것이다. 먼저 ( 일 경우 큐에 push..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 일단 규칙을 파악해보면 n = 7, k=3 일 때 12[3]45[6]7 12[4]57 [1]25[7] 이런식으로 []안에 있는 것을 출력할 것이다. 쉽게 생각해보면 자기 차례가 아닌 것을 뒤로 보내주면 연결이 된다. 12[3]45[6]712[4] 이런식으로 말이다. 바로 queue를 쓰면 쉽게 이 방식을 구현할 수 있다. 자기 차례가 아니면 뒤로 옮겨주고 자기 차례인 경우 pop을 해주면 된다. ps. 출력 형식이 안에 있으니 주의 하도록 하자. 단계별 풀이 1. 정답을 저장할 vecto..

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net pair로 받아서 정렬 기준을 바꾸어 주면 된다. vector를 잘 모르면 https://hagisilecoding.tistory.com/53?category=1050177 공부하고 오면 이해하기 편하다. 전체코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2..

https://www.acmicpc.net/problem/23284 23284번: 모든 스택 수열 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 www.acmicpc.net 문제를 보고 일단 구해보려고 직접 써보았다. 그러다 보니 떠오른생각이 N-Queen하고 비슷한 문제인 것을 느껴서 백트래킹 쪽으로 생각하게 되었다. 왜 비슷하면 각 자리마다 숫자를 넣을 때 이 숫자를 넣으면 수열이 가능한지 아닌지를 판단 한 후 아니면 다른 수를 넣는식으로 가기 때문에 n-queen도 각 자리에 퀸이 들어갈지 아닐지를 판단하는 문제였어서 비슷하다고 느꼈다. 이..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 이 문제같은 경우 다이나믹 프로그래밍에 대표적인 문제라고 할 수 있다. 각 경우에 대해서 최선의 선택을 하면서 가면 되는데 이 말을 이해하기 위해서는 직접해보는 것이 좋다. 표를 직접 그려봤다면 이게 무슨 원리인지 알 것이다. 자신이 채우고 있는 행의 최선의 선택은 1. dp[i][j] = dp[i][j-현재 물건 무게] + 현재 ..