본문 바로가기
반응형

C++245

[백준/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.
[Algorithm] 트라이(Trie) 트라이(Trie)" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스Trie는 탐색트리의 일종으로 특정 문자열이 포함되어있는지 등을 찾는데 효과적인 자료구조다. 예를 들어 영어로 된 여러 단어가 N개 주어지고,  여러개의 접두어가 M개 주어진다.이때, M개의 접두어로 시작하는 단어가 몇 개 있는지 구하는 경우를 생각해보자. 단순하게 반복문으로 구하게 되면 (M개의 접두어)*(N개의 단어)*(접두어와 단어를 비교) 의 반복을 하게 된다.M, N, 접두어 단어의 길이가 작으면 상관없지만 조금이라도 커지면 시간복잡도가 크게 늘어나게 된다. 이러한 반복을 줄이는데 효과적인 자료구조가 Trie다. 이제 [HILL, HIGH, HELL, HELLO, HELLT] 라는 단어를 Trie 구조로 .. 2024. 5. 24.
[백준/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.
반응형

티스토리툴바