SY DevLog

1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 동적 계획법을 통한 최장 공통 수열을 구하는 문제이다. 보통은 두 문자열의 LCS를 구하는데, 이 문제는 세 개의 문자열의 LCS를 구해야 한다. 아래는 LCS(Lowest Common Subsequence)를 구하는 방법에 대한 글이다. lotuslee.tistory.com/39?category=964787 LCS(Longest Common Subsequence) LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장..

동적 계획법(Dynamic Programming) 동적 프로그래밍, 다이나믹 프로그래밍 이라고도 한다. 동적 계획법이란 하나의 큰 문제를 작은 문제로 쪼개어서 문제를 해결하는 방법이다. 동적 계획법에서 가장 중요한 개념은 메모이제이션(Memoization)과 점화식이다. 메모이제이션(Memoization) : 동일한 계산이 반복될 때, 이전에 계산한 결과를 메모리에 저장하여 동일한 계산을 반복하는 것을 피하는 방법이다. 이전에 계산한 결과를 메모리에 저장하기 때문에 중복된 계산을 할 필요가 없으므로 속도가 빠르다는 장점이 있다. 그리고 동적 계획법에서는 이 메모이제이션을 위해 점화식을 세우는 과정이 필요하다. 동적 프로그래밍하면 가장 대표적인 예시가 바로 피보나치 수열이다. 피보나치 수열은 앞의 두 항의..

