본문 바로가기

전체 글51

[백준] 1149 : RGB거리 (JAVA) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net Solution dp 문제인데 삽질을 했다... 아래와 같이 간단히 생각하면 금방 점화식을 도출할 수 있다 R G B house[0] house[0][0] house[0][1] house[0][2] house[1] Math.min(house[0][1], house[0][2]) + house[1][0] Math.min(house[0][0], house[0][2]) + house[1][1] Math.min(house[0][0], house[0].. 2022. 7. 28.
[백준] 9663 : N-Queen (JAVA) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. Solution 너무 유명한 알고리즘이라 퀸이 어떻게 움직이는 지도 써져있지 않다..(^^) 퀸은 상하좌우대각선 8방향으로 움직인다. 2차원 배열을 이용해도 되지만, index를 열, arr[index]를 행으로 하는 1차원 배열로 푸는게 더 간단하다. 위의 경우 arr = { 6, 4, 2, 0, 5, .. 2022. 7. 28.
[백준] 3273 : 두 수의 합 (JAVA) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 전형적인 LIS 문제이다. 하지만 역시 dp에 약한 나는 애를 먹었다... 문제를 읽고 처음 들었던 생각은, 수열의 i번째 값을 탐색할 경우 0 부터 i-1 값을 다 살펴보면 O(n^2) 으로 시간초과가 나지 않나? 하는 의문이었다. 게다가 i-1 과 i-2 만 살펴보는 피보나치와 달리 0 ~ i-1 을 매번 탐색하는 것은 dp 가 아니라고 생각했다. 결론적으로 O(n^2) 로 푸는 것.. 2022. 7. 28.
[백준] 11053 : 가장 긴 증가하는 부분 수열 / LIS (JAVA) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 전형적인 LIS 문제이다. 하지만 역시 dp에 약한 나는 애를 먹었다... 문제를 읽고 처음 들었던 생각은, 수열의 i번째 값을 탐색할 경우 0 부터 i-1 값을 다 살펴보면 O(n^2) 으로 시간초과가 나지 않나? 하는 의문이었다. 게다가 i-1 과 i-2 만 살펴보는 피보나치와 달리 0 ~ i-1 을 매번 탐색하는 것은 dp 가 아니라고 생각했다. 결론적으로 O(n^2) 로 푸는 것.. 2022. 7. 28.
[백준] 1912 : 연속합 (JAVA) 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 간단한 dp 문제인데 dp 문제는 족족 틀린다.. 연습이 많이 필요한 부분이다.. 간단하게 생각하면 쉬운 문제이다. 0 1 2 3 4 5 6 7 8 9 arr[i] 10 -4 3 1 5 6 -35 12 21 -1 dp[i] 10 6 9 10 15 21 -14 12 33 32 dp[i] 는 (i-1까지 누적된 dp) + (arr[i]) 와 arr[i] 중 큰 값을 저장한다. 이후 dp 에 저장된 값 중 가장 큰 것이 답이 된다. import java.util.*; impor.. 2022. 7. 28.
[백준] 2805 : 나무 자르기 (JAVA) 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net Solution 문제를 처음 확인했을 때 이분탐색으로 풀어야겠다 하는 생각이 들어서 금방 풀겠다 싶었는데 신경 써줄 것들이 조금 있었다. 입력 값의 범위가 크다는 것 조건을 충족하는 mid 중에 최대가 되는 mid 를 골라야 한다는 것 정수형 타입 할당되는 메모리의 크기 데이터의 표현 범위 byte 1바이트 -128 ~ 127 short 2바이트 -2^15 ~ (2^15 - 1) -32,768 ~ 32,767 int 4바이.. 2022. 7. 28.

티스토리툴바