본문 바로가기

Dev/BOJ

 (48)
[백준 1799] 비숍 백트래킹 문제다. 그래프 이론이나 탐색 유형의 문제는 곧 잘 푸는 편인데, 이건 핵심 아이디어가 바로 떠오르지 않아서 꽤 많은 시간을 소요했다. 브루트 포스를 활용하면 O(2^(n^2))에 해당하므로, 풀 수가 없다.  그래서 처음 시도한 방법은 그리디 알고리즘이었다. 비숍을 놓을 수 있는 빈칸 배열을 저장해 두고, 각각 대각선을 탐색해서, 해당 칸에 비숍을 놨을 때 놓을 수 없게 되는 칸의 수를 셌다. 그리고 이를 우선순위 큐에 집어넣고, 손실이 가장 적은 칸부터 하나씩 채워보는 방법을 썼다. 몇 가지 직접 떠올린 케이스들에 대해서는 꽤나 잘 먹혔지만, 이 방법은 시간복잡도만 우선했을 뿐, 최적해 찾는 것을 보장할 수 있느냐를 스스로 증명하지 못했다. 결과는 아니나 다를까 중간에 틀렸습니다를 받았다. ..
[백준 1647] 도시 분할 계획 심플한 MST(Minimum Spanning Tree, 최소 신장 트리) 문제다. 간선의 수가 최대 1,000,000으로 그리 크지 않아서 O(E logE)인 Kruskal 알고리즘으로 해결했다. Kruskal 알고리즘을 사용하기 위해서는 경로 집합에 해당 간선이 포함되어 있는지를 확인해야 하므로, Union-Find 알고리즘을 구현해서 빠르게 판별할 수 있도록 했다. 일반적인 MST와 조금 다른게 있다면 두 개의 MST를 만들어야 한다는 점인데, 이는 Union의 수가 두 개일때까지만 Kruskal 알고리즘을 진행하는 것으로 구현할 수 있다. 전형적인 MST 유형인데다, 디테일한 구현 요소도 없어서 그 외에는 크게 신경쓸 건 없었던 것 같다. #include #include using namespace..
[백준 1644] 소수의 연속합 심플한 투 포인터 문제이다. [1, N] 구간 내에 있는 모든 소수를 구해 배열로 만든다음, 투 포인터를 활용해 제일 작은 소수부터 차례대로 탐색해 나가면 된다. 먼저 소수 배열부터 만드는데, N이 최대 4,000,000까지 될 수 있으므로 O(n)인 방법으로 소수를 판별해서는 안된다(각 판별마다 O(n)만큼 걸리는데 이를 1~n까지 반복해줘야 하기 때문). 나는 약수를 제곱근까지만 탐색하고, 2의 배수와 3의 배수는 따로 처리해 최적화 하는 방법을 사용했다. 이는 O(n^0.5)에 해당하며, 약수 탐색 간격이 6이기 때문에 실질적으로는 더 빠르다. 물론, 범위가 크기 때문에 에라토스테네스의 체를 사용해도 무방하다.  소수 판별하는 로직을 작성해, [1, N] 구간 내의 소수 배열을 완성했다면 제일 앞부..
[백준 17387] 선분 교차 2 기하 알고리즘 문제이다. 처음에는 선분의 양 끝 점을 알고 있으므로, 두 개의 1차함수로 만들어 교점을 구해 그 점이 선분위에 있는지 찾는 방법을 사용했다. 두 함수의 기울기가 같을 때만 따로 처리해주었고, 문제에 있는 예제와 다양한 반례들을 넣어봐도 모두 바른 답이 나왔으나 정작 코드를 제출하면 3%에서 틀렸습니다가 발생했다. 아무래도 x의 증분 및 y의 증분을 계산할 때 실수 자료형을 사용해야 하고, 부동 소수점 오차 때문에 문제가 생기는 것 같았다. 그래서 double형을 사용하지 않고, 분수 꼴의 자료형을 커스텀해볼까 하다가 연산 도중에 그럼에도 분모 혹은 분자가 long long의 범위를 넘어갈 수 있어 패스했다. 그 다음엔 오차 범위 이내의 차를 보이면 같은 것으로 취급해 부동 소수점 오차를 ..
[백준 14003] 가장 긴 증가하는 부분 수열 5 일전에 풀었던 가장 긴 증가하는 부분 수열 2 문제에서 한 단계 더 나아간 문제이다. 그 때의 풀이처럼 DP와 이진탐색을 골자로 진행한다. [백준 12015] 가장 긴 증가하는 부분 수열 2 (tistory.com)  [백준 12015] 가장 긴 증가하는 부분 수열 2아마 알고리즘을 따로 공부했거나, 학부 과정에서 컴퓨터 알고리즘 과목을 수강했다면 익숙할 LIS 문제이다. 대표적인 DP 문제인데, 직관적으로 떠올릴 수 있는 형태의 DP 알고리즘의 시간복잡도winterry.tistory.com  저 때와 비교해서 달라진 것은, 결과로 얻어지는 LIS를 출력해야 한다는 점이다. 저 포스트에서도 작성했듯이, 해당 풀이에서는 최종적으로 얻어지는 LIS의 길이만 알 수 있을 뿐 실제 LIS의 구성에 대한 정보는 ..
[백준 13460] 구슬 탈출 2 그래프 탐색 문제다. 최소로 움직이는 횟수를 구해야 하니 BFS가 유리한 측면이 있으나, 최대 깊이가 10으로 그다지 깊지 않고 오늘따라 recursive call이 땡겨서 DFS로 구현했다.  문제에 제시되는 그대로 구현하는 시뮬레이션 문제이기도 해서, 복잡한 로직은 필요하지 않다. 나는 구슬을 움직이는 함수를 먼저 만들었다. 보드의 크기가 컸다면 미리 벽의 좌표들을 저장해두고 이진 탐색으로 구슬이 이동할 위치를 결정했을 것 같지만, 보드의 세로와 가로 크기는 둘다 최대 10으로 상당히 작다. 그래서 구슬의 위치로부터 정해진 방향으로 선형 탐색을 통해 구슬이 멈출 위치를 찾도록 했다. 구슬이 멈출 위치를 찾았다면, 기존 구슬의 위치는 빈 공간으로 만들어 주고 구슬이 구멍으로 빠지는 경우인지 검사한다. ..
[백준 12015] 가장 긴 증가하는 부분 수열 2 아마 알고리즘을 따로 공부했거나, 학부 과정에서 컴퓨터 알고리즘 과목을 수강했다면 익숙할 LIS 문제이다. 대표적인 DP 문제인데, 직관적으로 떠올릴 수 있는 형태의 DP 알고리즘의 시간복잡도는 O(n^2)로 이 문제를 풀기에는 부적합하다. 접근 방식을 조금 바꿔야 하는데, 나는 DP 문제에 약한 편이라 아무것도 모르는 체로 이 문제를 접했다면 발상에 꽤나 애먹었을 것 같다.  먼저 시작은 O(n^2)인 알고리즘에서 매번 dp[0]~dp[i-1]까지를 모두 확인하고 싶지 않다는 생각에서 출발한다. LIS를 구성하기 위해 배열을 탐색한다고 할 때, 앞서 나온 LIS의 가장 마지막 원소보다 탐색 중인 원소가 더 크다면 LIS에 바로 추가하면 된다는 것은 자명하다. 하지만 LIS의 가장 마지막 원소보다 탐색 ..
[백준 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를 예시로 생각해보..

티스토리툴바