본문 바로가기

분류 전체보기282

1781. 컵라면 (Python) 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 그리디하게 현재 시간에서 풀 수 있는 문제의 리스트 중 가장 많은 컵라면 수를 얻을 수 있는 문제를 풀어 컵라면을 얻도록 하면 된다. 이때 현재 시간은 1에서부터가 아닌 제일 큰 데드라인부터 1씩 줄여가면서 풀 수 있는 문제에 대하여 컵라면 수를 우선순위 큐에 넣고 가장 큰 수를 꺼내어 풀면 된다. 문제의 예제를 보면 가장 큰 데드라인은 6이다. 그렇기 때문에 시간은 6부터 시작한다. 현재 시간 6에서 풀 수 있는 문제는 7번이 있다. 7번을 풀고 얻을 수 있는 컵.. 2022. 4. 27.
11054. 가장 긴 바이토닉 부분 수열 (Python) 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 최장 증가 부분 수열(LIS)을 활용하여 해결하는 문제다. LIS는 이 링크를 참고하자. LIS를 구하는 방법에는 dp를 사용하는 방법과 이분 탐색을 사용하는 방법이 있다. 이 문제는 dp를 사용하여 해결하면 된다. A 배열의 각 원소까지 증가 부분 수열을 만들었을 때의 길이를 구한다. 위와 같은 array가 있을 때 dp 배열의 의미는 각 인덱스까지의 증가 부분 수열 중 가장 긴 증가 부분 수열의 길이를 의미한다. 이렇게 한 번 dp를 구하고 이번에는 배열을 뒤집어서 한 번 .. 2022. 4. 26.
7453. 합이 0인 네 정수 (Python) 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 풀이 두 가지 방식으로 풀었는데 기본적으로 적용되는 것은 A, B, C, D 이렇게 4개의 배열을 두고 각각 더하는 것이 아니라, A 배열과 B 배열의 원소를 합한 결과(이하 AB라고 표기) 그리고 C 배열과 D 배열의 원소를 합한 결과(이하 CD라고 표기) 이렇게 두 개로 나누어 구한다. 이때 AB의 원소와 CD의 원소의 합이 0이 되려면 두 값의 부호가 반대여야 한다(ex. AB: 29, CD: -29). (1) Dict를 사용한 풀이 먼저.. 2022. 4. 25.
2539. 모자이크 (Python, Swift) 2539번: 모자이크 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 www.acmicpc.net 풀이 문제의 조건을 잘 읽어봐야 된다.......... 문제에 주어진 조건 중에서 모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다고 되어있다. 처음에 이걸 도화지의 모든 행의 밑변으로 이해하고 풀었는데 결국 해결하지 못하여 인터넷에 검색해서 풀이를 조금 봤는데 알고보니 가장 아래 밑변 하나를 의미하는 거였다. 이걸 알고나니 쉽게 문제를 해결할 수 있었다ㅎ. 문제에서 가장 작은 색종이의 크기를 물어보고 있다. 색종이의 크기가 N이고 N크기의 색종이로 잘못 칠한 칸을 주.. 2022. 4. 23.
2042. 구간 합 구하기 (Python) 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 세그먼트 트리를 사용하는 대표적인 문제이다. 해당 문제에 대한 풀이는 세그먼트 트리에 대한 포스팅을 참고하자. 코드 import sys input = sys.stdin.readline # 세그먼트 트리 초기화 # start, end: 범위(구간), node: 세그먼트 트리에서 노드 번호 def init(start, end, node): # start와 end가 같다는 것은 leaf node임을 의미.. 2022. 4. 22.
[Algorithm] 세그먼트 트리 (Segment Tree) 세그먼트 트리란? 세그먼트 트리는 완전 이진 트리를 기반으로 주어진 쿼리에 빠르게 응답하기 위해 만들어진 자료구조이다. 각 노드는 구간, 혹은 그 구간의 정보(구간합, 구간의 최솟값 등에 대한)를 저장하고 있는 자료구조이다. 리프 노드들은 길이가 1인 각각의 구간을 갖고 있고 부모 노드는 자신의 자식들의 구간의 합을 갖고 있으며 모든 구간은 연속적이다. 루트는 전체 구간을 포함하게 된다. 세그먼트 트리의 시간 복잡도 -> O(logN) 세그먼트 트리는 한 번의 연산에 O(logN)의 시간복잡도를 가진다. 만약 0번부터 7번 인덱스까지의 원소의 합을 구한다고 가정해보자. 완전탐색으로 값을 구할 경우 총 7번의 연산이 필요하다. 하지만 세그먼트 트리를 사용하면 루트 노드에 0~7까지의 구간합을 갖고 있고 따.. 2022. 4. 22.

티스토리툴바