본문 바로가기
반응형

C++245

[백준/C++] 이진 검색 트리 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 재귀로 한번에 풀려고 했다.왜냐하면 이진 트리를 직접 나누기에는 시간이 아슬아슬해 보였기 때문이다. 그러나 재귀적으로 풀기가 너무 힘들어 그냥 루트노드에서 원소를 넣으며 이진트리를 만들어 풀었다. 즉, 이진트리 만들기 -> 만든 이진트리에서 후위순회하기로 문제를 풀었다. 이진트리를 만드는 방법은 아래 그림과 같다.전위 순회이므로 최상단 루트 노드에서 수를 넣어 이진트리를 만든다. 만약 28이 들어오는 경우는 50보다 작으므로 왼쪽 자식이다. 이때, 왼쪽 자식의 자리가 비어있지 않으므로 28을 5.. 2024. 5. 22.
[백준/C++] 트리의 순회 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트리의 규칙을 잘 찾으면 해결할 수 있는 문제다. 인오더는 중위 순회로 (왼쪽) -> (루트) -> (오른쪽)프리오더는 전위 순회로 (루트) -> (왼쪽) -> (오른쪽)포스트오더는 후위 순회로 (왼쪽) -> (오른쪽) -> (루트)순서로 탐색을 한다. 여기서 아래 그림을 예로 들어 생각해 보자그러면 우리는 포스트오더가 항상 맨 마지막에 루트 노드가 오기 때문에 포스트오더의 마지막 노드는 프리오더에서 맨 처음에 나오는 루트 노드라는 사실을 알 수 있다. 즉, 아래 그림과 같이 처음에 탐색을 한다. 이를 이용하.. 2024. 5. 20.
[프로그래머스/C++] 올바른 괄호 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 stack을 활용해도 되지만 단순히 개수를 세도 쉽게 풀 수 있는 문제다. '('의 괄호가 나오면 괄호가 시작했다는 count를 1 증가시키고 ')' 괄호가 나오면 괄호가 끝났다는 의미에서 count를 1 감소시킨다.이때, count가 0보다 작은 값이 되면, 이는 올바른 괄호가 아니라는 의미이므로 false를 return 하면 된다. 그리고 모든 string의 탐색이 끝난 후에 count가 0이 아니라면 '('의 괄호가 ')' 괄호의 개수보다 많다는 의미이므로 false를 return 하면 된다. 만약 두 .. 2024. 5. 18.
[백준/C++] 트리 순회 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 전위 순회와 후위 순회, 중위 순회의 각 특징만 알면 쉽게 풀 수 있는 문제다. 문제에 제시된 출력 순서를 보면 아래와 같다.전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)여기서 전위 순회의 출력 순서를 보면 루트 -> 왼쪽 자식 정점 -> 오른쪽 자식 정점인 모습을 볼 수 있다.그러므로 pseudo 코드로 표현하면 아래와.. 2024. 5. 17.
[백준/C++] 트리의 지름 (No. 1167) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 사실 이 문제는 문제의 제목이 가장 큰 힌트라고 생각한다. 목표는 트리의 지름을 구하는 것으로 트리의 지름은 트리에서 임의의 두 점 사이의 거리가 가장 긴 것을 의미한다. 그렇다면 어떻게 그 거리를 구하기 위해 생각해야할 점은 2개다. 1. 특정 두 점 사이의 거리가 가장 먼 경우는 두 점이 전부 최하위에 있는 leaf다.2. 두 점 사이의 거리가 가장 먼 노드를 구했을 때, 정점을 a, b라고 하면 임의의 정점 c는 a, b 의 경로에 포함되거나 포함되지 않는다. 1번은 당연한 말이다.왜냐하면 두 정점이 leaf가 아.. 2024. 5. 16.
[백준/C++] 플로이드 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 플로이드 워셜 알고리즘 문제에 경로를 역추적 하는 게 추가된 문제다.이전에 풀었던 플로이드문제" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스  모든 경로에 대해 구해야 하므로 플로이드 워셜 알고리즘을 이용하면 O(n^3)으로 구할 수 있다. 플로이드 워셜 알고리즘이란 쉽게 말해 몇 번의 경로를 거쳐서 가는게 최소 비용이 되는지 구하는 방법으로 n개의 노드가 있을 때, [i][j]로 가는 최소 경로를 구하는 방법은 그 사이에 포함 될 수 있는 모든 노드의 수 만큼 k를 반복하면 되.. 2024. 5. 14.
[백준/C++] 최소비용 구하기 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 예전에 풀었던, 최단거리 알고리즘과 같은 문제다.그래서 N이 1000이고 E가 100,000이므로 우선순위 queue를 이용한 dijikstra로 문제를 풀었다. 들어온 경로들로 graph를 만들고, 시작점부터 시작해 위치, 비용의 정보를 가진 pair를 priority queue에 넣는다.이후 가장 비용이 적은 위치의 값을 가져와 다시 pq에 넣는 과정을 반복하면 된다.여기서 최소 비용과 어느 도시에서 왔는지 정보를 저장할 visited라는 이름의  vector> 를 만들어 관리한다. 이후 pq에서 도시를 .. 2024. 5. 13.
[백준/C++] DSLR 문제 문제 설명 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스   풀이 ">HTML 삽입미리보기할 수 없는 소스 [문제 풀이]  이 문제는 이전에 풀었던 문제들과 큰 차이가 없는 문제다.가장 적은 연산으로 특정 수를 만드는 것을 목표로 하기 때문에 BFS로 풀 수 있다. BFS로 구할 경우 어떤 수 A를 DSLR 연산으로 다른 수 k를 만들 수 있고 이 때, k가 처음 나온다면, k가 나오는 가장 빠른 방법이 되기 때문이다. 그러므로 배열을 이용해 어떤 수A를 연산해  k를 처음 만들었을 경우에 어떤 연산으로 k가 되었는지를 array[k]에 저장한다.그리고 A에서 k로 변했다고 저장하기 위해 arrayIdx[k]에 A를 저장한다. (어떤 수에.. 2024. 5. 12.
[백준/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까지의 소수를 구한 다음에 투 포인터로 연속합을 계산하면 되겠다고 생각했다. 하지만 여기서 간과한 점이 소수를 구하는데 걸리는 시간이었다. 처음에는 2~4,000,000까지 하나씩 전부 소수인지 검사했다.그렇기 때문에 시간복잡도가 O(N^3/2)이 됐다.  그래서 이 시간을 줄이기 위해 예전에  에라토스테네스의 체를 이용했다.에라토스테네스의 체를 이용하면 (n/1 ~ n/n)을 전부 더한 시간복잡도로 O(NlogN)으로 소수들을 구할 수 있다. 그래서 에라토스테네스의 체로 소수들을 구해 빠르.. 2024. 5. 4.
반응형

티스토리툴바