본문 바로가기

Dev

 (86)
[백준 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를 예시로 생각해보..
[백준 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개의 숫자 등장 배열을 이용하면 빠르게 처리할 수 있다. 들어갈 수 있는 숫자를 찾았다면 숫자 등장 배열에 등장 처리를 해준 뒤에, 스도쿠 배열에도 해당 값을 채운 ..

티스토리툴바