알고리즘/알고리즘 문제 풀이 (17) 썸네일형 리스트형 [백준/c++] - 1504 특정한 최단 경로 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 활용문제를 하나 풀어봤다. 비용이 최소가 되는 경로를 구하는 문제에 또다른 조건으로 특정 정점을 통과하는 최단 경로를 구하는 문제이다. 네트워크 수업시간에 특정 노드를 방문하는 경로탐색 기법에 대해 설명을 들었던 적이 있는데 이 문제를 보고 그게 어렴풋이 생각이 났다. 그때는 개념만 들었기에 어떤식으로 구현이 될지 생각해보진 않았는데 이번에 .. [백준/c++] - 1753 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘을 학습한 후 예제문제를 풀어봤다. 방향이 존재하는 가중치 그래프에서 시작 지점으로부터 최단 경로를 찾는 대표적인 예제 문제이다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; struct Vertex { int v.. [백준/c++] - 2178 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net DFS, BFS, 다익스트라와 같은 최단 경로 탐색 알고리즘을 학습한 후, 복습겸 풀어본 문제이다. 옛날에도 이미 많이 풀었던 문제지만 다시보니 또 새롭다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; // 간선에 비용이 동일한(없는) 최단 경로 탐색 -> BFS // 그래프 표현 방식 -> 인접 행렬 방식, 2차 .. [백준/c++] - 4949 균형잡힌 세상 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net - 서론 스택을 활용하는 문제 였습니다. 문제의 조건은 소괄호와 대괄호가 제대로 닫혀 있는지를 체크하는 문제로 복잡하지 않았습니다. 문제를 읽자마자 어디선가 풀어봤던 기억이 나서 익숙 했습니다. 이런식으로 메모장에 기록해서 생각을 정리 하였습니다. 복잡하지 않게 구현 할 수 있을 것 같지만 약간 생각이 필요했던 부분이 있었습니다. 프로그램의 기능은 간단히 생각해보면 문장을 입력받고 .. [백준/c++] - 13305 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 매 순간 마다 최선의 것을 택해서 최소 혹은 최대의 것을 구하는 그리디 알고리즘 문제 입니다. 처음에는 dfs나 dp등 다른 방법으로 구현이 가능할 것 같았지만, 문제에 제시된 조건에 도시의 수가 이 방법으로는 시간 초과가 날 것같아 그리디 알고리즘으로 구하려고 방향을 바꿨습니다. #include #include #include using namespace std; int main(.. [백준/c++] - 10844 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제로, 1부터 100사이 길이의 숫자중에 각 자릿수가 1씩만 차이나는 수의 개수를 구하는 문제입니다. 근데 문제는 이 문제가 dp를 사용하는 문제인지를 판단하는게 어렵다는 거;; 그래서 문제를 처음 접했을 때, 이전에 공부했던 백트래킹 기법이 잘 어울리는 것 같아 적용을 해보려고 했으나, 길이가 100인 수의 개수를 구한다고 가정했을 때, 한가지 경우의 수를 구하는 데에만 함수를 100번 호출한다. 길이가 100인 수를 백트래킹으로 계산하면 로그를 써야할 정도의 횟수만큼 함수를 .. [백준/c++] - 15650 N과 M(2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹에 대해 공부하면서 풀었던 문제입니다. N과 M(1)과 다른점이라면 중복된 수열을 제외하고 출력한다는 점입니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int N; int M; vectorans; vectorans_check; vectorans_tmp; void backTracking(.. [백준/c++] - 1436 영화감독 숌 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 666이 포함된 숫자를 크기 순서대로 세는 문제입니다. #include #include using namespace std; int main() { int input, series = 0; cin >> input; int count = 666; while (input != series) { string num = to_string(count); // 검사하기 위해 문자열로 변환 for (int .. 이전 1 2 3 다음
