본문 바로가기
반응형

algorithm279

[백준/C++] 트리와 쿼리 (No. 15681) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 루트노드가 주어지면 그 노드를 기준으로 트리를 그리면 되는 문제다. 단지 그냥 트리를 그리는 것과 다른 점이 있다면, 자식 노드의 수가 몇 개 인지 쿼리를 통해 출력한다는 점이다. 여기서 매번 쿼리가 들어올 때 마다 자식 노드의 수를 계산한다면 매우 많은 반복이 생기게 된다. 그러므로 애초에 트리를 그릴 때 자식노드가 몇 개 인지 return을 해준다면 한번의 트리를 그림으로써 모든 노드의 자식의 수를 알 수 있게 된다. 이제 아래 그림을 통해 어떻게 진행되는지 알아보자 위 그림과 같은 트리가 있을 경우 트리.. 2024. 6. 3.
[백준/C++] 전력난 (No. 6497) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 집에서 다른 집으로 이동하기 위해서는 길에 가로등이 켜져있어야 하며, 다른 집을 거쳐서 이동할 수 있다. 이때, 가로등을 최소로 켜두면 얼마만큼의 비용을 절약할 수 있는지 계산하는 문제다. 즉, 모든 집들이 연결되어 있을 경우의 최소 비용을 구해 총 비용에서 빼면 절약한 비용이 나오므로, MST 문제임을 알 수 있다. 제한 사항을 보면 m과 n이 200,000이므로 prim 알고리즘이나 크루스칼 알고리즘을 이용해 문제를 풀면 된다. 나는 모든 간선을 우선순위 큐에 넣어서 최소 비용을 구하는 방법으로 문제.. 2024. 6. 2.
[백준/C++] 우주신과의 교감 (No.1774) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀었을 때, 단순히 크루스칼 알고리즘으로 풀었다. 외계신들 간의 거리만 계산해 priority_queue에 넣으면 매우 쉽게 풀 수 있기 때문이다. 문제는 크루스칼 알고리즘이나 heap을 이용한 prim알고리즘은 시간복잡도가 O(ElogV)인데, 이 문제에서 E=V^2이기 때문에 O(V^2)의 prim알고리즘을 사용하면 더 빨리 문제를 해결할 수 있다. O(V^2)의 prim알고리즘을 간단히 설명하면 정점은 {현재 방문한 노드}와 {아직 방문하지 않은 노드}의 두 집합으로 나눌 수 있다. 여기서, 현재.. 2024. 6. 1.
[백준/C++] 다리 만들기 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보면 섬의 개수도 적고 격자의 크기도 생각보다 작기 때문에 풀이 방법만 잘 생각하면 여유롭게 풀 수 있는 문제다. 먼저 섬과 다른 섬의 연결은 오직 직선으로 만들어진 다리로 연결되어야 하며, 이 때 다리의 길이는 2 이상이어야 한다. 위 조건에 맞게 섬끼리 연결되는 다리의 길이만 계산하면 Prim 알고리즘이나 크루스칼 알고리즘을 이용해 모든 섬이 연결되는데 드는 최소 비용계산할 수 있다. 그렇다면 어떻게 섬끼리 연결되는 다리의 길이를 계산할지 알아보자.  먼저 하나의 섬에는 같은 번호가 오도록 아래 그림과 같.. 2024. 5. 31.
[백준/C++] 별자리 만들기 (No. 4386) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이]  이 문제는 이름만 다르지 사실 이전에 풀었던 최소 스패닝 트리 문제와 다를게 없다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스  왜냐하면 모든 별을 잇는 최소 비용을 계산하는게 목적인 문제이므로, 각 별 들을 잇는 간선의 비용을 계산해 어떤 별들을 잇는 간선인지 저장하면 MST 문제가 된다. 두 점의 거리를 계산하는 방법은 (x1, y1), (x2, y2) 일 경우 두 점의 거리 s^2 = (x1-x2)^2 + (y1-y2)^2 를 이용해 계산하면 된다.  이제 두 점의 거리를 계산하.. 2024. 5. 30.
[백준/C++] 최소 스패닝 트리 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 최소 스패닝 트리를 구하는 문제로 모든 노드가 연결되어 있어야 한다. 단순히 비용을 기준으로 정렬을 한 다음 두 노드가 연결될 경우에 방문 처리를 하면 떨어진 섬과 같은 경우가 발생하기 때문에 방법을 생각해 봤다. Union-Find를 사용하면 떨어진 경우를 제외할 수 있을 것 같았지만,  굳이 그럴 필요가 없을 것 같아서 그냥 priority_queue를 이용해 단순하게 풀었다. (나중에 찾아보니 Prim 알고리즘 방식이었다..) 이 priority_queue는 비용을 기준으로 오름차순 정렬 되어 있다. 먼.. 2024. 5. 30.
[백준/C++] 사이클 게임 (No. 20040) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 그냥 사이클이 존재하는지 확인하는 문제가 아니라 간선을 추가하면서 사이클이 존재하는지 확인하고, 만약 사이클이 존재한다면 몇 번째에서 사이클이 만들어졌는지 출력하는 문제다. 임의의 두 노드를 연결하는 간선이 추가될 때 마다 사이클이 만들어 지는지 확인하는 조건은 간단하다. 두 노드사이에 간선이 생기기 전에도 두 노드가 다른 노드를 통해 연결되었는지 확인하면 된다.  그림을 보면 이해가 쉽다.  위 그림과 같이 두 노드가 이미 연결된 상태에서 두 노드를 잇는 간선이 생기자 사이클이 완성되는 모습을 볼 수 있다... 2024. 5. 28.
[백준/C++] 친구 네트워크 (No. 4195) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 친구 관계가 생길 때 마다 두 사람의 친구 네트워크의 합을 출력하는 문제다. 즉, 두 집합의 합집합의 결과를 출력하는 문제와 같다. 문제에서는 친구 관계가 연결되면, string으로 친구 관계가 주어진다.그러므로 좀 더 편하게 문제를 풀기 위해 unordered_map을 이용해 string을 int로 변환하고 이 int를 index로 사용했다. index로 변환하는 방법은 처음 나타난 친구라면 map에 저장된 int가 0이다.그러므로 map[string]==0일 경우에는 index를 저장해주고 아니라면, 그대.. 2024. 5. 26.
[백준/C++] LCS 4 (No. 13711) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 LCS를 찾는 문제인데, 특이한 조건이 있다.바로 수열의 크기 N이 주어지면 1~N의 숫자를 가진 순서가 다른 수열이 2개 주어진다는 것이다.  만약 이 조건을 대충 넘기고 그냥 풀게 되면 조건으로 주어지는 N이 10만이므로 일반적인 LCS로 문제를 풀게되면 O(N^2)으로 시간초과가 나게 될 것이다.  이제 어떻게 하면 O(N^2)보다 빠르게 문제를 풀 수 있을지 생각해보자.  잘 생각해보면 1~N의 숫자가 2개의 수열에 한 번만 등장하기 때문에 하나의 수열의 i번째 index가 다른 수열의 몇 번째 자리에.. 2024. 5. 26.
[백준/C++] 하이퍼 토마토 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 사실 BFS를 풀 줄 알면 쉽게 해결할 수 있는 문제다.하지만, 11차원이라는 점에서 그렇게 되면 거의 반 노가다 문제가 된다. 그래서 어떻게 하면 코드를 효율적으로 짤 수 있을까? 생각을 하다가, 1차원 배열로 토마토들을 배치한 뒤 인접 이동을 +1,-1이 아니라 n칸씩 이동하면 되겠다는 생각이 들었다. 간단한 예를 생각해 보자만약 차원이 [3 2 2 1 1 1 1 1 1 1 1]로 주어진다면 토마토를 이렇게 표현할 수 있다.파란색으로 표시된 부분은 2번 토마토가 다른 토마토를 익게 할 수 있는 범위다. 즉.. 2024. 5. 26.
[백준/C++] 여행 가자 (No. 1976) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 경로가 서로 연결된 상태인지 구하는 문제다.왜냐하면 여러 경로가 주어지고, 그 경로를 따라 이동할 수 있는지 묻는 문제기 때문이다. 그래서 Union Find로 분류된 문제지만, 단순한 BFS로 풀 수 있다. 간단히 BFS로 푸는 방법을 설명하자면, 주어진 경로에 있는 위치에서 탐색을 시작한다.그리고 방문한 노드들을 기록할 배열 visited를 만든 뒤 방문한 위치는 true로 바꿔준다. 이제 주어진 경로를 탐색하며 한번이라도 방문하지 않은 노드가 있다면, NO를 출력하면 된다. 즉, 문제를 요약하면 특.. 2024. 5. 25.
[백준/C++] 집합의 표현 (No. 1717) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 두 원소가 같은 집합에 있는지 찾는 것과 두 집합을 합치는 연산을 구현하면 쉽게 해결할 수 있는 문제다. 먼저 1차원 배열을 만든다.이 배열에는 특정 원소의 부모 원소 값이 저장된다. 그러므로 이를 이용해 부모 원소를 따라가다 보면 array[i] 에 저장된 값이 i인 원소가 나타나는데, 이 때 i가 이 집합의 대표 원소가 된다. 즉, 두 원소가 속한 집합이 같은지를 찾기 위해서는 array를 이용해 대표 원소가 같은지 비교하면 해결할 수 있다. 이제 두 집합을 합치는 방법을 알아보자. 두 원소가 속한 집합을.. 2024. 5. 24.
[백준/C++] 트리 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이]이 문제는 트리가 몇 개인지 세면 되는 문제다. 여기서 트리의 특징은 사이클이 존재하지 않는다는게 특징이다.문제에서는 연결된 간선에 없이 하나의 노드만 있는 경우도 트리로 세기 때문에 사이클이 있는지만 검사하면 쉽게 풀 수 있는 문제다. 사이클을 찾는 방법은 쉽다. 특정 노드를 루트 노드로 정한 뒤 그 노드를 시작으로 트리를 탐색한다.그러면 모든 노드는 부모 노드가 정해지게 된다. 이렇게 탐색할 때, B노드의 자식인 A노드에 부모노드가 정해져있다면, 사이클이 존재하는 것이다. 아래 그림을 통해 더 쉽게 알아보자왼쪽은 정상.. 2024. 5. 23.
[백준/C++] 별 수호자 룰루 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 규칙만 잘 생각하면 쉽게 풀 수 있는 문제다. N과 K가 주어지면 N은 K로 나누어 떨어진다.이때,  N/K개의 팀을 나누고, 각 팀의 전투력의 합이 K로 전부 나누어떨어지지 않게 만들 수 있는지 구하는 문제다. 가장 먼저 생각할 수 있는 경우는 K가 1인 경우다.K가 1이라면, 모든 팀은 K로 나누어떨어지기 때문에 당연히 정답은 "NO"다. 이제 K가 1 이상일 경우를 생각해보자. 가장 쉬운 방법은 1 ~ N의 전투력을 가진 사람을 K명씩 나누어 팀을 만들기 때문에, 각 팀에 전투력을 K로 나누었을 때 나머.. 2024. 5. 22.
[백준/C++] 이진 검색 트리 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스   풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 재귀로 한번에 풀려고 했다.왜냐하면 이진 트리를 직접 나누기에는 시간이 아슬아슬해 보였기 때문이다. 그러나 재귀적으로 풀기가 너무 힘들어 그냥 루트노드에서 원소를 넣으며 이진트리를 만들어 풀었다. 즉, 이진트리 만들기 -> 만든 이진트리에서 후위순회하기로 문제를 풀었다. 이진트리를 만드는 방법은 아래 그림과 같다.전위 순회이므로 최상단 루트 노드에서 수를 넣어 이진트리를 만든다. 만약 28이 들어오는 경우는 50보다 작으므로 왼쪽 자식이다. 이때, 왼쪽 자식의 자리가 비어있지 않으므로 28을 5.. 2024. 5. 22.
반응형

티스토리툴바