Algorithm/Baekjoon Online Judge
-
[BOJ] 10986번: 나머지 합Algorithm/Baekjoon Online Judge 2022. 4. 27. 17:43
문제풀이 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 처음에는 누적합을 구하고 그 안에서 만들수 있는 조합에 대한 범위로 모든 경우를 살펴서 나머지가 0인 것을 찾았지만 이는 시간초과가 났다. 아무래도 2중 반복문을 써서 계속 배열에 접근하는게 문제였던 것 같다. 해결할 방식의 경우 다른사람의 풀이를 참고했는데 이해하기가 쉽지 않았다. 따라서 설명을 자세하게 적어보려고 한다. 주어진 입력이 다..
-
[BOJ] 12865번: 평범한 배낭Algorithm/Baekjoon Online Judge 2022. 4. 16. 15:17
문제풀이 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 가장 일반적인 냅색 문제이다. dp를 통해 해결할 수 있는데 생각보다 조건을 생각할 것이 많았다. 나의 경우 다이나믹프로그래밍 배열을 1차원으로 작성하는 것을 선호하는데 이 경우에는 2차원 배열로 먼저 작성했다. 2차원 배열의 행은 각 물건을 나타내며, 열은 무게를 나타낸다. 0번째 행, 0번째 열은 비워두기 때문에 (n+..
-
[BOJ] 9251번: LCSAlgorithm/Baekjoon Online Judge 2022. 4. 15. 00:22
문제풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 개의 문자열이 주어질 때 두 문자열에서 매치되는 가장 긴 문자열의 길이를 구하는 문제이다. 사실 어떻게 하면 풀 수 있을지 고민을 좀 했다. 생각보다 쉽게 방식이 안 떠올라서 이전에 계산한 값을 어떻게 하면 현재 계산에 적용할 수 있을지 방법을 알기위해 노력했다. 이 문제에서는 알파벳 하나가 어떤 알파벳과 매치될지 알 수 없다는 점이 가장 ..
-
[BOJ] 2565번: 전깃줄Algorithm/Baekjoon Online Judge 2022. 4. 13. 16:34
문제풀이 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 우선 전깃줄을 하나씩 보면서 그때까지 가질 수 있는 최대 전깃줄 개수를 구해야 한다는 것을 제일 먼저 생각해야한다. 그렇다면 최대 전깃줄 개수를 어떻게 구할 수 있을까를 생각해야한다. 두개의 전깃줄이 있을 때 A와 B에서의 위치를 (a1, b1), (a2, b2)라고 한다면 전깃줄이 교차되지 않기 위해서는 a1 a2 and b1 > b2 여야한다. ..
-
[BOJ] 11054번: 가장 긴 증가하는 바이토닉 부분수열Algorithm/Baekjoon Online Judge 2022. 4. 12. 21:00
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 풀이 백준 11053번 문제를 풀고 난 후 바로 도전한 문제여서 쉽게 해결 가능했다. 만약 안풀었다면 먼저 풀어보기! https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 ..
-
[BOJ] 11053번: 가장 긴 증가하는 부분수열Algorithm/Baekjoon Online Judge 2022. 4. 12. 20:51
문제풀이 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp를 활용해서 푸는 문제인 것은 알았지만 어떤식으로 해결해야할지 처음엔 와닿지 않았다. 입력받은 수열을 하나씩 검사하면서 그 때까지 가장 긴 수열을 dp에 저장해야한다는 것은 생각했다. 그 사이에서 수의 비교를 어떤 식으로 해나가야할지 감이 안잡혔지만, 결국엔 그냥 비교를 다 해보는 것으로 깨달았다. 이전에 ..
-
[BOJ] 2156번: 포도주 시식Algorithm/Baekjoon Online Judge 2022. 4. 11. 18:10
문제 풀이 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 3연속으로 시식할 수 없다는 조건이 제일 중요하다. 다이나믹 프로그래밍을 통해 해결할 수 있는데 첫번 째 포도주 잔부터 마지막까지 하나씩 보면서 해당 잔에서 마실수 있는 최대 양을 구하면 된다. 3연속 조건에 의해 매번 3가지 경우 중에 하나로 판별을 해야한다. 현재 잔을 i번째 잔이라고 하면 1. i번째 잔을 마시고 i-1번째 잔을 마셨을 때 i-3번째까지 마실 수 있는 최대 양의 합 ..
-
[BOJ] 10844번: 쉬운 계단 수Algorithm/Baekjoon Online Judge 2022. 4. 10. 23:12
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 처음에 생각했던 방식은 N이 1일 때 부터 시작해서 9, 17, 32,,,,순으로 개수가 증가하길래 dp[1] = 9로 정해두고 dp[N] = dp[N-1]*2 - N + 1 와 같은 식을 생각했다. 하지만 이렇게 코드를 작성했을 경우 틀렸습니다!가 표시,,,, 예를들어 N이 5일경우 내 식에 의하면 118이지만 답은 116이 나온다. 따라서 다른 코드를 생각했다. N이 1일때, 0 은 0가지 1, 2, 3, 4, 5, 7=6, 7, 8, 9 모두 1가지이다. N이 2일때, 뒤에 붙는 숫자를 기준으로 생각해보자..