본문 바로가기

Programming/BOJ277

[C/C++] 백준 #2075 N번째 큰 수(n'th element) N번째 큰 수를 찾으라는 이 문제는 특이한 조건을 가진 \(N \times N\) 2차원 공간에 들어가 있는 숫자 중 뒤에서 N번째 큰 수를 찾아서 출력하라는 것입니다. https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 처음 이 문제를 봤을 때, 저 조건을 잘 이용하면 되지 않을까라는 생각을 하고 고민을 했습니다. 하지만 결론은 문제에서 제시하는 조건은 쓸모가 없다는 것입니다. N개의 정렬된 상태의 배열이 있으니 합병을 생각할 수도 있지만, 결국 \(O.. 2023. 3. 25.
[C/C++] 백준 #2056 작업(위상정렬) https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 이번 문제는 선행작업과 후행작업이 있을 때, 전체 작업시간이 얼마나 걸릴 것인지 판단하는 것입니다. 소프트웨어 공학에서 자주 발생하는 일입니다. 소프트웨어 공학에서도 선행작업과 후행작업이 있는 경우 작업 인력을 무한정 투입할 경우 마칠 수 있는 최소 시간을 구하게 됩니다. 이와 같이 작업의 선후가 있는 경우에 위상정렬을 사용하게 됩니다. 위상절렬은 작업의 선후에 따라서 정렬을 하는 것이지.. 2023. 3. 23.
[C/C++] 백준 #2042 구간 합 구하기(세그먼트 트리) 구간 합 구하기 문제는 전형적인 세그먼트 트리를 이용하여 푸는 문제입니다. 세그먼트 트리 이외에도 비슷한 방식들이 존재합니다. 세그먼트 트리를 이용하는 문제는, 1. 많은 수의 쿼리를 진행해야 하고, 2. 미리 연산한 결과를 사용할 수 있어야 하고, 3. 미리 연산한 결과를 수정해야할 경우가 많은 경우 형태일겁니다. 위의 조건이 만족하지 않는다면, 다른 방식으로 계산하는 것이 더 좋을 수 있습니다. 세그먼트 트리와 관련한 문제들은 다음과 같습니다. https://sdev.tistory.com/958 백준 #1849 순열(세그먼트 트리) 이번 문제는 N개의 배열에 1부터 N까지 한번씩만 숫자가 써져있는 a[i] 수열이 있을경우, A[i] 란 수열은 원래의 수열에서 i번째 수의 앞에 있는 수 중 i보다 큰 .. 2023. 3. 21.
[C/C++] 백준 #2023 신기한 소수(수학) N자리 소수중에서 하위자리를 빼나가도 소수가 되는 수들은 상당히 많습니다. 첫자리를 제외하고 나머지는 모두 홀수로 이루어져 있어야 하죠. 물론 5와 같이 10의 소인수인 수는 제외입니다. 이 문제를 풀기 위한 접근은 간단합니다. 1) 초기 시작수 2, 3, 5, 7을 리스트에 넣습니다. 2) 이곳에 1, 3, 7, 9를 붙여서 소수가 된다면 그 수를 리스트에 넣습니다. 3) N자리수가 될때까지 2)를 반복합니다. 이렇게 하면 손쉽게 결과를 출력할 수 있습니다. for 루프 쓸 때, 1, 3, 7, 9만 붙이면 되는데, 그냥 5도 같이 붙였습니다. 크게 성능 이슈가 있지는 않기 때문에, 문제 통과하는데에는 이상이 없었습니다. 제가 작성한 소스입니다 //------------------------------.. 2023. 1. 19.
[C/C++] 백준 #2014 소수의 곱(우선 순위 큐) 우선 순위 큐와 힙(heap) 자료구조는 탐욕 알고리즘(greedy algorithm)에서 많이 쓰이는 자료구조입니다. 우선 순위 큐가 힙 자료구조를 이용해서 작성된다는 것은 이미 잘 알고 있겠죠. 그래서 삽입, 최소값(또는 최대값) 삭제가 모두 \(O(\log N)\) 시간복잡도를 가지고 있습니다. 이번 문제는 주어진 소인수로 이루어진 수들중 K번째로 작은 수를 고르는 문제입니다. 여러가지 방식을 생각해보았는데, 저는 우선 순위 큐를 이용해서 풀었습니다. 1) 주어진 소수를 우선 순위 큐에 넣습니다. 2) K번째 수가 나올 때까지 2-1) 우선 순위 큐에서 수를 빼냅니다. 2-2) 빼낸 수에 대해서 주어진 소수를 곱해서 우선 순위 큐에 넣습니다. 조금이라도 효율을 좋게 하기 위해서 우선 순위 큐의 저장.. 2023. 1. 17.
[C/C++] 백준 #2011 암호코드(동적 계획법) 영문 대문자로만 이루어진 암호가 있으면, 해당 영문자를 A는 1로 B는 2로 Z는 26으로 차례대로 숫자를 지정한다면, 숫자를 나열할 수 있습니다. 예를 들어서 BEAN은 B는 2, E는 5, A는 1, N은 14이므로 25114로 표현할 수 있죠. 하지만, Y = 25, K = 11, D = 4 이므로 YKD도 될 수 있죠. 숫자가 주어졌을 때, 그것을 영문자로 바꿀 수 있는 경우는 제한되어 있습니다. 일단 0을 제외한 한자리 숫자는 모두 영문으로 만들 수가 있겠죠. 두자리 숫자가 26을 초과한다면 이 경우에는 J 이상의 영문자로 만들 수가 없으므로 한자리 숫자로 해야 합니다. 그리고 바꿀 수 없는 경우도 있습니다. 304와 같은 숫자는 나올 수 있는 영문 단어가 없습니다. 30은 글자가 안 되고, 0.. 2023. 1. 15.
728x90

티스토리툴바