https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. Logic 재귀를 이해하고 있다면 쉽게 풀 수 있는 문제이다. 각 노드의 부모 노드를 순서대로 출력해야 하기 때문에 부모 노드를 저장하는 배열(check)에 저장해줬다. 양방향으로 입력을 받았기 때문에 반복되는 계산을 막아주기 위해 vis배열도 추가해줬다. 수정 > 원래는 vis배열에 넣어줬지만 check배열을 -1로 초기화 시켜준 다음 -1이 아니면 continue하도록 설계해주면 100001개짜리 배열 하나를 덜 써도 된다 2. Code #includ..
백준
https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 1. Logic 처음에 이 문제를 딱 보고 위상정렬인줄 알았다. 하지만 위상정렬의 탈을 쓴 DP문제였고 결국 멘토한테 도움을 받았다. 내가 처음에 짠 코드는 동시에 진행하는 작업 중에 가장 시간이 오래 걸리는 작업의 시간이 고려되지 않을 수도 있는 코드였다. 그래서 이 문제는 위상정렬과 코드가 비슷하긴 하지만 DP로 풀이해야 한다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 1. Logic 조건 그대로 구현하면 된다. 구현이 약간 까다롭지만 계란의 수 N의 크기가 8로 엄청 작기 때문에 브루트포스로 풀이할 수 있다는 것을 유추할 수 있다. 구조체를 사용하지 않고 내구도와 무게를 따로 저장하는 배열을 선언하여 풀이했다. 2. Code #include #include using namespace std; int n; int dura[10]; int weig..
https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 1. Logic 각 조건에 따라 compare 함수를 커스텀해서 정렬하면 된다. 2. Code #include #include #include using namespace std; vector input; bool cmp(string a, string b) { //1번 조건 if(a.length() != b.length()) return a.length() < b.length(); //2번 ..
https://www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 1. Logic map을 사용해서 풀었다. 2. Code #include #include using namespace std; map m; int main() { long long ans = 0; long long n; cin >> n; while(n--) { long long a; cin >> a; m[a]++; ans = max(ans, m[a]); } for(auto &a : m) { ..
https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 1. Logic 우와 구현은 역시 까다롭다. 문제를 보자마자 최단거리 알고리즘을 사용해야 할 것같아서 BFS를 사용하려고 했지만 문제와 맞지 않아 DFS가 더 적절하다고 판단했다. 이유는 계속 탐색이 아니라 한번 시작해서 한번 실패하면 바로 종료되기 때문에? 그리고 방향을 유지해야하기 때문에! 로직은 문제에 있는 그대로 실수하지 않고 구현하면 된다..
https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 1. Logic 재귀로 들어가서 0이 되면 경우의 수 1을 count해준다. 다만 숫자가 크기 때문에 타입을 long long 으로 해줬다. 2. Code #include #include using namespace std; long long dp[1000001]; long long solve(long long n) { if(n == 0) return 1; else if(n < 0) return 0; long long &ret = dp[n]; if..
https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 1. Logic LIS약간 변형? str1과 str2의 문자가 같으면 이전최대길이에 +1을 해준다! 2. Code #include using namespace std; int dp[4001][4001]; string str1, str2; int solve(int s1, int s2) { if(s1 == str1.size() || s2 == str2.size()) return 0; int..
https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 1. Logic 동일한 경로의 비행기 노선이 있을 수 있기 때문에 기내식의 점수가 가장 높은 것 만을 입력받아줬다. 그리고 DP배열이 의미하는 바는 당연 가장 높은 기내식 점수이다. dp[도시의 번호][몇번째로 방문한 도시인지] 2. Code #include #include #include #include using namespace ..
https://www.acmicpc.net/problem/9657 9657번: 돌 게임 3 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 1. Logic 먼저 dp테이블의 의미는 dp[i] i개의 돌에서 턴을 잡은 사람의 승패 유무이다. 문제에서 1개, 3개, 4개를 가져갈 수 있다고 했고 항상 상근이가 먼저 시작한다고 했기 때문에 돌 갯수 | 우승자 1개 | 상근이 2개 | 창영이 3개 | 상근이 4개 | 상근이 항상 이렇게 이기고 이후는 이전에 메모이제이션 된 값으로 부분문제가 쪼개지기 때문에 DP로 풀 수 있다. 항상 두 사람이 완벽하게 게임을 한다고 했으며 항상 상근이가 먼저 시작하기 때문에 한번이라도 상근이가 이기는 경우가 생기면 해당 n개..
