본문 바로가기
반응형

전체 글307

[백준/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.
[프로그래머스/C++] 가짜 해밀토니안 (월간 코드 챌린지 시즌1) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 가짜 해밀토니안 경로를 만들 때, 어떻게 경로가 형성되는지 잘 파악해야 풀 수 있는 문제다. 문제에서 알려주는 가짜 해밀토니안 경로를 한번 분석해보자위 그림에서 같은 그래프지만 2번 노드에서 어디로 가는지에 따라 만들 수 있는 가짜 해밀토니안 경로가 달라진다. 4번으로 가게 되면, 더 이상 2번 경로로는 돌아오지 못한다.대신 2번 분기점에서 다른 곳으로 빠지지 않고 다시 1번까지 돌아가면 4번 5번을 거쳐 해밀토니안 경로를 만들 수 있다. 만들어진 해밀토니안 경로를 보면 특정 노드와 연결된 노드는 최대 3개가.. 2024. 4. 24.
[백준/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.
반응형

티스토리툴바