구름

문제 보러가기 : 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. 현재까..

문제 보러가기 : https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 이번 문제는 구현 문제였습니다. 공기청정기가 작동하여 미세먼지가 이동할 때에는 BFS 알고리즘처럼 구현하면 됩니다. [필요한 것] 1. 미세먼지 확산과 공기청정기가 작동했을 때의 미세먼지 이동을 기록할 배열 room (실제 값을 바꾸는 배열) 2. 미세먼지의 확산 가능 여부와 이동 가능 여부를 위한 배열 copyRoom (배열 room 복사본) 3. 공기청정기의 위쪽 칸과 아래..

문제 보러가기 : https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제였습니다. 11053번 가장 긴 증가하는 부분 수열 문제에서 조금 더 확장된 문제입니다. 가장 긴 증가하는 부분 수열의 길이 뿐만 아니라 가장 긴 증가하는 부분 수열도 출력해야 하기 때문에 부분 수열을 갱신할 벡터와 가장 긴 증가하는 부분 수열을 담을 벡터, 2개..

문제 보러가기 : https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 이번 문제는 다이나믹 프로그래밍 문제였습니다. 11053번 가장 긴 증가하는 부분 수열 문제와 유사하지만 이번 문제는 감소하는 부분 수열도 찾아줘야 했습니다. 《문제 풀이》 1. 가장 긴 증가하는 부분 수열의 길이를 기록할 배열 incre 와 가장 긴 감소하는 부분 수열의 길이를 기록할 배열 decre 2. incre 배열에서 자기 자신의 증가하는 부분 수열의 길이는 1이므로 모두 1로 초기화 3...

문제 보러가기 : https://www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 이번 문제는 비트 마스킹 문제였습니다. 정수의 2진수 표현을 자료구조로 쓰는 기법을 비트 마스킹이라고 합니다. 비트 마스킹 기법을 활용하여 문제를 풀면 시간 단축, 메모리 절약을 할 수 있습니다. 문제 풀이를 하기 전에 문제를 풀 때 사용했던 비트 연산자들을 테이블로 정리했습니다. 비트 연산자 연산자 설명 예시 a >N>>M; int remember = 0; // 처음에는 모..