겐지충 프로그래머

전체 글 검색 결과

해당 글 200건

알고리즘 풀이 - 백준 9095(1,2,3 더하기, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 개요 문제 링크는 여기를 참조 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제 이 문제를 완전 탐색(재귀)를 이용하여 풀 수도 있다. 그 방법은 여기를 참조 2. 풀이 이 문제는 DP로 해결 가능하다. 우선 두 가지 조건이 만족하는지 알아보자. 각 정수는 n으로 표기하여 이 자체가 변수로 하나의 State를 나타낸다. 정수 n을 1, 2, 3의 합으로 나타내는 방법은 아래와 같다. n = (n-3) + 3 n = (n-2) + 2 n = (n-1) + 1 즉, 작은 문제들인 n-3, n-2, n-1을 반복하여 사용하고 해당 최적 결과값이 그대로 사용되므로 DP의 두 가지 조건인 Overlapping Subpro..

알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 6. 21:54

알고리즘 풀이 - 백준 11727(2xN 타일링2, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 비슷한 문제인 11726번(2xN 타일링)은 여기를 참조 1. 문제 문제 링크는 여기를 참조 이번 문제는 11726번과 비슷한데 거기에 타일이 하나 추가되었다. 2xn의 타일을 2x1, 2x2, 1x2의 타일로 채울 수 있는 경우의 수를 구하는 문제이다. 2. 풀이 이 문제는 DP로 풀어낼 수 있다. 이전 11726번과 같으나 2*2가 추가되어 n의 상태를 증가시켜 가며 채운다는 것만 변한 것이다. 따라서 2*n을 채우려면 다음과 같은 3가지 경우의 수가 있을 것이다. ⅰ. 2*(n-1)에서 2*1로 세로로 하나 채우는 경우 ⅱ. 2*(n-2)에서 1*2로 가로로 두개 채우는 경우 ⅲ. 2*(n-2)에서 2*2로 하나 채우는 경우 따라..

알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 6. 19:29

알고리즘 풀이 - 백준 11726(2xN 타일링, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 문제 문제 링크는 여기를 참조 이 문제는 2x1 또는 1x2 타일로 2xn타일을 채우는 문제이다. 2. 풀이 이 문제는 2*n타일로 채운다는 것을 통해 좋은 힌트를 얻을 수 있다. 세로 길이가 2로 정해져 있기 때문에 세로를 채우려면 가로로 2개를 넣거나 세로로 1개를 넣으면 된다. 이 때, 가로로 2개를 채워서 넣게 되면 2*2만큼이 채워지게 되고 세로로 한 개를 채워 넣으면 2*1개가 채워진다. 여기서 DP로 풀 수 있다는 것을 알 수 있는데, 만약 2*n을 채울 수 있는 방법에서 n은 하나의 state가 되는 변수이고 더 작은 n만큼의 타일을 채운 것에서 규칙을 부여할 수 있다는 것을 알 수 있다. 위에서 적었듯이 세로를 채..

알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 6. 10:39

알고리즘 풀이 - 백준 1463(1로 만들기, DP)

관련글 Dynamic Programming 관련 포스팅은 여기를 참조 1. 문제 문제 링크는 여기를 참조 간단하게 설명하여 1 ~ 1,000,000 까지 숫자 중 하나를 입력 받아 해당 숫자에서 1을 빼거나, 2 또는 3으로 나누는 작업을 반복하여 1이 되게 하려면 몇 번의 연산이 필요한지 구하는 문제이다. 2. 풀이 우선 이 문제는 DP로 풀 수 있다. DP로 풀 수 있는지 어떻게 알 수 있을까? DP인지 아닌지 확인하려면 우선 2가지 조건이 만족되는지를 알아야 한다. 그 조건은 다음과 같다. 1) Overlapping Subproblems(겹치는 부분 문제) 2) Optimal Substructure(최적 부분 구조) 예를 들어, 숫자 5를 1로 만들기 위해서는 아래와 같은 방법이 있을 것이다. 5 ..

알고리즘 풀이(Problem Solving)/Dynamic Programming 2021. 1. 5. 20:53

알고리즘 - Dynamic Programming(동적 계획법)

1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 그래서 혹자는 DP가 아닌 '기억하며 풀기'라고 부르기도 한다. 2. DP를 쓰는 이유 왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 ..

자바 프로그래밍/알고리즘(Algorithm) 2021. 1. 5. 15:08

자료구조 - 접미사 배열(Suffix array, 맨버-마이어스 알고리즘)

1. 접미사 배열 접미사 배열은 문자열 형태의 데이터가 갖는 모든 접미사를 사전 순 정렬한 것을 의미한다. 접미사 배열은 문자열 검색, 전문 검색 등에 활용하기 위해서 많이 쓰인다. 접미사 배열로 검색하면 아래와 같은 예시를 가장 많이 볼 수 있다. 이를 통해 간단히 이해해보자. 기존 배열(original array) 접미사 배열(suffix array) banana a anana ana nana anana ana banana na na a nana 이해하기 어렵지 않다. banana 라는 문자열의 모든 접미사는 자기 자신을 포함해, 뒤에서 부터 한 글자씩 잘라낸 부분이라고 보면 된다. 위의 표를 보면 좌측의 기존 접미사를 저장한 배열이 정렬 후 우측과 같이 정렬 상태가 됨을 알 수 있다. 이제 보니, ..

자바 프로그래밍/자료구조(Data Structure) 2020. 12. 30. 22:02

알고리즘 - 진법 변환하기(10진수 - N진수)

1. 개요 수학 교육 과정에서 배운 진법 변환을 코드로 구현해보자. 10진법에서 N진법으로, N진법에서 10진법으로 변환하는 방법을 알아본다. 수학에서 변환했던 방법을 생각하며 아래의 진법 변환을 알아보자. 2. 10진법에서 N진법으로 변환하기 10진법에서 N진법으로의 변환은 매우 쉽다. 수학으로 생각하면 10진법으로 표기된 숫자를 N으로 나누어 그 나머지를 표시하고 더 이상 나눌 수 없을 때까지 반복하여 표기하는 방식이다. 예를 들어 10진법 5를 3진법으로 바꾼다면, 5를 3으로 나누면 나머지 2에 몫은 1이다. 최종 나누어진 값부터 표시하므로 12가 된다. 이를 자바 코드로 살펴보자. public class Conversion { public static void main(String[] args)..

자바 프로그래밍/알고리즘(Algorithm) 2020. 12. 29. 17:55