알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net N개의 문자열이 주어질 때 겹쳐지는 문자를 확인할 수 있는지 물어보는 문제입니다. N개의 문자 중, 겹치는 문자는 그대로, 다른 문자는 ?로 표시해야합니다. 따라서 1~N개의 문자열을 비교해, 다른 문자가 나타날 때마다 ?로 바꿔주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #..

문제 링크입니다. https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 입력 받은 문자를 거꾸로 뒤집어도 같은지를 확인하는 문제입니다. 펠린드롬이란 문자를 거꾸로 뒤집어도 원래의 문자와 같은 것을 의미합니다. 따라서 for문을 통해 원래 문자열과 뒤집은 문자열을 동시에 비교해주면 됩니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define P pair #define F first #define S..

문제 링크입니다. https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 최소 공통 조상을 물어보는 문제였습니다. 연결된 노드가 주어졌을 때, 두 노드의 최소 공통 조상을 구하는 문제입니다. 문제에서 N과 M이 크기 때문에, 조상을 구하는 과정을 반복하면 시간초과가 생기게 됩니다. 따라서 트리를 만든 뒤, 깊이를 통해 조상을 구하는 방식을 사용해야합니다. 트리를 만드는 코드입니다. void make_tree(){ queue q; q.push(1)..

문제 링크입니다. https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 플로이드 와샬을 이용해 푸는 문제입니다. 2-친구를 찾는 문제입니다. 2-친구가 되기 위해서는 X와 Y가 서로 친구이거나, X와 Y가 한다리 건너서 이어져 있으면 됩니다. X에 대해 남은 사람들이 몇번을 건너서 친구가 될 수 있는지를 확인하기 위해서 플로이드 와샬 알고리즘을 이용하면 됩니다. 플로이드 와샬 알고리즘을 사용한 후, Distance[i][j]의 값이 2이하라면, 2-친구..

문제 링크입니다. https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 플로이드 와샬 혹은 DFS를 이용해 풀 수 있던 문제입니다. 플로이드 와샬로 푸는 문제였지만, DFS를 이용하면 더 쉽게 풀 수 있었습니다. 1~N번까지 무게의 비교가 주어질 때, X번 물건과 비교할 수 없는 물건이 몇개인지를 구하는 문제였습니다. 그렇다면, 전부 비교할 수 없다면 값은 N-1이 될 것입니다. 여기서, 자신보다 큰 물건과 작은 물건의 갯수..

문제 링크입니다. https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 플로이드 와샬을 이용하면 쉽게 풀 수 있는 문제입니다. 플로이드 와샬 알고리즘을 모르시는 분은 해당 링크를 참고해주세요. https://dongdd.tistory.com/10 Floyd-Warshall(플로이드 와샬) 알고리즘 Floyd-Warshall(플로이드 와샬) 알고리즘 Floyd-Warshall Algorithm - 그래프에서 모든 정점..

문제 링크입니다. https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 밸만 포드 알고리즘을 이용해 푸는 문제입니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 u..

문제 링크입니다. https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net DFS 혹은 플로이드 워셜을 이용해서 풀 수 있는 문제입니다. 저는 DFS를 이용해 풀었습니다. 자신의 키 순서를 정확히 알기 위해서는 자기보다 작은 학생의 수와 큰 학생의 수의 합이 N-1의 값이 되면 됩니다. 예제 입력에서 4의 경우에는 자기보다 작은 학생은 3명, 큰 학생은 2명이기에 자신이 3번째로 크다는 것을 알 수 있다는 것입니다. 따라서 DFS를 통해 자신보다 작은 학..

문제 링크입니다. https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 비트마스킹과 BFS를 이용해 풀 수 있는 문제입니다. 자세한 것은 코드를 참고해주세요 #include #include #include #include #include #include #include #define P pair #define F first #define S second using namespace std; int N, M; char map[21][21]; int check[..

문제 링크입니다. https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 비트연산자를 이용해 풀 때 다른 방법보다 쉽게 풀 수 있는 문제입니다. 서쪽은 1, 북쪽은 2, 동쪽은 4, 남쪽은 8의 값을 가질 때, 한 칸마다 수가 주어지는데 해당 하는 수를 통해 어디가 벽으로 막혀있는지를 알 수 있습니다. 예를 들어, 11인 경우 남쪽 + 북쪽 + 서쪽이 벽이 막혀있는 것을 구할 수 있습니다. 그렇다면, 벽이 어디있는지를 알아야하니 합의 조합을 통해..

문제 링크입니다. https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 순환되는 그래프를 찾을 수 있는지를 물어보는 문제였습니다. DFS와 BFS를 함께 써야했던 문제입니다. 그래프가 양방향으로 주어집니다. 주어진 그래프는 순환하는 지점이 만들어지는데, 해당 지점에 속하지 않은 정점과 순환하는 곳과의 거리를 구하는 문제입니다. 그렇다면, 2가지를 구해야하는데 1. 순환하는 지점을 구해야한다. 2. 속하지 않는 지점과 순환하..

문제 링크입니다. https://www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net 규칙을 구하는 것이 난이도를 높였던 것 같습니다. ※pow() 함수를 사용하면 시간초과가 됩니다. (1 (1, 4) / (2, 1) -> (1, 3) / (3, 1) -> (1, 2) / (4, 1) -> (1, 1) (1, 2) -> (2, 4) / (2, 2) -> (2, 3) / (3, 2) -> (2, 2) / (4, 2) -> (2, 1) (1, 3)..