본문 바로가기

Dev/BOJ

 (63)
[백준 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에 병합할 수 있고 같..
[백준 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 테이블이 필요하게 될 것이고, 이는 메모리 초과에 이른다.   그렇기 때문에, 비트 마스킹을 통해서 모든 경로를 저장하는 것이 아닌 방문 정보(숫자의 등장 정보)만을 저장해준다. 결국 필요한 것은 모든 숫자를 이용했는가를 판단하는 것이기 때문에 모든 경로가 저..
[백준 1202] 보석 도둑 그동안 포트폴리오랑 자기소개서를 작성하느라 공부를 많이 하지 못했는데, 어느정도 틀은 완성한 것 같아서 조금 여유가 생겼다. 아직 고칠 부분이 많지만 이제 다시 공부를 병행할 수 있을 것 같다. 더군다나 알고리즘 문제는 부트캠프 최종 프로젝트 기간동안 손을 놨다가 오랜만에 푸는 것이고, 이렇게 내일배움캠프가 아닌 카테고리에 개별 포스트로 작성하는 것도 처음이기 때문에 감회가 새롭다.   문제가 심플하면서 묻고 있는 것이 명확하다. 그런데 알고리즘 문제를 너무 오랜만에 풀었더니 이 문제에서도 꽤 난항을 겪었다. 당연히 보석과 가방 리스트를 그대로 이용하게 되면 절대 제한 시간 안에 풀 수 없다. 그래서 가방을 내림차순으로 정렬하고, 우선순위 큐를 통해 보석을 가치가 크면서 무거운 보석이 먼저 나오도록 해두..

티스토리툴바