알고리즘
-
사과와 바나나 (boj 3114)알고리즘 2020. 4. 17. 15:08오늘은 사과와 바나나 문제를 풀어봤어요 R * C 크기의 땅에 두 국가 A, B가 있어요. A나라는 Apple(사과)를 좋아하고, B 나라는 Banana(바나나)를 좋아해요. 각 땅은 1 * 1 격자로 쪼개어져 있고, 격자 한 칸에는 사과나무 혹은 바나나 나무가 심어져 있고, 각 생산량은 입력으로 주어져요. A 국가와 B국가는 불도저로 땅을 밀어버려서 국경선을 그으려고 해요. 국경선의 아래쪽은 A 국가, 윗 쪽은 B 국가의 땅이고, 불도저가 지나간 자리는 나무가 모두 사라져요. 불도저는 맨 왼쪽 위에서 출발하여 맨 오른쪽 아래에 도착할 때까지 이동하며, 한 번 이동할 때 한 칸 아래, 한 칸 오른쪽, 한 칸 오른쪽 아래 대각선으로 이동할 수 있어요. 이때 어떻게 하면 A 국가의 사과 생산량과 B국가의 바..
-
구간합 구하기알고리즘 2020. 4. 17. 14:21구간합을 O(n) 만에 구하는 알고리즘에 대해서 알아볼게요 위와 같은 수열이 있다고 하고 이들의 구간합을 구해볼게요 구간합을 구한다는 말은 랜덤으로 어떤 구간을 정하면 그 구간의 합을 딱딱 구하는걸 말해요 [0 - 3], [2 - 4] 를 예시로 구간합을 구해봤어요. 어떤 구간이 주어질때마다 수열을 loop 돌며 구하는 방법이에요. 이 방법으로 모든 구간의 구간합을 구하기 위해서는 O(n^2)이라는 시간이 필요해요 하지만 오늘 알아볼 방법은 O(n)의 방법이에요 하늘색 수열이 보이시나요? 이건 0번째 원소부터 자기 자신까지의 누적합을 구해둔 배열이에요 0번째 누적합은 2, 1번째 누적합은 2 + 5 = 7 2번째 누적합은 2 + 5 + 8 = 15 이렇게 누적합을 구해두면 특정구간의 합을 O(1)만에 구..
-
DFS 메모이제이션알고리즘 2020. 4. 15. 19:54오늘은 DFS 메모이제이션 기법에 대해 알아볼거에요 이 기법은 DFS 문제를 조금 더 최적화 시킨 기법으로, 개념 자체는 매우 간단해요 "한 번 갔던 곳의 DFS 결과 값을 저장해두고 나중에 이 곳에 다시 방문하면 또 탐색하지 말고 이 값을 재사용하자!" 라는 생각인거죠 메모이제이션 기법은 N이 커질수록 그 빛을 발하니 꼭 익혀두는게 좋아요 N * N 짜리 2차원 배열이 있다고 하고, 우리는 값이 점점 커지는 최대 경로를 구하는 문제가 있다고 합시다. 아래와 같은 배열의 경우에는 1 2 3 5 6 4 7 6 5 1 2 3 5 6 4 7 6 5 분홍색으로 칠해진 부분이 정답이 될거에요 일반적인 DFS로도 충분히 구할 수 있지만 그렇게 되면 계산의 중복이 심해져서 매우 느린 알고리즘이 될 수 있어요 여기서 ..
-
편집거리(boj 7620)알고리즘 2020. 4. 11. 02:45
최근 며칠동안 편집거리 문제 푸느라 엄청 고생했었어요 사실 쉽게 푸는 방법이 있었는데 편집거리(Hard) 로 풀어보고 싶어서 고집 피우다가 결국 실패했네요.. ㅠㅠ 학교 과제로 나온거라 기한이 있어서, 나중에 시간나면 하드로 다시 풀어보려구요 간단히 요약하자면 최대 17000 글자인 두 문자열 A, B 를 입력받게되면 문자열 A를 B로 만드는데 필요한 비용을 편집거리라고 해요 우리는 이 편집거리를 최소한으로 하는 방법을 찾으면 됩니다. 연산과 그 비용의 정의는 다음과 같아요 a 'n' : add 출력 문자열에 'n' 을 출력 ( 비용 : 1 ) d 'n' : delete 입력 문자열의 'n'을 삭제 ( 비용 : 1 ) m 'n' : modify 입력 문자를 'n'으로 수정 ( 비용 : 1 ) c 'n' ..