본문 바로가기
반응형

Algorithm

 (109)
[백준][C++] 17299: 오등큰수 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net - 문제 https://stopthebackspace.tistory.com/130 위의 오큰수 문제에서 큰지 작은지 판별하는 걸 숫자가 나온 횟수로 바꾼 문제다. - 해설 오큰수 문제를 푼 방식 그대로 map을 이용해서 카운팅을 해 줬는데, 시간초과가 나왔다. 그래서 그냥 배열을 이용해서 카운팅해봤는데 잘 풀렸다. - 풀이 #include #include // #include using namespace st..
[백준][C++] 17298: 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net - 문제 A1, A2, ..., An으로 이루어진 A배열이 있을 때 Ai에 대해서 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 출력하는 문제다. - 해설 (틀린 방법) Ai에서부터 그 이후에 있는 숫자 중에서 자신보다 크면서 가장 근접한 숫자를 출력하면 되는 문제인 줄 알고 풀었다. 백준 기준으로 대략 50%까지는 천천히 되다가 시간초과가 나버린다. 심한 경우에는 O(n^2)이 되기 때문..
[백준][C++] 9935: 문자열 폭탄 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net - 문제 문자열이 S가 있고 폭탄문자열 bomb가 있을 때 S 안에 bomb를 모두 없애는 문제다. - 해설 string 클래스를 stack처럼 사용하면 문제를 해결할 수 있다. S 문자열을 하나씩 확인하다가 폭탄 문자열의 가장 마지막 문자랑 일치하는 문자가 나오면, 폭탄문자열의 길이만큼 돌아가면서 두 문자열을 비교하고, 만약 같으면 pop_back으로 날려버린다. 이후에 계속 이어..
[백준][C++] 2629: 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net - 문제 양팔저울과 n개의 추가 있고, 무게를 측정하고 싶은 m개의 구슬이 있을 때 추를 이용하여 구슬의 무게를 측정할 수 있는지 없는지 구하는 문제다. - 해설 가방문제?와 비슷하게 풀 수 있을 것 같다. 결국 추 하나당 할 수 있는 행동은 3가지가 있다. 1. 추를 좌측 저울에 둔다. 2. 추를 두지 않는다. 3. 추를 우측 저울에 둔다. 위의 세 가지 행동을 모든 추가 한다면 그걸로 문제를 해..
[백준][C++] 1520: 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net - 문제 2차원 배열이 있고, 상하좌우로 숫자가 작은 곳으로만 움직일 수 있다고 할 때 가장 우측하단에 도착할 수 있는 경우의 수를 구하는 문제다. - 해설 1. (틀린 방법) 일반적인 dfs 방법으로 하나의 점에서 상하좌우를 확인하고 해당 조건에 맞으면 가장 우측하단에 있는 지점에 도착하는 경우의 수를 구하는 방법을 생각해봤다. - 이동이 중복되는 경우도 있고, 경우의 수가 너무 많아서 시간초과가 남..
[백준][C++] 1063: 킹 https://www.acmicpc.net/problem/1063 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net - 문제 체스판 위에 킹의 위치와 돌의 위치가 주어졌을 때 각종 이동 후에 킹과 돌의 위치를 출력하는 문제다. - 해설 "A3"와 같은 위치가 주어지면 이걸 어떻게 C++언어의 배열로 변경해서 문제를 풀 것인지를 생각해야 하는 문제다. 상하좌우와 대각선까지 8방향을 dx,dy를 이용해서 접할수있고, check 함수를 만들어서 방향으로 이동한 킹과 돌이 체스판위에 있는지 확인하도록 하였다. - 풀이 #incl..
[백준][C++] 2293: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net - 문제 동전의 값이 n개 주어지면 이 동전들을 이용해서 k원을 만들 수 있는 경우의 수를 구하는 문제다(중복없이). - 해설 이건 나도 혼자서 못 풀어서 다른 사람 풀이를 보고 참고했다. 1, 2, 5원이 있다고 할 때 dp라는 배열에 1을 이용했을 때 만들 수 있는 경우의 수를 저장하고 그 다음 반복문에서 2도 함께 사용했을 때, 즉 1과 2를 사용했을 때 만들 수 있는 경우의수를 더한다. 마지..
[백준][C++] 23757: 아이들과 선물 상자 https://www.acmicpc.net/problem/23757 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net - 문제 N개의 선물 상자에 각각 c개의 선물이 들어 있고, M명의 아이들이 각자 w개의 선물을 받고 싶을 때 아이들이 주어진 순서대로 선물을 고를 때 모든 아이들이 선물을 받을 수 있는지 없는지 판별하는 문제다. - 해설 https://stopthebackspace.tistory.com/123 위의 링크에서 우선순위 큐를 처음 사용해 보았고, 어떻게 사용해야 하는지 배웠기에, 큰 숫자가 먼저 튀어나오도록 우선순위큐를 만들어 사용하면 문제를 풀 수 있다. 나는 ..
반응형

티스토리툴바