건망증 환자의 뇌장하드

leetcode.com/problems/rotting-oranges/ Rotting Oranges - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2차원 배열에 오렌지가 담겨져 있다고 가정한다. 오렌지의 상태는 없는경우, 그냥 오렌지, 썩은 오렌지 요렇게 3개의 상태가 된다. 2차원 배열 내 썩은 오렌지가 있을 경우 1분마다 해당 오렌지를 기준으로 4방향으로 인접한 오렌지가 썩는다. 2차원 배열 내 오렌지들이 모두 썩을때 까지의 시간을 계산해야 된다. 만약 모..

leetcode.com/problems/symmetric-tree/ Symmetric Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 2진 tree가 주어지면 절반 나누어 왼쪽 오른쪽의 패턴이 일치하면 true, 그렇지 않으면 false를 반환하는 문제 #include #include #include using namespace std; //Definition for a binary tree node. struct TreeNode { int val; ..

위와 같은 2진트리가 주어질 때 화살표 방향처럼 가장자리만 출력하게 하는 문제 output : a b d h i p k q m n o g c //1. left edge 탐색 -> dfs 사용 // - root node에서 시작 // - left node가 있는지 없는지 확인 후 있으면 left node출력 // - left node가 없을 경우 rigth node출력 // - left/right node가 모두 없을 경우 left edge탐색 완료 //2. bottom edge 탐색 // - 1번 로직을 계속 진행하면서 최하단 node를 만나면 출력 //3. 1번/2번 logic이 종료된 후 다른 logic으로 실행 // - root node에서 시작 // - right node가 있는지 없는지 확인 후..

leetcode.com/problems/maximum-depth-of-n-ary-tree/ Maximum Depth of N-ary Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com DFS로 푸는 문제이다. 2진트리가 주어지면 최대 depth를 return #include #include #include using namespace std; // Definition for a Node. class Node { public: int val; vector ..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정수의 집합을 두번 나누어 입력하고 두번째 정수 집합의 원소를 기준으로 첫번째 정수 집합 내 같은 정수가 있을 경우 1출력 없으면 2출력 #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); s..

www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 나무를 나무의 분포도를 출력하는 문제 문자열을 입력받고 해당 문자열이 총 얼마나 나왔는지 백분율로 계산하여 소수점 4자리까지 반올림하여 출력하는 문제이다. #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); map m; strin..

www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 사이트와 사이트에 맞는 비밀 번호를 입력해 둔 후 찾으려는 사이트의 비밀번호를 출력하는 문제 첫번째 줄에 사이트, password를 입력할 갯수(N)와, 비밀번호를 찾아야 되는 사이트의 수(M)를 입력 두번째 줄 부터 N번째 줄만큼 사이트와 비밀번호를 입력, N+1번째 줄 부터 N+M줄까지 비밀번호를 찾아야 되는 사이트를 입력 MAP을 사용하여 푸는 문제 #include #incl..

www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 수첩1과 수첩2에 각각 정수가 적혀져 있다. 각 수첩에 모두 존재하는 숫자가 있다면 1을 출력 아니라면 0을 출력하는 문제이다. 첫번째로 시도한 케이스는 단순하게 2중 반복문을 이용하여 문제를 제출했다. 코드를 조금씩 수정해 가며 풀어도 2중 반복문(O(n²))으로는 시간 초과가 난다. 좀더 빠른 문제풀이를 위하여 2진 탐색을 했다. #include #include #include using namespace std..