구름

문제 보러가기 : https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 이번 문제는 문자열 문제였습니다. 태그 안팎의 단어를 꺼낼 때 각각 큐(queue)와 스택(stack) 자료구조를 사용하였습니다. 😀 《문제 풀이》 1. 공백을 포함하여 출력하기 위해 getline() 함수로 문자열 입력 2. 태그 안의 단어는 큐에 넣고, '>' 를 만나면 큐에 있는 모든 문자를 결과 문자열에 합함 3. 태그 밖의 단어는 스택에 ..

문제 보러가기 : https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 이번 문제는 그래프 탐색 문제였습니다. (본인은 DFS 알고리즘으로 풀었습니다.) 💡 My Case 💡 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 모눈종이를 뒤집어도 영역의 넓이는 그대로이므로 왼쪽 아래 꼭짓점의 좌표와 오른쪽 위 꼭짓점의 좌표로 값을 채워넣어도 되지만, 본인은 문제에 그려진 위치에 직사각형을 그렸습니다. 《문제 풀이》 1. 모눈..

문제 보러가기 : https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제였습니다. 《문제 풀이》 1. n가지 동전의 가치를 coinValue 배열로 입력받음 2. 가치의 합이 k원이 되는 경우의 수를 구하기 위한 dp 배열을 모두 0으로 초기화 3. dp[0]은 자신의 가치만으로 j원이 되는 경우의 수이므로 1로 세팅 4. 가치의 합이 j원이 되는 경우의 수와 자신의 가치를 뺀 가치의 경우의 수를 합함 ⭐️ 5. n..

문제 보러가기 : https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 이번 문제는 문자열 문제였습니다. A와 B의 길이를 같게 할 때 A와 B 길이의 차이만큼 A의 앞 또는 뒤에 B와 같은 문자를 추가해주면 되므로 이 부분은 구현할 필요없이 입력받은 A와 B의 차이를 구하면 됩니다. 😺 《문제 풀이》 1. B의 인덱스를 증가시켜 가면서 A의 길이만큼 A와 B의 차이를 계산 2. A와 B 문자열의 문자가 다르면..

문제 보러가기 : https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이번 문제는 다이나믹 프로그래밍(DP) 문제였습니다. 1463번 1로 만들기 문제와 다른 점은 n을 1로 만드는 방법에 포함되어 있는 수들을 역추적하여 출력하면 됩니다. 😛 《문제 풀이》 1 ~ n 의 각 숫자를 1로 만들기 위해 연산을 하는 횟수의 최솟값을 dp 배열에 저장하려고 함 1. 숫자 1의 연산 횟수의 최솟값은 0 이므로 dp[1] = 0 2. 1의 이전 경로는 존재하지 않으므로 before[1] = -1 (경로 추적을 위한 배열 before) 3. 정수 n에 사용할 수 있..

문제 보러가기 : https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 이번 문제는 재귀 알고리즘 문제였습니다. 중위 순회(In-Order) : 루트 노드 전까지 왼쪽 부분 트리이고 루트 노드가 나온 이후부터는 오른쪽 부분 트리 후위 순회(Post-Order) : 가장 마지막 노드가 루트 노드 각 순회마다 정점을 순회하는 순서는 다음과 같습니다. ✨ 전위 순회 : root -> left -> right ✨ 중위 순회 : left -> root -> right ✨ 후위 순회 : lef..

문제 보러가기 : https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이번 문제는 플로이드-워샬(Floyd-Warshall) 문제였습니다. 플로이드-워샬 알고리즘은 모든 정점 간의 최단 경로를 구하는 알고리즘입니다. 😊 《문제 풀이》 1. i == j 이면 0, 아니라면 무한대로 초기화 2. 버스의 정보 입력 (시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c) 3. 플로이드 워샬 알고리즘 --> 정점을 거쳐가는 것이 더 빠르다면 gr..

문제 보러가기 : https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 이번 문제는 다익스트라(Dijkstra) 문제였습니다. 최단 경로뿐만 아니라 최단 경로에 포함된 정점들까지 출력해야 하는 문제였습니다. 《문제 풀이》 1. 입력한 출발 도시에서 도착 도시까지의 경로는 단방향이므로 단방향 연결 2. 다익스트라 (최단 경로 구하기) (1) 출발 도시를 큐에 삽입 (2) 출발 도시를 제외한 모든 도시의 거리는 INF (..

문제 보러가기 : https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 이번 문제는 자료구조 문제였습니다. 처음에는 string의 find 함수와 erase 함수를 사용하여 문제를 풀어서 시간초과가 났습니다. 😅 《문제 풀이》 1. 입력 문자열을 하나씩 결과 문자열에 삽입 2. 결과 문자열의 마지막 문자가 폭발 문자열의 마지막 문자와 같으면 폭탄 문자열을 제거할 지를 검사 (1) 결과 문자열의 마지막 문자부터 폭발 문자열의 길이까지 비..

문제 보러가기 : www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 이번 문제는 다익스트라(Dijkstra) 문제였습니다. 다익스트라 기본 문제에서 각 지역의 아이템 개수를 담을 배열만 추가해주면 됩니다. 😊 《문제 풀이》 1. 길은 양방향 통행이 가능하므로 두 지역을 양방향으로 연결 2. n개의 지역 중 습득 가능한 아이템의 최대 개수를 구해야 하므로 다익스트라 n번 수행 3. 낙하 지역을 제외한 모든 지역의 거리는 무한대로 초기화 (낙하 지역은 0) 4. 현재까..