알고리즘
[BOJ / 스택] 1918 후위 표기식
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 1918 후위 표기식 알고리즘 : 스택 흔히 사용하는 중위 표기식 문제를 후위 표기식으로 바꾸는 문제입니다. 후위 표기식이라 하면 헷갈릴 수 있는데 예시로 - A+B*C -> ABC*+ - A+B+C -> AB+C+ - A+B*(C+D*E-F/(Z+P))+H -> ABCDE*+FZP+/-*+H+ 입니다. 두번째와 같은 경우를 ABC++로 처음에 생각하였는데 그러면 결과는 같더라도 계산순서..
[BOJ / 트리 DFS] 19542 전단지 돌리기
https://www.acmicpc.net/problem/19542 19542번: 전단지 돌리기 현민이는 트리 모양의 길 위에서 오토바이를 타고 전단지를 돌리려고 한다. 현민이의 목표는 케니소프트에서 출발하여 모든 노드에 전단지를 돌리고, 다시 케니소프트로 돌아오는 것이다. 현민 www.acmicpc.net 19542 전단지 돌리기 알고리즘 : 트리 / DFS 현재 정점이 루트인지와 자식의 수에 따른 재귀의 갈래를 나누어주면 됩니다. #include #include #include using namespace std; #define MAX 100005 vector inj[MAX]; int n,s,d; int dfs(int v, int last) { if((inj[v].size() == 2..
[BOJ / 유니온파인드 BFS] 14868 문명
https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(1 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net 14868 문명 알고리즘 : 유니온파인드/BFS/메모이제이션 KOI 2017 2번문제입니다. 유니온 파인드를 이용하여 각 문명의 부모를 빠른 시간안에 가져오도록 하고, 간선의 가중치가 1인 상황에서 BFS를 이용하면 현재 상태에서 최단해가 나오는 성질을 이용하여 문제를 풀이하였습니다. 초기값에서 답이 나오는지 체크를 하고 중간중간에 특이 문명을 연결해주는 경우를 해주어야 ..
[BOJ / DP] 1126 같은탑
https://www.acmicpc.net/problem/1126 1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 1126 같은 탑 알고리즘 : DP 일반적인 dp 구조로는 풀이를 떠올리기 힘든 문제입니다. 보고나서 경찰차 문제가 떠올랐지만 그 방식으로도 해결이 되지 않았습니다. 2차원 dp 테이블을 구상하여야 하는데 dp[A][B]=K - A : A-1번째까지의 블록을 사용하였을 때 - B : 각 탑의 높이가 차이가 B일 때 - K : 둘 중 더 높은 탑의 높이 입니다. 이를 이용해 i번째 ..
[BOJ / 구현] 19535 ㄷㄷㄷㅈ
https://www.acmicpc.net/problem/19535 19535번: ㄷㄷㄷㅈ 첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다. www.acmicpc.net 19535 ㄷㄷㄷㅈ 알고리즘 : 구현 아이디어성 구현 문제입니다. ㄷ인 트리는 두 인접한 간선 사이의 (자식-1)을 곱하면 2ㄷ가 나와 2를 나눠주면 얻을 수 있고, ㅈ인 트리는 해당 정점이 자식이 n개일 경우 n! / (n-3)!3! 이므로 n(n-1)(n-2) / 6으로 구할 수 있습니다. 최대 자식이 30만일 경우 30만*30만*30만 / 6이 나올 수 있으므로 계산에 들어가는 정수형은 long long int로 선언해주어야 합니다. #inclu..
[BOJ / 구현] 19539 사과나무
https://www.acmicpc.net/problem/19539 19539번: 사과나무 첫 번째 줄에 모든 나무가 갊자가 바라는 높이가 되도록 물뿌리개를 통해 만들 수 있으면 “YES”를, 아니면 “NO”를 따옴표를 제외하고 출력한다. www.acmicpc.net 19539 사과나무 알고리즘 : 구현 스택을 이용하여 구현하였는데 결국 나무 1,2인 애들은 겹칠 수가 없어서 스택이 아니라 count[2]짜리 배열을 만들어서 썼어도 됐을거 같다. 정렬을 하여 구현하여야 오류인 해를 피해갈 수 있습니다. #include #include #include using namespace std; #define MAX 100005 stack stk; int namu[MAX]; int sum = 0;..
[BOJ / 메모이제이션 BFS] 14867 물통
https://www.acmicpc.net/problem/14867 14867번: 물통 표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최 www.acmicpc.net 14867 물통 알고리즘 : 메모이제이션을 활용한 BFS 얼핏보면 간단 dp같지만, 두 물통의 총량이 100,000으로 두 값을 dp배열의 크기로 사용하면 메모리초과가 납니다. 하지만 나오는 물의 경우의 수는 한정적이므로 이를 map으로 dp를 한다면 시간이 오래 걸리지만 (visited 체크시 log N) 시간내에 결과값을 얻어낼 수 있습니다. ma..
[BOJ / 다차원 비트마스크 DP] 1562 계단 수
https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1562 계단 수 알고리즘 : 다차원 비트마스크 DP 정답률이 47%로 나오고 있지만 쉬운 문제는 아닙니다.. 힌트로 정답을 확인할 수 있기 때문에 정답률이 높은 것 같습니다. 4차원 배열을 활용 한 DP이며 dp[A][B][C][D]에서 각각 - A : 현재 계단 수의 길이 #include #include #include using namespace std; #define MAX 105 #define MOD 1000000000 typedef long long int ll; ll dp[MAX][1