Doby's Lab

https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 트리 순회에는 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)를 제외하고도 여러 가지 순회 방법이 있다. 이번 문제에서는 3가지 순회만 다룬다. 전위 순회(preorder traversal): [루트] [왼쪽 서브 트리] [오른쪽 서브 트리] 중위 순회(inorder traversal): [왼..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 솔루션 1) 로프가 들어올 수 있는 각 중량을 입력받아 내림차순으로 정렬한다. 2) 배열에 맨 마지막엔 들어 올릴 수 있는 최솟값이 들어있을 것이다. 3) 그 최솟값과 배열의 사이즈를 곱하면 배열에 들어있는 로프들로 들어 올릴 수 있는 최대 중량이 된다. 4) 맨 뒤 원소를 pop 하고, 2~3 과정을 반복한다. 5) 그 과정에서 최댓값(최대 중량)을 구한다. [AC 코드] #includ..

https://www.acmicpc.net/problem/1166 1166번: 선물 민식이는 아이들에게 선물할 같은 크기의 작은 박스를 N개 가지고 있다. 모든 작은 박스는 정육면체이고, 크기는 A × A × A 이다. 민식이는 이 작은 박스를 크기가 L × W × H 인 직육면체 박스에 www.acmicpc.net 이번 문제는 간단히 이분 탐색이라기보다 부가적인 요소로 신경 써야 할 것이 많은 문제였다. 자료형 while을 이용한 이분 탐색이 아닌 for문을 이용해야 함 (혹은 double이 아닌 long double로 선언) 출력은 실수형 솔루션 (+참고 https://vision-ary.tistory.com/2) 1) 자료형 l, w, h가 주어졌을 때 최댓값이 1e27이 되어 long long을 ..

https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 2차원 배열을 활용하여 BFS로 풀 수 있었다. int emozi[현재 클립보드][현재 화면에 있는 이모티콘 수]; 이렇게 두고 '현재 화면에 있는 이모티콘 수'가 s가 되면 시간이 얼마큼 흘렀는지 출력하게끔 BFS를 짜주면 된다. 3가지 모든 연산의 가중치가 1이라 가능했다. [AC 코드] 의문점 (틀왜맞?): 주어진 범위는 1000 이하가 맞으나 MAX가 1000 + 1인데 되는 이유가 무엇일까..

종종 BFS나 DP를 풀 때 2차원 배열이라는 키워드를 고려하면 쉽게 풀리는 경우가 있다. 꼭 행과 열의 의미가 아니라 각각 행의 의미와 열의 의미를 다르게 주어 풀 수 있다. 2차원 배열이라는 키워드 꼭 리마인드 하기

https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 이번 문제는 TC를 통해 규칙을 파악했다. TC #1 3 4 TC #2 3 6 TC #3 500000000000000000 500000000000000002 분명 주어진 입력값만큼 1의 개수라는 말인데 어째서인지 입력값끼리의 최대공약수도 똑같다는 것을 발견했다. TC #2를 보면 3 6으로 111과 111111의 최대공약수를 구하는 것이다. 물론 111*1001 = 11111..

https://www.acmicpc.net/problem/13423 13423번: Three Dots 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,000)이 주어 www.acmicpc.net 이 문제는 3가지 점 모두 브루트 포스로 구하면 시간 초과가 난다. Worst Case: O(n^3) => O(1000^3) 솔루션 두 점까지는 브루트 포스로 구하고, 나머지 한 점은 2번째 점과 1번째 점의 차이를 만족하도록 고르는 점과 2번째 점의 차이가 같은 점을 이분 탐색으로 구해주었다. >> 이분 탐색을 위해 입력받은 점들을 정렬해주었다. #include #incl..

https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 1. 주어진 N을 B로 나머지 연산 후 그 값을 'B진법'으로 바꾼다. 2. B진법으로 바꾼 값을 결과 문자열에 더한다. 3. 다음 값을 위해 N을 B로 나눠준다. 4. 1~3번 과정이 끝나면 결과 문자열을 뒤집는다. #include #include #include using namespace std; char change(int value) { if (value > N >> B; strin..