본문 바로가기

분류 전체보기

 (159)
[백준 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..
[백준 1562] 계단 수 DP를 이용해야 하는 문제다. 일단 대강 로직을 떠올렸을때, 1번째 자리~N번째 자리에 이르기까지 각각 들어갈 수 있는 수의 범위인 0~9에 대하여 해당 지점까지의 '계단 수'의 수를 계속해서 저장해나가면 되겠다 싶었다. 그런데 문제 조건에서 0~9까지 모든 숫자가 등장해야 한다는 조건을 걸었으므로, 결국 계단 수가 형성되는 경로가 저장되어야만 한다. 따라서 직관적이고 단순한 DP 테이블을 떠올리면 크기가 최대 10*100*경로 집합의 수인 int 테이블이 필요하게 될 것이고, 이는 메모리 초과에 이른다.   그렇기 때문에, 비트 마스킹을 통해서 모든 경로를 저장하는 것이 아닌 방문 정보(숫자의 등장 정보)만을 저장해준다. 결국 필요한 것은 모든 숫자를 이용했는가를 판단하는 것이기 때문에 모든 경로가 저..
Unable to load class 'org.jetbrains.kotlin.gradle.plugin.mpp.pm20.KotlinCompilationData' 오류 Unable to load class 'org.jetbrains.kotlin.gradle.plugin.mpp.pm20.KotlinCompilationData' Compose나 ksp 같은 비교적 최신 기술들을 적용해 개인 프로젝트를 해보고 있는데, gradle 파일에서 dependency를 추가하다가 위와 같은 오류가 발생했다. 아무래도 ksp의 버전을 공식문서 그대로 사용했더니, 다른 빌드 환경에 호환되지 않는 부분이 있었던 것 같다.   내가 설정했던 ksp 버전은 위와 같은데, 일단 공식 문서에서 안내하는대로 먼저 내 코틀린 버전과의 호환부터 체크해보기로 했다.  쭉 살펴보니 코틀린 버전과, ksp 버전의 앞쪽 버전 넘버가 맞아야 동작하는듯 했다. 코틀린 1.9.0에 대응하는 버전은 아무래도 1.0..
[백준 1202] 보석 도둑 그동안 포트폴리오랑 자기소개서를 작성하느라 공부를 많이 하지 못했는데, 어느정도 틀은 완성한 것 같아서 조금 여유가 생겼다. 아직 고칠 부분이 많지만 이제 다시 공부를 병행할 수 있을 것 같다. 더군다나 알고리즘 문제는 부트캠프 최종 프로젝트 기간동안 손을 놨다가 오랜만에 푸는 것이고, 이렇게 내일배움캠프가 아닌 카테고리에 개별 포스트로 작성하는 것도 처음이기 때문에 감회가 새롭다.   문제가 심플하면서 묻고 있는 것이 명확하다. 그런데 알고리즘 문제를 너무 오랜만에 풀었더니 이 문제에서도 꽤 난항을 겪었다. 당연히 보석과 가방 리스트를 그대로 이용하게 되면 절대 제한 시간 안에 풀 수 없다. 그래서 가방을 내림차순으로 정렬하고, 우선순위 큐를 통해 보석을 가치가 크면서 무거운 보석이 먼저 나오도록 해두..

티스토리툴바