알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 중위 순회를 이용해 푸는 문제였습니다. 1부터 N까지 열이 존재할 때, 트리의 노드를 적정하게 배치하여 하나씩만 위치하게 합니다. 이때, 최대 길이를 가지는 행을 구해주면 되는 문제입니다. 이 문제를 트리를 탐색하는 3가지 방법 중에, 중위 순회 방법이 가장 적당합니다. 왜냐하면, 중위 순회는 왼쪽 자식 -> 부모 -> 오른쪽 자식의 순서로 탐색을 진행하는데 1..

문제 링크입니다. https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 문자열과 배열을 이용해 푸는 문제입니다. 문자열이 주어진 뒤, 주어진 문자열에서 알파벳이 각각 몇개가 들어있는지를 구하는 문제입니다. 알파벳 갯수를 저장하는 배열을 만들어서, 해당 알파벳이 나올 때마다 값을 1씩 증가해줍니다. 마지막에 값을 전부 출력해주면 됩니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #defin..

문제 링크입니다. https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net DFS를 이용해 푸는 문제입니다. 윗 줄의 숫자를 하나씩 선택할 때마다, 밑에 붙어 있는 숫자도 같이 선택됩니다. 윗 줄의 숫자를 선택해, 밑의 줄의 숫자와 같게 뽑으려고 할 때 몇 개, 어떤 숫자를 뽑아야하는지 구하는 문제입니다. 이 문제를 푸는 핵심은 윗 줄과 아랫 줄의 숫자를 연결해주는 겁니다. 만약 윗 줄이 1, 아랫 줄이 3이라면, connect[1] = 3..

문제 링크입니다. https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 공통 조상을 찾는 문제입니다. 두 노드가 주어지고 서로의 가까운 공통 조상을 찾는 문제입니다. 이 문제를 푸는 방법은 두 노드 중 하나의 노드를 선택해 해당 노드의 부모를 찾아준 뒤, 찾은 부모들의 값을 1로 바꿔줍니다. 남은 노드 하나를 탐색해, 해당 노드의 부모를 찾아줍니다. 이때, 노드의 값이 1인 것이 있다면, 해당 노드..

문제 링크입니다. https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 완전탐색을 이용한 그래프 문제입니다. 5*5 숫자판에서 무작위 위치에서 5번까지 이동해 수열을 구하는 문제입니다. 1을 5번 이동했다면 11111이 수열이 됩니다. 만들 수 있는 수열이 숫자판에 따라 11111 ~ 99999까지 있을 수 있습니다. 따라서 이전에 만들었던 수열을 찾는 배열 칸은 100000 이상으로만 잡아주면 됩니다. 아..

문제 링크입니다. https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 그래프탐색을 이용해 푸는 문제입니다. 저는 BFS를 이용해 풀었습니다. 자신의 친구와 친구의 친구를 결혼식에 초대하려고 할 때, 부를 수 있는 사람 수를 구하는 문제입니다. 친구의 친구까지 부를 수 있으니, 2번까지 이동할 수 있습니다. 1번 정점에서 시작해 2번까지 이동해서 자신과 연결된 정점 갯수를 찾아주면 됩니다. 자세한 것은 코드를 참고해주세요 #includ..

문제 링크입니다. https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 그래프 탐색을 이용하는 문제입니다. 노드를 하나 지웠을 때, 리프 노드를 구하는 문제입니다. 시작 노드를 찾은 뒤, 시작 노드에서 그래프 탐색을 시작해줍니다. 탐색 노드와 연결된 노드 중, 연결되지 않는 노드로 이동해 다음 노드로 계속 이동해줍니다. 더 이상 이동할 수 없는 노드로 도착하면, 리프 노드 갯수를 1 증가해줍니다. 여기서, 지워진 노드가 연결되어 있어도 이동할 ..

문제 링크입니다. https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 분리 집합과 그래프 탐색을 이용해 푸는 문제였습니다. 연결된 정점들을 줬을 때, 주어진 길로 여행을 할 수 있는지 확인하는 문제입니다. 예제 입력을 봤을 때, 1 -> 2 2 -> 1, 3 3 - > 2 와 같이 연결되어 있습니다. 또한, 출발지와 목적지를 여러개로 나눠서 생각해보면, 1 -> 2와 2 -> 3을 확인할 수 있습니다. 따라서, (1, 2) + (2, 3)으로 나눠..

문제 링크입니다. https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문자열을 사용한 구현 문제였습니다. 문자가 연속되는지만 찾으면 되는 문제입니다. 같은 알파벳이 떨어져서 나오면 안되며, 항상 붙어져 나와야지 그룹 단어가 됩니다. 따라서 알파벳을 3가지로 나눠야하는데, 1. 처음 나온 알파벳인 경우 2. 처음 나온 알파벳은 아니지만 전에 나온 알파벳과 같은 경우 3. 처음 나온 알파벳은 아니지만 전에 나온 알파벳과..

문제 링크입니다. https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 이분탐색을 활용해야하는 문제였습니다. 두 개의 섬이 주어졌을 때, 옮길 수 있는 중량의 최댓값을 구하는 문제입니다. 저는 이분탐색의 방법으로 풀었는데, low = 0, high = 다리의 최대 중량로 만들어, mid값을 얻은 뒤, mid값보다 큰 값으로만 두 섬을 이동할 수 있냐? -> 해당 과정을 확인했습니다. mid ..

문제 링크입니다. https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net Dp로 풀 수 있지만, BFS로 푸는게 더 간단해 보여 약간의 노다가를 추가한 BFS로 풀었습니다. 3개의 SCV가 각각 9 or 3 or 1의 값이 빼집니다. 따라서 모든 경우를 확인한 뒤, 전부 0이 된 최소 횟수를 출력해주면 됐습니다. 자세한 것은 코드를 참고해주세요 #define _CRT_SECURE_NO_WARNINGS #include #include #include #inclu..

문제 링크입니다. https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net BFS를 이용해 푸는 문제입니다. BFS를 짜는 것 자체는 간단했습니다. 돌이 A, B, C가 존재하니 옮길 수 있는 경우는 3가지입니다. 1. A 와 B 2. A 와 C 3. B 와 C 각 경우에서도 X가 큰 경우, Y가 큰 경우가 있으니 총 6가지 경우만 확인하면 됐습니다. 방문했던 돌의 크기를 확인하는 방법은 3차원 배열을 이용해 [A][B][C]로 저장하면 편하겠지만..