본문 바로가기

알고리즘/백준8

[백준] 2565번 전깃줄 (C++) 문제 링크 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 들어가기 전에... 해당 문제는 LIS(Longest Increasing Subsequence)를 활용하여 해결하는 문제였는데, 처음 문제를 풀 때 이를 활용하지 않는 풀이법이 생각나서 그 풀이법 대로 풀다가 틀렸다... 여러 가지 반례도 찾아보고 코드 수정도 해봤는데 결국 고통받다가 다른 사람의 풀이법 참고함... 정석 풀이법 보고 진짜 어떻게 LIS를 저런 식으로 적용해서 풀 생각을 한 거.. 2022. 7. 30.
[백준] 11054번 가장 긴 바이토닉 부분 수열 (C++) 문제 링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 들어가기 전에... 문제를 해결한 이후에 다른 분들의 풀이를 보니 훨씬 더 효율적이고 간단하게 풀었음을 발견함... 주어진 크기 데이터가 1000개 이하였기 때문에 저처럼 \(O(n^{3})\)로도 풀 수 있었지만 더 효율적이고 간단한 풀이가 존재하기 때문에 이런 식으로 풀 수도 있구나~ 하는 정도로만 참고만 해주시길 ^,,,^ 문제 설명 주어진 수열 S에 대해, 가장 긴 바이토닉 부분 수열의 길이를 구한.. 2022. 7. 29.
[백준] 17298번 오큰수 (C++) 문제 링크 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 문제 설명 크기가 N인 수열이 주어지며, 수열의 각 원소에 대한 오큰수 NGE(i)를 구한다. 오큰수는 해당 원소의 오른쪽에 있으면서 큰 수 중 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에는 오큰수는 -1이다. 예를 들어 A = [9,5,4,8]인 경우, NGE(1) = -1 (9보다 큰 수가 오른쪽에 없으므로) NGE(2) = 8 (5보다 오른쪽에 있으면서 큰 수 중 가장 왼쪽의 .. 2022. 7. 2.
[백준] 1300번 K번째 수 (C++) 문제 링크 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 설명 N과 K가 주어진다. 주어진 N에 대하여 NxN인 배열 A를 가정할 때, 배열에 들어있는 수 A[i][j] = ixj 이다. 이를 일차원 배열 B에 넣으면 NxN 크기가 되며, B를 오름차순 정렬 할 때 B[k]를 구한다. 배열 A와 B의 인덱스는 1부터 시작한다. 사고 과정 가장 단순하게 생각한다면 NxN의 배열을 반복문을 통해 생성한 후, 이.. 2022. 6. 27.

티스토리툴바