알고리즘
-
BOJ) 가장 긴 감소하는 부분 수열알고리즘/백준 2020. 8. 1. 23:47
가장 긴 감소하는 부분 수열 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 풀이 가장 긴 감소하는 부분 수열을 구하는 문제다. Longest Increasing Subsequence와 조건만 다른 Longest Decreasing Subsequence 문제다. LIS 문제의 조건을 반대로만 해주면 쉽게 풀 수 있다. 우선, int[] 배열 dp를 선언했다.그리고, 순회하는 인덱스의 다음 인덱스부터 n까지 돌면서 순회하고있는 인덱스의..
-
BOJ) 동전 2알고리즘/백준 2020. 7. 27. 23:57
동전 2 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 풀이 방금 전 포스팅한 LIC 문제보다 푸는데 조금 더 많은 시간이 걸렸다. 먼저, 동전 1과 다르게 k원을 만드는 최소 값을 구해야 한다는 조건이 까다롭게 느껴졌다. 또한, 만들 수 없는 경우 -1을 리턴해야한다는 부분을 간과했다. 마지막으로 고민한 부분은 점화식을 어떻게 세우는가였다. 우선 coin의 값이 뒤죽박죽일 수 있기 때문에, Arrays.sort를 통해 오름차순 정렬을 해주었다. 이후, 답이 될 dp[k]는..
-
BOJ) 가장 긴 증가하는 부분 수열 (LIS, Longest Increasing Subsequence)알고리즘/백준 2020. 7. 27. 23:51
가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 어제 푼 가장 큰 증가하는 부분수열 (BIS)와 유사한 문제다. 다른 점이 있다면, 최대 값을 구하는 것이 아니라 최대 길이를 구하는 것이다. 그래서, Math.max를 통해 값을 증가 시켰던 것과 달리, Math.max를 통해 카운트를 증가시켜준다. 먼저, 자신만 존재하는 부분 수열에 대해서 dp[n]에 1을 저장한다. 이후, 탐색을 통해 자신보다 큰..
-
BOJ) 가장 큰 증가 부분 수열알고리즘/백준 2020. 7. 26. 17:33
가장 큰 증가 부분 수열 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 풀이 다이나믹 프로그래밍 문제는 너무 어렵다.. ㅠㅠ 다른 문제 유형보다 생각을 조금 많이 요한다. 많은 실패를 겪고 답을 찾았다. 먼저, 각 index에서 취할 수 있는 가장 큰 증가 부분 수열의 합을 저장할 dp를 선언해준다. 이후 for문을 통해 index를 탐색하면서( i ) dp[i] 에 최대값을 저장한다. 최대값을 저장하는 과정은 0부터 해당 index 전 까지 for..
-
BOJ) 달팽이는 올라가고 싶다알고리즘/백준 2020. 7. 26. 17:27
달팽이는 올라가고 싶다 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 풀이 달팽이가 막대의 높이 V까지 올라가는 데, 걸리는 날을 구하는 문제다. A는 달팽이가 낮에 올라갈 수 있는 높이이고, B는 밤에 잠을 자는 동안 아래로 미끄러지는 높이다. 정상에 올라간 후에는 미끄러지지 않는다. 위의 조건으로 미루어 봤을 때, 막대까지 오르는 날 * A 만큼 위로 올라가고, (막대까지 오르는 날 -1) * B 만큼 아래로 미끄러진다. 잠을 자는 동안만 미끄러지고, 높이까지 올랐을 때는 미끄러지지 ..
-
BOJ) 로봇 청소기알고리즘/백준 2020. 7. 24. 22:47
로봇 청소기 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 푸는데 많은 시간을 소요했다. 현재 위치를 청소한다. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다. 네 방..
-
BOJ) 벽 부수고 이동하기알고리즘/백준 2020. 7. 23. 15:51
벽 부수고 이동하기 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 풀이 BFS 문제로, (1,1)에서 시작해서 (n,m)에 최소 경로로 도달하기 위해 몇 개의 칸을 밟는지 구하는 문제다. 처음에는 단순하게 visit을 좌표만 체크하면서 (2차원 배열) 답을 구해줬다. 50퍼센트 쯤 넘어갈 때 틀렸다고 뜨는 것을 보고, 벽을 허물고 이동한 경우와 벽을 허물지 않고 이동한 경우가 물린다는 것을 알아챘다. 그래서 visit 변수를 3차원 배열로 생성해주었는데, 벽을 한 번 허물었을 경..
-
BOJ) LCS알고리즘/백준 2020. 7. 23. 15:44
LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 이 문제를 통해 LCS 알고리즘을 처음 학습했다. LCS(Longest Common Subsequence)는 최장 공통 부분 수열을 의미하며, 두 수열이 주어졌을 때, 부분 수열이 되는 수열 중 가장 긴 것을 찾는 것이다. 이 문제에서는 알파벳으로 이루어진 두 문장이 주어졌으므로, 두 문자열에서 알파벳의 부분 수열이 공통으로 가장 긴 길이를 찾아야 한다. 문제의 예시를 통해 LCS 이론을 살펴보면 다음과 ..