비트맵(Bitmap) 이미지 비트맵 이미지란, 이미지를 픽셀 단위로 저장하는 방식을 의미한다. 이미지를 확대했을 때 이미지가 계단 모양으로 된 것처럼 보이는 것을 한 번쯤 경험했을 것이다. 이는 픽셀 하나하나가 마치 계단처럼 보이기 때문으로, 비트맵 이미지에서 이러한 현상이 나타난다. 비트맵 이미지로는 JPEG, PNG, GIF 등이 있다. 벡터(Vector) 이미지 벡터 이미지란, 점, 선, 면을 수학적 연산을 통해 벡터로 표현하는 이미지를 말한다. 비트맵 이미지와 달리 이미지가 픽셀로 구성되는 것이 아니기 때문에 계단 현상이 없고, 이미지를 확대해도 꺠지지 않는다. 보통 로고를 만들 때 비트맵 이미지보다는 벡터 이미지를 사용한다. 일러스트에서 사용하는 .ai 확장자는 벡터 형식에 속한다. PNG(Po..

안드로이드 개발을 하다보면 어플리케이션에 이미지를 넣을 때 dp개념이 등장한다. 주로 안드로이드 디자인 측면에서 많이 사용되지만, 개발자가 알아두어도 도움이 될 것 같아서 글을 작성하게 되었다. dp가 무엇인지, 안드로이드에서는 왜 dp 개념을 사용하는지 알아보자. 우선, dp에 대해 설명하기 전에 pixel이 무엇인지 먼저 알아야 한다. 픽셀(pixel, px) 화소라고도 하며, 디지털 이미지를 나타내는 데 사용되는 최소 단위이다. 픽셀은 해상도와도 관련이 있는데, 동일한 이미지라 하더라도 픽셀의 수가 많은 것이 해상도가 더 높다. 아래에서 오른쪽 그림이 왼쪽 그림보다 1인치당 픽셀 수가 더 많으므로 해상도가 높다고 볼 수 있다. ppi는 pixel per inch -> 1인치당 픽셀 수를 의미한다. ..

10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 백준 2740번 : 행렬 곱셈을 응용한 문제이다. B의 범위가 매우 크기 때문에 단순히 2740번 문제에서 for문을 하나 더 추가해서 문제를 풀면 시간초과가 난다. 이 문제는 행렬을 곱하는 똑같은 과정을 반복하기 때문에 이미 한번 계산한 결과는 다시 재사용하면 계산 횟수를 줄일 수 있다. 따라서 분할과 정복 방법으로 문제를 해결하였다. 만약 B가 짝수라면, B번 행렬을 곱한 결과는 B/2번 행렬을 곱한 결과 * B/2번 행렬을 곱한 결과가 된다. 이 때 B/2번 행렬을 곱한 ..

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍으로 해결할 수 있다. dp[n][l][r] : n번째 빌딩을 세울 때, 왼쪽에서 보이는 빌딩의 수가 l개, 오른쪽에서 보이는 빌딩의 수가 r개가 되도록 건물을 배치하는 모든 경우의 수 먼저, 처음으로 빌딩을 하나 세웠다고 치자. 건물이 하나밖에 없으므로 왼쪽에서 보이는 건물의 수는 1개, 오른쪽에서 보이는 건물의 수도 1개가 된다. -> dp[1][1][1] = 1 그 다음으로 두번째 빌딩을 하나 세운다. 그러면 두 가지 중 하나이다. 왼쪽에..

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍으로 문제를 해결하였다. 메모이제이션을 위해 3차원 dp배열을 생성했다. int[][][] dp = new int[2*N+1][2*N+1][N+1]; 첫번째 인덱스는 몇일이 지났는지를 의미하고, 두번째 인덱스는 현재 시점에서 반알짜리 알약의 개수, 세번째 인덱스는 한알짜리 알약의 개수를 의미한다. dp[t][h][w] : t일이 지났을 때, 반알짜리 알약의 개수가 h개이고, 한알짜리 알약의 개수가 w개일 때 가능한 모든 문자열의 개수 점화식을 세우면 아래와 같..

2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 www.acmicpc.net dp[n][m] : n개의 수를 m개의 구간으로 나누었을 때 최대 합 arr[i] : 입력받은 수들을 저장 n번째 수가 m번째 구간에 포함되어 있는지, 포함되어 있지 않는지 두 가지 경우로 나눌 수 있다. - n번째 수가 구간 m에 포함되지 않은 경우 : dp[n][m] = dp[n-1][m] n-1번째 수가 구간 m에 포함된 경우의 최대 합(dp[n-1][m])과 동일하다. - n번째 수가 구간 m에 포함된 경우 : dp[n][m] = max(d..

안드로이드 개발을 하다보면 context를 접하게 된다. getApplicationContext(), getContext() 혹은 this 키워드를 통해서 메서드의 인자 혹은 클래스 생성자로 context를 넣어줘야 하는 경우를 자주 경험했을 것이다. 그렇다면 Context란 정확히 무엇일까? Context 등장 배경 일반적인 OS와는 달리, 안드로이드는 어플리케이션과 프로세스가 독립적이다. 독립적이기 때문에 프로세스가 종료되어도 어플리케이션은 실행 상태일 수 있다. 예를 들어, 서비스(Service)나 브로드캐스트 수신자(Broadcast Receiver)의 경우, 어플리케이션의 실행 여부에 관계 없이 백그라운드에서 작업을 할 수 있는 것은 이 때문이다. 이러한 안드로이드의 특징 때문에 프로세스와 어플..

안드로이드 애플리케이션을 구성하는 기본 요소 4가지를 안드로이드 4대 컴포넌트라고 한다. 이 4가지는 액티비티(Activity), 서비스(Service), 브로드캐스트 수신자(Broadcast Receiver), 콘텐츠 제공자(Content Provider) 이다. 안드로이드 4대 컴포넌트는 AndroidManifest.xml 파일에 그 정보가 보관된다. 액티비티(Activity) 애플리케이션에서 사용자에게 보여지는 화면을 담당하는 컴포넌트이다. 화면뿐만 아니라 화면에서 일어나는 사용자와의 상호작용도 액티비티가 관여한다. 여러 개의 액티비티가 모여서 하나의 애플리케이션을 구성한다. 매니페스트 파일에서 태그 형식으로 하나의 액티비티를 표현한다. 서비스(Service) 액티비티가 사용자와의 상호작용에 관여한..