개발일지

https://www.acmicpc.net/problem/13077 13077번: Sequence The first line of the input includes the number of test cases, 1 ≤ t ≤ 1000. Each test case consists of one line. This line contains p, followed by / and then q without any space between them. www.acmicpc.net 오늘 포스팅에서 다뤄볼 문제는 ICPC에서 출제된 트리문제이다. 문제 분석을 하자면, 루트는 1/1로 왼쪽수를 p 오른쪽수를 q라고 하고, 왼쪽 자식노드엔 p/p+q, 오른쪽 자식노드엔 p+q/q 를 갖도록 하는 이진트리의 구조를 갖는다. ..

https://www.acmicpc.net/problem/6615 6615번: 콜라츠 추측 입력은 몇개의 테스트 케이스로 구성된다. 각 테스트 케이스는 두개의 정수 A와 B가 주어진다. ( 1 ≤ A, B ≤ 1,000,000) 마지막 줄은 두개의 0으로 구성된다. www.acmicpc.net ICPC에서 출제됐던 흥미로운 문제를 다뤄보도록 하겠다. 문제에서 나와있는 콜라츠 추측은 다음과 같다. 임의의 숫자 i가 짝수인경우, i / 2 홀수인 경우 i * 3 + 1을 반복한다. 이 수열의 반복 결과는 1이된다. 문제에선 이 콜라츠추측이 옳다고 가정하에 두개의 정수를 주고 이 정수두개가 같은수가 되는 시점을 찾아 각각 몇번의 반복을 통해 같은수가 되는지 출력해주면 된다. 이 과정을 트리로 표현한다면, 루트..

https://www.acmicpc.net/problem/6800 6800번: Huffman Encoding The first line of input will be an integer k (1 ≤ k ≤ 20), representing the number of characters and associated codes. The next k lines each contain a single character, followed by a space, followed by the binary sequence (of length at most 10) represe www.acmicpc.net 이번에 다뤄볼 문제는 문자열을 다루는 문제이다. 처음 문제를 봤을때 그림때문에 트리문제인가 싶어 풀었지만, 트리문제라기보단..

https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 트리에 대해 복습하기 좋은 문제가 있어 가지고 왔다. 먼저 이진트리와 순회개념에 대해 숙지가 되어있지 않다면 하단의 링크를 참조하면 된다. https://0bliviat3.tistory.com/32 [자료구조] 이진 트리와 순회의 구현(JAVA) 이번 포스팅에서는 비선형 자료구조인 트리중 이진트리에 대해 다뤄보겠다. 우선 비선형 자료구조란 무엇인가 정의를 살펴보면, 비순차..

https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이 문제는 이중반복문으로 풀려하면 시간초과가 나는 문제로, 어느정도 수학적 접근이 필요하다. 먼저 문제분석을 하자면 연속된 부분 구간의 합이 m으로 나누어 떨어지는 구간의 개수를 구하면 된다. 전체 구간의 범위 n이 매우크기 때문에 단순하게 접근해서는 풀 수 없다. 이 문제를 풀기 위한 아이디어는 첫번째 수부터 n번째 수까지의 누적합을 구하되 그 과..