하수하따 록기장

📍 문제 링크 : https://www.acmicpc.net/problem/16948 📍 알고리즘 분류 : BFS 📍 문제 풀이이 문제는 큐를 이용해서 BFS로 해결할 수 있다. (r,c)의 위치에서 이동할 수 있는 칸은 아래 그림과 같이 총 6개이다. 따라서 한 위치에 대해 이동할 수 있는 6개의 위치를 모두 탐색해주면 된다.체스판을 넘어가거나, 이미 방문한 위치가 아니면 큐에 넣어준다.이미 방문했다면, 지금 방문한 것은 최단 횟수의 방문이 아니라는 것이므로 고려해줄 필요가 없다. 모든 지점은 처음으로 방문했을 때가 최단 횟수의 방문이다. 위 과정을 큐가 빌 때까지, 혹은 목표 지점에 도달할 때까지 반복한다. 이 문제의 핵심 로직은 모든 지점은 처음으로 방문했을 때가 최단 횟수의 방문이라는 것이다..

📍 문제 링크 : https://www.acmicpc.net/problem/2138 📍 알고리즘 분류 : 그리디 알고리즘 📍 문제 풀이 신기한 점이 어떤 전구를 먼저 켜고 끄든, 순서가 중요하지 않다는 것이다!따라서 우리는 첫 번째 전구부터 순서대로 탐색하면 된다. 그리디하게. 현재에 최적이 되도록.첫 번째 전구를 목표 상태와 비교하고 다르다면 전구의 상태를 바꾸고, 같다면 그냥 두면 된다. 그런데 전구는 자신의 왼쪽, 자신, 자신의 오른쪽 이렇게 3개의 전구의 상태에 영향을 미치게 되는데그리디하게 접근할 경우 이 조건이 훨씬 쉽게 만들어진다. 현재 보고 있는 i번째 전구를 변경하고자 할 경우 할 수 있는 것은 i+1번째 전구를 누르는 것이라는 것이다! i-1번째 전구나 i번째 전구를 누르면 안되는..

📍 문제 링크https://www.acmicpc.net/problem/1339 📍 알고리즘 분류그리디 📍 문제 풀이직관적으로 높은 자리에 큰 수가 와야된다는 것을 파악할 수 있다. 그런데 단어가 하나가 아니기 때문에, 어떤 단어에서는 높은 자리수의 알파벳이 다른 단어에서는 가장 낮은 자리수에 위치해있을 수도 있다. 따라서 모든 단어를 종합하여 판단해야 한다. ABC와 CADB가 주어졌다고 해보자.단어 수의 합은 (100*A + 10*B + C) + (1000*C + 100*A + 10*D + B) = (1000*C + 200A + 11B + C)가 될 것이다.이게 최대가 되기 위해서는 가장 큰 수를 곱하는 알파벳부터 9, 8, 7, 6, .. 순서대로 바꿔주면 된다.따라서 C = 9, A = 8, ..

📍문제 링크https://www.acmicpc.net/problem/1202 📍알고리즘 분류그리디, 우선순위 큐 📍 풀이 방법최대한 많은 보석을 훔치기 위해서는 최대한 비싼 보석을, 많이 담아야 한다.따라서 비싼 보석부터 담아야 하는데, 최대로 용량을 채울 수 있는 가방에 넣어야 한다.반복문을 통해 가방을 하나씩 그리디하게 보면서 넣을 보석을 정해준다.우선순위 큐를 이용해서 하나의 가방 안에 들어갈 수 있는 무게의 보석들 중 가격이 가장 비싼 것을 담으면 된다. 어떤 가방부터 보아야할까?용량이 큰 가방부터 본다면, 비싼데 크기가 작은 보석이 용량이 큰 가방에 담길 것이다. 더 보석을 가져갈 수 있을텐데 용량이 낭비될 것이다.따라서 용량이 작은 가방부터 탐색한다. 작은 가방에 담기는 무게 중에서 비싼..

📍 문제링크 : https://www.acmicpc.net/problem/1914📍 알고리즘 분류 : 재귀📍 문제 풀이 : 알고리즘 시간에 배운 내용과 코드를 기반으로 하노이탑 문제를 풀었다. 옮긴 횟수를 출력하는 것 때문에 시간이 오래 걸렸다. 처음에는 재귀함수가 호출될 때마다 카운트를 해가며 구했는데, N📍 코드 :#include #include #include using namespace std;void Hanoi(int n, int a, int b, int c){ if(n>0){ Hanoi(n-1, a, c, b); cout>N; string tmp = to_string(pow(2,N)); // 결과값 double을 string으로 변환하여 저장 ..

📍알고리즘 분류: DP 동적 프로그래밍큰 문제를 작은 문제로 나눌 수 있으며 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 경우 DP를 사용한다.📍문제 풀이:처음에는 조합(Combination)을 이용한 수식으로 문제에 접근했다. 문제에서 높이는 2로 고정되어 있으므로 2xn 타일을 쪼개보면 타일을 구성할 수 있는 경우는 '2x1' 혹은 '1x2 두개를 위아래로 붙인 2x2' 뿐이다. 그래서 2x1의 모양을 A, 2x2의 모양을 B라고 하자.A는 가로를 1만큼 차지하고 B는 한번에 2만큼 차지한다. 따라서 2xn의 모양에서 n = (1 x A의개수) + (2 x B의개수)라는 수식을 세울 수 있다. A와 B의 범위는 0과 자연수이다. 따라서 A와 B의 순서쌍 조합을 구하면 이 과정에..

📍알고리즘 분류: DFS, BFSDFS란 Depth First Search, 깊이 우선 탐색. 트리나 그래프에서 한 루트로 탐색하다가 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 다시 돌아가 다른 루트로 탐색하는 방식이다. 재귀호출이나 스택 배열로 구현할 수 있다.📍문제풀이: 재귀호출 방식의 DFS로 문제를 풀었다. dfs가 처음 호출되면 인접한 집들을 다 탐색하여 한 단지를 구성하는 집의 개수를 모두 센다.📍코드#include #include #include #include using namespace std;#define MAX_N 26int map[MAX_N][MAX_N];bool visited[MAX_N][MAX_N];int dx[4] = {-1,1,0,0};int dy[4] = {0,0..

https://www.acmicpc.net/problem/2309📍  풀이 방법: 합이 100이 되는 7명의 난쟁이를 구하는 것이 아니라, 9명의 난쟁이 키 합에서 뺐을 때 100이 되는 2명의 난쟁이를 구하면 된다. 📍 알고리즘 분류: 브루트포스brute force(무식한 힘). 즉 무식하게 가능한 경우의 수를 모두 탐색해보는 완전탐색 알고리즘.📍  소스코드#include #include using namespace std;int main() { int dwarf[9]; int sum = 0; for(int i=0;i> dwarf[i]; sum += dwarf[i]; } sort(dwarf,dwarf+9); for(int i=0;i 처음에 break문으..

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net #include #include using namespace std; int gcd(int a, int b){ //유클리드 호제법을 이용한 최대공약수 구하기 알고리즘 if(a

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net #include using namespace std; static int tree[26][2]; void preOrder(int now){ // 전위 순회 if(now == -1) return; cout>right; int rootInt, leftInt, rightInt; rootInt = root - 'A'; // 'A'는 0으로, 'B'는 1로, ... 'Z'는 25로 변환하여 숫자..