본문 바로가기
반응형

Algorithm/BAEKJOON145

[백준/C++] 숨바꼭질 4 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 예전에 풀었던 숨바꼭질와 거의 다를게 없는 문제다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 이동 시간이 항상 같으므로 BFS로 탐색을 시작해 첫 방문하는 경우가 항상 이동 시간이 가장 작다는 것을 알 수 있다. 여기서 다른 점은 어떤 경로로 이동을 했는지 출력도 해야한다. 그러므로 visited 배열을 만든 뒤 첫 방문을 할 경우 어떤 위치에서 이동했는지 저장을 한다면, 역으로 어떤 경로를 통해 왔는지도 쉽게 구할 수 있다.     ​[아이디어 정리]이동 시간이 항상 같으므.. 2024. 5. 11.
[백준/C++] 조용히 하라고!! 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 완전 탐색을 해야겠다는 생각이 들었다.왜냐하면 모기를 가장 많이 잡는 루트를 탐색하는 최적의 방법이 없다고 판단했기 때문이다. 시간 복잡도는 O(N*M*K+K!) 으로 N과 M이 충분히 작고 K도 10으로 매우 작아 계산해보면 충분히 완전 탐색을 해도 통과할 것이라고 생각했다. (10! = 3,628,800) 우정이는 모기를 잡는 순서를 따라 이동하면서 이동시간을 초과하지 않을 때 까지 모기를 잡는다.그렇게 모든 경우를 계산해 가장 모기를 많이 잡은 경우를 저장한다.(우정이는 모기가 있는 위치.. 2024. 5. 10.
[백준/C++] 경찰차 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 이전에 풀었던 숫자 타자 대회와 비슷하다는 느낌을 받았다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스  다른 점은 w가 1000으로 컸기 때문에 문제의 시간복잡도가 O(n^2)인지 아닌지 고민을 많이했다.고민해본 결과 다행히 시간복잡도 O(n^2)으로 풀 수 있다는 생각이 들었고, 아이디어를 구현했다. 아이디어는 다음과 같다.2차원 배열 DP[A][B]를 만들고 1번째 경찰차가 A 위치에 있으며, 2번째 경찰차가 B 위치에 있는 경우에 이동거리의 최소값으로 정의한.. 2024. 5. 9.
[백준/C++] LCS 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 LCS 문제로 Memoization을 잘 이용해 문제를 풀 수 있다. 풀이를 고민하다가 두 문자를 비교해 같은 경우 이전에 구했던 LCS를 이용해 경우를 추가하면 되겠다는 생각이 들었다. 그래서 이전의 결과를 이용하기 위해 2차원 배열을 만들고 다음과 같이 정의했다. (DP[i][j] = 1번 문자열의 1~i번 문자와 2번 문자열의 1~j번 문자를 이용해 LCS를 만든 경우의 최대길이)  이제 정의를 이용해 아래 예시를 따라가 보자. 그림에서 빨간 네모가 색칠해진 칸을 DP[i][j]라고 하자.그러면 이 경우.. 2024. 5. 8.
[백준/C++] 가장 긴 증가하는 부분 수열 5 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 예전에 풀었던 가장 긴 증가하는 부분수열(LIS) 문제와 비슷하다" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 단지 차이점이 있다면, 수열의 크기가 크다는 것과 가장 긴 증가하는 부분 수열이 무엇인지 출력을 해야한다는 것이다. 부분 수열의 길이를 구하는 것은 쉽지만, 이 부분수열이 어떻게 이루어져있는지를 구하기 위해서는 기록이 필요하다. 그러면 어떤 방식으로 기록을 해 문제를 해결했는지 아래 그림을 따라 진행하며 알아보자.  먼저 {1,3,5,2,4,5,3} 인 수열이 있다면 .. 2024. 5. 7.
[백준/C++] 냅색문제 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 단순하게 모든 경우를 구하면 시간이 오래 걸리게 된다. N이 30이기 때문에 부분집합의 모든 경우는 2^n이다. 여기서 Meet in the middle 이란 알고리즘을 이용하면 시간을 줄일 수 있다.비슷한 문제로는 아래의 문제가 있다. 세 수의 합 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 MITM 알고리즘에 대해 간단히 설명하면 경우의 수가 매우 큰 상황에서 Bruteforce로 문제를 풀어야 할 경우 적절히 분할하면 연산의 수를 줄일 수 있는 방법이다. 이 문제도 그냥 .. 2024. 5. 5.
[백준/C++] 소수의 연속합 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, N까지의 소수를 구한 다음에 투 포인터로 연속합을 계산하면 되겠다고 생각했다. 하지만 여기서 간과한 점이 소수를 구하는데 걸리는 시간이었다. 처음에는 2~4,000,000까지 하나씩 전부 소수인지 검사했다.그렇기 때문에 시간복잡도가 O(N^3/2)이 됐다.  그래서 이 시간을 줄이기 위해 예전에  에라토스테네스의 체를 이용했다.에라토스테네스의 체를 이용하면 (n/1 ~ n/n)을 전부 더한 시간복잡도로 O(NlogN)으로 소수들을 구할 수 있다. 그래서 에라토스테네스의 체로 소수들을 구해 빠르.. 2024. 5. 4.
[백준/C++] 두 용액 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 용액의 합이 0에 가까운 경우를 구하는 문제다.만약 0에 가장 가까운 경우가 여러개라면 아무 경우나 출력하면 된다. 단순히 2중 for문으로 문제를 풀면 O(n^2)의 시간복잡도가 걸린다. 하지만 이 문제는 정렬을 하면 O(nLogn)의 시간복잡도로 문제를 풀 수 있게 된다. 오름차순으로 정렬을 한 다음 양쪽 끝에서 탐색을 시작한다. 이후 양쪽의 용액의 합이 0보다 작다면 왼쪽에 있는 용액을 오른쪽으로 이동시키면 된다. 정렬 돼 있기 때문에 왼쪽의 용액과 오른쪽 끝에 있는 용액을 더한 값이 0보다 작다면,.. 2024. 4. 30.
[백준/C++] 운동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 도시에서 시작해 다시 돌아오는 사이클이 있는지 확인하고 있다면, 그 중 가장 비용이 적은 사이클을 출력하는 문제다. 사이클을 찾기 위해서는 결국 st 에서 st로 돌아오는 최소비용을 구해야 한다. 문제는 시작점이 하나만 주어진게 아니라 모든 도시가 시작점이 될 수 있다는 점이다. 그러므로 결국 모든 도시에 대해서 시작점으로 돌아오는지 탐색을 해야한다. 처음에는 priority queue를 사용한 다익스트라 알고리즘으로 풀려고 했으나, N개의 점에 대해 다익스트라 연산을 하면 시간복잡도가 O(V*Elog(V))가 된다. [(E < V*2) 이므로 log(V)로 표현 가능] 그러면 O(V^3log(V.. 2024. 4. 23.
[백준/C++] 플로이드 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 정점에서 다른 정점으로 갈 수 있는 최단거리를 구하는 문제다. 모든 정점의 경우를 구해야하기 때문에 플로이드 워셜 알고리즘으로 문제를 풀면 O(N^3)의 시간복잡도로 문제를 해결할 수 있다. 문제를 풀기전에 플로이드 워셜 알고리즘을 간단하게 정리하면, 정점 i에서 j로 가는 비용과 정점 i -> k -> j로 가는 비용을 비교해 최단 거리를 갱신하는 과정이다. 위의 과정을 3중 for문을 이용하면 모든 정점에서 다른 정점으로 가는 최소비용을 구할 수 있다. 여기서 중요한 점은 경유지 k가 for문의 가장 상위에 있어야 한다. 왜 가장 상위에 있어야 하는지 설명하기 전에, 지나갈 수 있는 경유지의 .. 2024. 4. 21.
[백준/C++] 램프 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 열의 램프들을 반전 시키는 방법을 K번 실시했을 때, 모든 행의 램프가 켜진 경우가 가장 많은 수를 구해야 한다. 이 문제에서는 램프가 가장 많이 켜진 경우를 찾기 위해 모든 경우를 탐색해봐야 하는데 이때, 모든 경우를 찾기 위한 기준을 잘 정해야 한다. 특정 열의 램프들을 끄거나 키는 것을 기준으로 잡게 되면 2^n의 시간복잡도가 나타나고 중복이 발생하게 된다. 잘 생각해보면 반대로 특정 행의 램프들을 전부 키도록 한 다음 그때, 몇 행의 램프가 켜져있는지 비교하는 방법으로 쉽게 문제를 풀 수 있다. (왜냐하면 같은 열에 있는 램프들은 전부 불이 반전되는 것에 연결되어 있다. 그렇기 때문에 한 .. 2024. 4. 21.
[백준/C++] Pho Restaurant HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 가지 요리만 하는 식당에 n개의 테이블이 있고, n개의 테이블당 i명의 사람이 요리를 시킨다. 이때, 같은 테이블은 같은 요리를 주문하도록 만드려면 사람을 몇 번 이동해야하는지 계산하는 문제다. 문제 자체는 크게 어렵지 않다. 테이블 당 1번 메뉴와 2번 메뉴를 주문한 사람의 수를 파악하고, 그 중에서 메뉴의 수가 더 적은 사람을 다른 테이블로 이동시키면 된다. 여기서 하나의 예외 상황이 발생하는데, 만약 모든 테이블이 1번 메뉴를 많이 시키고 2번 메뉴를 적게 시키는 경우다. (또는 모든 테이블이 2번 메뉴를 많이 시키고 1번 메뉴를 적게 시키는 경우) 이 경우 최소값인 수만 다른 테이블로 이동하.. 2024. 4. 19.
[백준/C++] 타임머신 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 음의 간선이 있기 때문에, Dijikstra알고리즘으로 문제를 풀 수 없다. 음의 사이클이 존재하는지 찾는 알고리즘에는 벨만 포드 알고리즘이 있기 때문에 벨만 포드 알고리즘을 이용해 문제를 풀었다. 벨만 포드 알고리즘에서 음의 사이클이 존재하는지 판단하는 방법은 다음과 같다. N개의 정점이 있을 때, 임의의 정점 A에 도달하기 위해 거쳐야되는 정점의 개수는 총 N-1개다. 그렇기 때문에 음의 사이클이 없다면 임의의 정점에서 다른 정점으로 도달하는 최소비용을 구하는 과정을 N-1번 하면 출발 정점에서 모든 정점에 도달하는 최단경로가 계산이 된다. 이 때, 음의 사이클이 있다면 한번 더 최단경로를 계산했을.. 2024. 4. 18.
[백준/C++] 미확인 도착지 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 시작점 st에서 도착점 ed로 가는 최단 경로에 임의의 두 점 (m, n)을 잇는 경로가 포함되어 있는지 계산하는 문제다. 문제를 해결하는 방법은 여러 방법이 있다. 1. Dijikstra 알고리즘으로 두 점 m, n을 잇는 경로를 포함하는지 체크한다. 2. Dijikstra 알고리즘으로 최단경로와 [st -> m -> n -> ed, st -> n -> m -> ed]의 최단 경로의 길이가 같은지 비교하는 방법이 있다. 이 중에서 1번 방법으로 코드를 구현해 문제를 풀었다. Dijikstra 알고리즘과 동일하게 코드를 구현하지만 m, n을 잇는 경로를 포함하는지 체크할 배열을 하나 만든다. 이후.. 2024. 4. 17.
[백준/C++] 특정한 최단 경로 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 중간에 반드시 두 정점을 거쳐서 가는 최단경로를 찾는 문제다. 결국 최단경로를 찾는 문제기 때문에 Dijikstra 알고리즘으로 쉽게 풀 수 있다. 제한사항을 보면 V의 개수가 최대 800이기 때문에 O(N^2)의 시간복잡도로 문제를 풀어도 빠르게 풀 수 있는 문제다. 이 문제의 특징은 양방향 간선이기 때문에 a -> b의 최단거리는 b -> a의 최단거리와 같다. 그러므로 이를 이용하면 최단거리를 구하기 위해서는 두 개의 값만 비교하면 된다. 1. 1 -> a -> b -> V로 도착하는 경우 2. 1 -> b -> a -> V로 도착하는 경우 위의 두 경우를 비교하면 되는데, a -> b의 최단거리.. 2024. 4. 16.
반응형

티스토리툴바