분류 전체보기
1890번-점프
문제 https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 "반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다." 라는 힌트로 두 가지의 경우로 나뉘며 재귀함수로 코드를 작성하면 구현이 쉬울 거 같은 설명이 적혀있다. 2) 시간 복잡도 다이나믹 프로그래밍을 활용하여 접근하였으므로 O(n)의 시간복잡도를 가진다...
1912번-연속합
문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 접근방법 1) 접근 사고 처음에는 이분탐색으로 구현을 할 려고 했었다. 그러나 이분탐색 부분을 구현하던 도중 두 개의 값을 더 한것을 어떻게 표현할 것인지에 대해 막혀서 다시 고민을 했었고 두 개를 더할 것인가 말 것인가에서 DP로 점화식을 세우면 될 것 같다고 생각을 하였다. 2) 시간 복잡도 DP로 구현을 하였으므로 시간초과 관련 문제는 없었다. 자료형도 최대 100,000 * 1000 = 1,00..
1463번-1로 만들기
문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근방법 1) 접근 사고 X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 이런 형식으로 문제에서 재귀함수로 구현하면 구현하기 쉽게 힌트를 준다. 이런 방식을 완전탐색으로 풀려고 접근하여 각각의 경우에서 수 많개의 경우의 수로 분할 되기 때문에 시간초과가 나므로 시간복잡도를 줄여야 하는 문제임을 알 수 있다. 2) 시간 복잡도 memorization 기법을 사용한 DP로 접근 3) 배운 점 memorization을 활용해서 탑다운 방식의 알고리즘을 구현해..
9461번-파도반수열
문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 접근방법 1) 접근 사고 문제에서 보면 누가봐도 규칙을 찾으라고 예시까지 친절하게 준다. 2) 시간 복잡도 완전탐색으로는 구현할 방법이 떠오르지 않는 문제. 삼각형의 예시를 보면서 점화식을 찾아야 하는 문제이다. 3) 배운 점 문제에서 n은 100까지 인데 문제를 보면서 규칙을 찾다보면 점화식이 cache[n] = cache[n - 2] + cache[ n - 3]인걸 알 수 있다. 그러므로 숫자..
1003번-피보나치함수
문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 접근방법 1) 접근 사고 피보나치 함수에서 재귀되는 경우에 0과 1이 몇 번 나오는지 물어보는 문제이나 반복된 재귀를 사용할 경우 시간초과 발생 2) 시간 복잡도 시간복잡도를 줄이기 위해 공통된 규칙이 있는 DP 방법을 탐색 n= 0 일 때 zero는 1개 나오고 one은 0개 나온다 n= 1 일 때 zero는 0개 나오고 one은 1개 나온다 n= 2 일 때 zero는 1개 나오고 one은 1개 나온다 n= 3 일 때 zero는 1개 나오고 one은 2개 나온다 n= 4 일 때 zero..
10816번-숫자카드2
문제 https://www.acmicpc.net/status?user_id=skaguq4270&problem_id=10816&from_mine=1 채점 현황 www.acmicpc.net 접근방법 1) 접근 사고 https://hyeophyeop.tistory.com/18 문제와 같습니다. 다만 갯수를 추가 해줘야 하므로 equal_range방식 또는 단순 구현으로 풀이를 해야한다. 2) 시간 복잡도 https://hyeophyeop.tistory.com/18 참조 3) 배운 점 복습하는데 좋았다! 4) PS 3가지 방법으로 구현해보았습니다. equal_range로 구현할 때 이유는 모르겠으나 배열을 사용하여 연산하니 오답처리를 받아서 Vector를 활용하는 방법으로 변경했습니다. 아무래도 메모리를 확보하..
10815번-숫자 카드
문제 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 접근방법 1) 접근 사고 n의 카드들이 있을때 m의 카드들이 n의 카드들에도 있는지도 확인하면 되는 문제였습니다. 이진 탐색을 활용하면 쉽게 해결할 수 있는 문제 입니다. 2) 시간 복잡도 n과 m의 카드의 길이가 500,000이므로 완전탐색을 돌리면 25,000,000,000,000의 연산이 일어나므로 시간복잡도를 줄여야 하는 문제였습니다. 3) 배운 점 두 ..
7453번-합이 0인 네 정수
문제 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 접근방법 1) 접근 사고 주어진 배열이 4개이고 탐색을 해야 하는 문제이므로 2개의 배열씩 짝지어서 n^2으로 조합을 맞춘 뒤에 문제에서 주어진 조건이 a, b, c, d의 배열 4개의 합이 0이어야 하므로 더한 배열에서 이분 탐색을 실시하면 되는 문제였습니다. 2) 시간 복잡도 가장 단순하게 4개의 배열이니까 n^4으로 문제를 풀면 n은 4000이고 N의 4승이므로 64,..
1300번-K번째 수
문제 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의 크기 때문에 완전탐색으로는 시간초과가 발생하는 문제이기 때문에 시간복잡도를 줄여야만 하는 문제였다. 이 문제의 탐색 기준은..
15732번-도토리숨기기
문제 https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 접근방법 이 문제는 어떤 것을 탐색 기준으로 삼아야 할 지 어려웠던 문제였다. 탐색 기준은 "박스의 최대 길이"로 설정하여서 이분 탐색을 수행하였다. 박스의 최대 길이와 규칙에서 더 짧은 기준을 선정하여 check 함수 탐색의 right값을 설정하였다.(앞에서 부터 갯수를 세는 문제 조건) 그 이후 mid ..
이분탐색 구현 팁 및 반환값 줄이기(부제: 공부하며 정리하는 생각들)
공부하면서 참조한 자료 1.종만북 2. https://blog.naver.com/jinhan814/222156334908 이분 탐색, 파라메트릭 서치 안 헷갈리는 TIP 예전에 종만북을 읽으면서 아래 글을 쓴 적이 있습니다. 아래 글에는 반복문 불변식을 이용해 lower_bound,... blog.naver.com 이분탐색은 문제에서 주어지는 탐색 값의 기준을 찾는 것이 문제이다. 예를 들어 1부터 10억cm의 길이의 자를 분할해서 최소 5개의 개수로 나누고 싶은데 이 때 "분할하는 경우에 가장 큰 분할 길이를 구하시오" 같은 문제에서 분할하는 길이를 구하면 되는 문제이다. 알고리즘에 관련된 설명과 강의는 나보다 뛰어나신 분도 너무 많고 작성하시는 분도 너무 많기에 넘어가고 이분탐색을 구현할 때 구현의 ..
16434번-드래곤앤던전
문제 https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 접근방법 n의 단위가 100,000만 이므로 n^2의 알고리즘은 시간초과가 발생한다는것을 깨닫고 O(logn으로 시간복잡도를 줄여야 하는 문제란걸 문제의 조건을 읽고 알아야 하며 H의 범위가 1,000,000인데 최대 연산이 발생할 경우 INT의 범위를 초과하기에 자료형을 long long으로 설정해줘야 하는 문제이다. 문..
2110번-공유기설치
문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 접근방법 일반적인 이분탐색 문제와 유사하지만 기준으로 정한 거리(mid)값의 변화를 측정하기 위한 이전 인덱스를 변경하는 35번째 줄에서 약간의 구현력이 필요했던 문제였습니다. 그 외에는 일반적인 이분탐색 문제였습니다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ..
1654번-랜선자르기
문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 접근방법 분할하였을 때 랜선의 개수가 n개 이상으로 만들어야 하는 경우에 랜선의 길이를 최대로 결정해야 하는 문제였습니다. 그렇기 때문에 이 문제에서는 탐색을 해야 하는데 n의 개수가 10000개 이므로 최악의 경우 100,000,000번의 연산이 발생하게 되므로 시간초과가 발생하여 O(logn)으로 시간복잡도를 낮춰야 하는 문제였습니다. 그러므로 이분탐색을 활용..
6236번-용돈관리
문제 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 접근방법 https://hyeophyeop.tistory.com/6 백준의 기타레슨과 매우 유사한 문제입니다. mid값을 어떻게 잡는가가 핵심이었던 문제였는데 저는 "현우가 당일날 사용할 수 있는 금액"으로 기준을 삼고 left값과 right값을 결정하였습니다. left값은 현우가 당일 사용하는 금액이 기준치보다 작으면 안됩니다. 왜냐하면 인출금액 K를 최소화하기로 했기 때문입니다. 그래서 lef..
2343번-기타레슨
문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 접근방법 이분탐색에서는 비교대상 (저의 코드에서는 mid 변수가 이것을 의미합니다.)을 어떻게 설정해줘야 하는것이 가장 중요합니다. 저는 "블루레이의 크기"를 mid 값으로 설정하였습니다. 예시를 들자면 블루레이의 크기를 10으로 설정하고 각 레슨들(arr의 값들)의 크기를 더해주면서 10을 넘을 경우 cnt값을 올려 총 블루레이의 갯수에 따라 left값과 right을 변경하였습니다. 이 문제의 주..
2512번-예산
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 접근방법 https://hyeophyeop.tistory.com/2?category=1003847 와 유사한 문제 입니다. 문제 접근을 위한 시간복잡도 계산, 자료형 설정부터 이분 탐색을 위한 범위 지정까지 유사합니다. 차이점은 이분탐색을 시작하는 while문 안에서 기준값 mid를 활용하여 arr에 대한 값들의 비교 연산만 다릅니다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12..
2805번-나무자르기
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 접근방법 이 문제는 n이 1000000이므로 완전탐색처럼 모든 케이스의 경우를 탐색할 경우 시간초과가 발생한다. 적어도 O(logn)의 시간복잡도로 줄여줘야 하는 문제다. 문제에 따라 적어도 m개의 나무를 가지기 위한 기준값을 정해주어야 한다. 기준값은 left와 right를 이용해서 중간값을 정해주는데 left와 right의 정의는 나무의 최소길이부터 최대..