알고리즘 모음(C++)

문제 링크입니다. 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)..

문제 링크입니다. https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net BFS를 이용한 구현 문제였습니다. 3개의 좌표를 동시에 옮겨야 했었기에 코드가 복잡해진 것 같습니다. 나무가 3개의 좌표가 연달아서 주어집니다. 그렇다면 움직일 때 3개의 좌표를 같이 움직여서 다른 위치로 갈 수 있는지를 확인해야합니다. 다른 좌표로 이동할 때 고려해야할 점이 2가지 있는데, 1. 이동한 3개의 좌표에 다른 나무가 없어야한다. 2. 이전에..

문제 링크입니다. https://www.acmicpc.net/problem/15596 15596번: 정수 N개의 합 C++17, Java 8, Python 3, C11, PyPy3, C99, C++98, C++11, C++14, Go, C99 (Clang), C++98 (Clang), C++11 (Clang), C++14 (Clang), C11 (Clang), C++17 (Clang) www.acmicpc.net 주어진 값의 합을 구하는 코드를 짜는 문제입니다. 자세한 것은 코드를 참고해주세요 #include long long sum(std::vector &a){ long long Sum = 0; for(int i = 0; i < a.size(); i++){ Sum += a[i]; } return Sum..

문제 링크입니다. https://www.acmicpc.net/problem/5622 5622번: 다이얼 첫째 줄에 알파벳 대문자로 이루어진 단어가 주어진다. 단어의 길이는 2보다 크거나 같고, 15보다 작거나 같다. www.acmicpc.net 조건문을 사용하는 간단한 문제였습니다. 단어를 구성하는 알파벳이 어디에 속하는지만 판단하는 문제였습니다. 자세한 것은 코드를 참고해주세요. #include #include #include #include #include #include #include #define P pair #define F first #define S second #define INF 987654321 using namespace std; string N; int main(){ cin.tie..

문제 링크입니다. https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net 수학을 이용한 구현 문제입니다. 날짜를 입력받아 요일을 출력하는 문제입니다. 예를 들어, 3월 14일인 경우, 1월과 2월의 날짜 수와 14를 더해 총 일수를 구합니다, 총 일수를 7로 나눈 뒤, 나머지를 따라서 요일을 정해주면 됩니다. 0 -> 일요일 ~ 6-> 토요일로 정해주면 구할 수 있습니다. 자세한 것은 코드를 참고해주세요 #in..