본문 바로가기

Dev

 (90)
[백준 11049] 행렬 곱셈 순서 DP 문제이다. 처음에 문제의 제목을 보고 슈트라센 알고리즘 문제인가 했는데, 열어보니 전혀 다른 문제였다. 어떤 수학적 원리에 의해 그리디 알고리즘으로 풀어낼 수도 있지 않을까 했는데, 고민해봐도 방법이 보이지 않아서 결국 정직하게 DP를 이용해서 해결했다.  행렬이 N개 있다고 할 때, i번째 행렬부터 j까지의 행렬 곱셈 연산 횟수의 최솟값을 dp[i][j]이라고 두었다. 이 때 이 값을 구하기 위해서는 i~j번째 행렬을 두 부분으로 나누어 dp[i][mid] + dp[mid+1][j] + i번째 행렬의 행 * mid번째 행렬의 열(=mid+1번째 행렬의 행) * j번째 행렬의 열 값으로 구할 수 있을 것이다. 이 때 mid 값은 i부터 j까지 모두 확인해야 한다(만약 행렬 ABCD를 예시로 생각해보..
[백준 9328] 열쇠 그래프 탐색 문제로 DFS나 BFS 등으로 풀 수 있다. 열쇠 처리를 구현 해주어야 하는데, 종류가 알파벳의 갯수인 26가지로 한정되어 있으므로 bool 배열을 이용해도 되고, 비트마스킹을 이용해도 된다. 나는 비트마스킹을 이용했다.  일단 일반적인 그래프 탐색 문제랑은 조금 다르게 빌딩의 밖에서 시작하고, 가장자리를 통해 빌딩 안팎을 드나들 수 있다는 조건이 추가로 붙어있다. 따라서 입력 받을 때에 입구 정보를 따로 저장해두고 이를 이용할 수 있게 하는 것이 효율적이다. 그 다음에는 평범하게 탐색을 진행한다. 내 경우에는 스택과 DFS를 사용해서 탐색을 진행했다. 탐색 과정에서 가장 먼저 해야하는 것은 방문 여부 검사이다. 나는 이를 위해 처음에는 XOR 연산을 이용하려 했다. 그렇게 하면 현재 열쇠 ..
[백준 7453] 합이 0인 네 정수 투포인터나 자료구조를 이용해서 푸는 문제. 배열의 크기 n은 최대 4,000으로 브루트 포스로는 절대 풀 수 없다. 로직 자체는 금방 떠올랐는데, 최적화 문제로 시간을 많이 썼다.   로직은 두 가지를 적용해 볼 수 있다. 먼저 투 포인터를 이용하는 방법이다. A, B, C, D 배열을 두 쌍으로 나누어 각각의 값을 교차시켜 더했을 때 나오는 결괏값 배열을 생성한다(O(n^2)). 그리고 생성된 두 합 배열을 정렬한다(O(n log n)). 이후엔 투 포인터를 이용해 하나의 배열은 시작점, 하나의 배열은 끝점부터 탐색하며 0이 되는 값을 찾아 나간다.(O(n^2)) 이때, 종료조건은 둘 중 한 배열을 가리키는 포인터가 반대쪽 끝에 도달했을 때로 설정해 두고, 더해서 0이 되는 모든 경우를 끝까지 탐색할 ..
[백준 2239] 스도쿠 단순 구현문제이다. 직관적으로 떠오르는 로직을 그대로 적용하게 되면 자연스럽게 백트래킹과 적당한 분기처리를 통해 풀게 된다. 탐색시간을 최대한 줄이기 위해서, 나는 가로줄, 세로줄, 3*3칸에 대해서 특정 숫자가 등장했는지 여부를 저장해두는 배열을 따로 생성해 이용했다.  본격적인 로직도 심플하게 작성했다. 빈 칸의 위치를 모두 저장해놓은 리스트를 만들고, 이를 바탕으로 백트래킹을 시작한다. 인덱스가 depth 값인(백트래킹 하는 함수의 파라미터)  빈 칸 정보를 가져와서 1~9까지 들어갈 수 있는 숫자를 찾는다. 이 과정은 미리 생성해둔 3개의 숫자 등장 배열을 이용하면 빠르게 처리할 수 있다. 들어갈 수 있는 숫자를 찾았다면 숫자 등장 배열에 등장 처리를 해준 뒤에, 스도쿠 배열에도 해당 값을 채운 ..
[백준 2166] 다각형의 면적 약간의 수학을 이용하는 단순 구현 문제이다. 처음에 헤른의 공식을 이용해 한 점을 정해두고 두 점을 한 칸씩 옮겨가며 각각 삼각형의 넓이를 구해 모두 더하는 방법을 썼다가 틀렸습니다를 받아서 조금 헤맸다. 그래서 문제를 가만히 쳐다보니까 볼록 다각형임을 보장할 수가 없는 상태여서 해당 풀이는 바로 폐기하게 되었다. 주어지는 좌표의 최대 갯수가 그리 많지 않기 때문에 신발끈 공식을 이용해서 심플하게 해결했다. #include #include using namespace std;typedef pair point;int main() { int n; cin >> n; point pointArr[10001]; double sum1 = 0; double sum2 = 0; for(in..
[백준 12100] 2048 (Easy) 단순 구현 문제다. 입력 값으로 주어지는 보드의 크기가 상당히 작은 것에서 눈치챌 수 있겠지만 결국 모든 케이스를 탐색해주어야 한다. 나는 탐색은 DFS로 처리해주었고, 단순 구현 부분을 신경써서 작성했다.  각각의 방향으로 움직일 때 보드를 움직이는 코드를 작성해주어야 하는데, 보자마자 떠오르는 직관적인 로직을 그대로 작성하면 된다. 문제에서 주어지는 조건들을 모두 if else 분기처리해서 해결하려 하면, 안 그래도 긴 코드가 더 길어지고 까다롭기 때문에 나는 스택을 이용했다. 움직이려는 방향이 가로 방향이라면 행 단위로, 세로 방향이라면 열 단위로 한 줄씩 계산한다. 해당 줄에서 목적 방향에 가까운 칸부터 하나씩 확인해서 숫자가 존재한다면 스택을 확인한다. 이 때 스택의 top에 병합할 수 있고 같..
Cannot figure out how to save this field into database. You can consider adding a type converter for it. 오류 및 Room과 Enum 타입 평소처럼 Room을 사용 중이었는데, DB에 내가 만든 Entity의 필드를 저장할 수 없다는 오류가 떴다. 분명히 나는 DB에서 기본적으로 지원하는 타입의 필드들만 사용한 것 같은데 좀 당황스러웠다.   의심되는 것은 물론 Date 타입이었다. 예전에 MySql을 이용할 때는 타임스탬프를 넣을 수 있었던 것 같은데, 내가 잘못 기억하는 것인지 Room에서만 지원하지 않는 것인지 좀 헷갈렸다. 그래서 혹시나 해서 공식 문서를 뒤적거리다 보니까 이런 게 떡하니 적혀있었다.   TypeConverter를 사용해야 하는 복잡한 데이터 타입으로, Date를 예시로 들고 있다... 처음엔 그냥 직접 리눅스 시간으로 변환해서 넣고 타입을 Long으로 바꿀까하다가, 그래도 공식 문서 권장사항은 따라야지 싶어서 Typ..
[백준 1509] 팰린드롬 분할 DP로 시작해서 DP로 끝나는 문제이다.   먼저 팰린드롬 분할 조합 중 최솟값을 구하는 로직이 필요하다. 이는 문자열의 특정 위치에서의 팰린드롬 분할 개수의 최솟값을 저장할 DP 배열을 만들어 구할 수 있다. 일단 dp[i]은 dp[i-1]+1이 될 수 있다. 직전 문자열까지의 최솟값에 새로 더해지는 문자를 하나의 팰린드롬으로 보는 경우이다. 하지만 문제에서 요구하는 것은 최솟값이므로, 앞서 등장한 문자열과 새로 더해지는 문자를 함께 이용해서 팰린드롬을 만들었을 때의 분할 개수가 더 적지는 않은지 확인해야만 한다. 그러니까 [i-1, i] 구간이 팰린드롬인지 확인하고, 팰린드롬이라면 dp[i-2]+1이 최소가 될 수 있는지 확인하고, 같은 방식으로 [i-2, i], [i-3, i], ..., [0, i..

티스토리툴바