본문 바로가기
반응형

Algorithm296

[백준/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 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 규칙에 따라 블록을 채우면 되는 문제다. 규칙을 잘 보면 k번째 블록이 임의의 수 n으로 나누어지는지 판단하면 되는 문제기 때문에 k번째 블록의 약수를 구하는 문제로 볼 수 있다. 여기서 k번째 블록의 약수를 구하기 위해서 1~k까지 계산할 필요가 없다. 왜냐하면 k번째 블록의 약수를 k = a * b로 표현할 수 있는데, 이 때 a 그러므로 임의의 두 수를 곱해서 k를 만드는 약수를 구하기 위해서는 1~sqrt(k)까지만 계산하면 된다.(sqrt(k)~k사이에 있는 약수는 1~sqrt(k)와 곱해서 k를 만.. 2024. 5. 6.
[백준/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 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 정수로 이루어진 교점에 별을 찍는 문제다. 먼저 교점을 찾는 방법은 쉽다.연립 방정식을 풀듯이 x의 계수를 일치시켜 y값을 구하고, y의 계수를 일치시켜 x값을 구하면 된다. 여기서 두 계수를 일치시키는 방법은 곱셈으로 해결했다.(곱셈을 사용하므로 변수형을 long long 으로 해주어야 한다.) 1번 함수의 x계수를 2번 함수의 x, y계수와 d값에 곱한다.2번 함수의 x계수를 1번 함수의 x, y계수와 d값에 곱한다.  이후 두 식을 빼주면 x항은 사라지고 y계수와 d값만 남게 된다. 여기서 y항이나 x항.. 2024. 5. 4.
[프로그래머스/C++] 양궁대회 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 어떤 것을 기준으로 탐색을 해야할지 고민을 했다. 만약 특정 점수에 a개의 화살을 맞추는 경우의 수를 구했다면 a!과 같은 형태의 시간복잡도가 나오게 된다. 하지만 반대로 각 점수판에서 특정 캐릭터가 이기는 경우의 수로 계산을 하면 [이긴다, 진다] 두 경우로 나오기 때문에 2^n의 시간 복잡도로 빠르게 문제를 해결 할 수 있게 된다. 그러므로 10개의 점수에 대해 라이언이 이기는 경우를 모두 탐색하고, 만약에 라이언이 이 경우대로 이기는게 가능하다면, 점수 차이를 비교했다. + 여기서 라이언이.. 2024. 5. 3.
[프로그래머스/C++] 순위 검색 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 문자열을 잘 나눌줄 알아야 풀 수 있는 문제다. 처음에 문제를 보고 단순히 query가 들어올 때 마다 계산을 할 경우 시간초과가 나게 되어있어서 어떻게 풀까 고민을 많이 했다. 그러다가 한 사람이 점수를 제외하면 가질 수 있는 경우의 수가 3*2*2*2로 24개 이며, 점수가 100000으로 모든 경우의 수를 구해도 2,400,000이 된다는 것에 착안해 문제를 해결했다. 이때 24개의 경우의 수를 표현하기 위해 cpp, java, python 은 각각 0, 8, 16 backend, frontend 는 4.. 2024. 5. 2.
[백준/C++] 두 용액 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 용액의 합이 0에 가까운 경우를 구하는 문제다.만약 0에 가장 가까운 경우가 여러개라면 아무 경우나 출력하면 된다. 단순히 2중 for문으로 문제를 풀면 O(n^2)의 시간복잡도가 걸린다. 하지만 이 문제는 정렬을 하면 O(nLogn)의 시간복잡도로 문제를 풀 수 있게 된다. 오름차순으로 정렬을 한 다음 양쪽 끝에서 탐색을 시작한다. 이후 양쪽의 용액의 합이 0보다 작다면 왼쪽에 있는 용액을 오른쪽으로 이동시키면 된다. 정렬 돼 있기 때문에 왼쪽의 용액과 오른쪽 끝에 있는 용액을 더한 값이 0보다 작다면,.. 2024. 4. 30.
[프로그래머스/C++] 택배 배달과 수거하기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가장 짧은 이동거리를 구하는 문제다. 여기서 중요한 점은 어차피 배달을 하거나 수거를 할 때 가장 먼 집을 들리게 된다는 점이다. 이때, 최소한의 거리를 이동하기 위해서는 가장 먼 거리에 있는 택배와 수거해야하는 택배를 먼저 수거해야 다시 먼 거리를 이동하지 않는다는 점이다. 아래 그림을 참고하면 이해가 쉽다. 어차피 먼 거리에 있는 택배를 가져오기 위해서 들려야 하므로 이동했을 때 먼 거리에 있는 택배를 먼저 가져오는게 무조건 최소 거리를 이동하는 방법이 된다. 그리고 이동할 때 가장 먼 거리에 있는 택배부.. 2024. 4. 29.
[프로그래머스/C++] 카카오프렌즈 컬러링북 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DFS나 BFS로 연결된 영역을 탐색하고, 그 크기를 계산하면 쉽게 풀 수 있는 문제다. 문제에서 구해야하는 값이 영역의 개수, 그리고 영역 중 가장 크기가 큰 영역이다. 그렇기 때문에 영역을 만나면 그 영역의 수를 세고 방문했다는 표시를 한다.(다시 탐색을 하지 않도록 표시를 해야한다) 연결된 부분 즉, 모든 영역을 탐색했다면 영역의 개수를 1 추가하고 최대영역의 크기와 비교한다. 만약 이번에 탐색한 영역의 크기가 이전에 저장된 가장 큰 영역의 크기보다 크다면 값을 갱신하면 된다. 마지막으로 구한 영역의 수.. 2024. 4. 28.
[프로그래머스/C++] 단체사진 찍기 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 위해서는 시간복잡도를 빨리 눈치채는게 중요했다.처음에 문제를 보고 어떻게 규칙을 찾아서 빠르게 계산을 할 수 있을까? 고민을 했다. 예를 들어 서로 연관된 규칙이 있는 경우에는 하나의 집합으로 포함시켜서 Combination을 계산하면 빠르게 조건을 탐색할 수 있지 않을까 생각했다. 하지만 아무리 생각해도 그 과정을 구현하기에는 힘들 것 같아서 다른 방법을 생각했다. 그러던 와중 8명을 배치하는 경우의 수가 8! 이고, 조건이 100개라는 걸 보고 둘을 곱하면 약 4,000,000 이므로 모든 경우를 직.. 2024. 4. 25.
반응형

티스토리툴바