Per ardua ad astra.

문제 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. 입력 세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다. 출력 직사각형의 네 번째 점의 좌표를 출력한다. 예제 입력 1 5 5 5 7 7 5 예제 출력 1 7 7 예제 입력 2 30 20 10 10 10 20 예제 출력 2 30 10 출처 Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #1 1번 알고리즘 분류 구현 기하학 문제 출처 https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때,..

문제 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 x, y, w, h가 주어진다. 출력 첫째 줄에 문제의 정답을 출력한다. 제한 1 ≤ w, h ≤ 1,000 1 ≤ x ≤ w-1 1 ≤ y ≤ h-1 x, y, w, h는 정수 예제 입력 1 6 2 10 3 예제 출력 1 1 예제 입력 2 1 1 5 5 예제 출력 2 1 예제 입력 3 653 375 1000 1000 예제 출력 3 347 예제 입력 4 161 181 762 375 예제 출력 4 161 알고리즘 분류 수학 기하학 문제 출처 https://www.ac..

문제 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 때, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 입력 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다. 출력 주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다. 예제 입력 1 Red Alder Ash Aspen Basswood Ash Beech Yellow Birch Ash Cherry Cottonwood Ash Cypress Red Elm ..

문제 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 입력 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. 출력 첫째 줄에 S의 서로 다른 부분 문자열의 개수를 출력한다. 예제 입력 1 ababc 예제 출력 1 12 알고리즘 분류 자료 구조 문자열 해시를 사용한 집합과 맵 트리를 사용한 집합과 맵 문제 출처 https://www.a..

문제 자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 이때, 두 집합의 대칭 차집합의 원소의 개수를 출력하는 프로그램을 작성하시오. 두 집합 A와 B가 있을 때, (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 한다. 예를 들어, A = { 1, 2, 4 } 이고, B = { 2, 3, 4, 5, 6 } 라고 할 때, A-B = { 1 } 이고, B-A = { 3, 5, 6 } 이므로, 대칭 차집합의 원소의 개수는 1 + 3 = 4개이다. 입력 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200..

문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다. 듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다. 출력 듣보잡의 수와 그 명단을 사전순으로 출력한다. 예제 입력 1 복사 3 4 ohhenrie charlie baesangwook obama baesan..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,0..

문제 안녕? 내 이름은 이다솜. 나의 꿈은 포켓몬 마스터야. 일단 포켓몬 마스터가 되기 위해선 포켓몬을 한 마리 잡아야겠지? 근처 숲으로 가야겠어. (뚜벅 뚜벅) 얏! 꼬렛이다. 꼬렛? 귀여운데, 나의 첫 포켓몬으로 딱 어울린데? 내가 잡고 말겠어. 가라! 몬스터볼~ (펑!) 헐랭... 왜 안 잡히지?ㅜㅜ 몬스터 볼만 던지면 되는 게 아닌가...ㅜㅠ (터벅터벅) 어? 누구지? 오박사 : 나는 태초마을의 포켓몬 박사 오민식 박사라네. 다솜아, 포켓몬을 잡을 때는, 일단 상대 포켓몬의 체력을 적당히 바닥으로 만들어놓고 몬스터 볼을 던져야 한단다. 자, 내 포켓몬 이상해꽃으로 한번 잡아보렴. 포켓몬의 기술을 쓰는 것을 보고 포켓몬을 줄지 안줄지 결정을 하겠네. 자 한번 해보아라. 다솜아. 이다솜 : 이상해꽃이..

문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다. 입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다. 출력 첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다. 예제 입력 1 5 11 baekjoononlinejudge startlin..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이..

multiset(중복 집합) 특징연관 컨테이너(Associative Container) 중 하나이다.연관 컨테이너에는 set, multiset, map, multimap 이 있다.set과 비슷하지만, 중복된 키(Key)를 넣을 수 있다는 차이점이 있다.삽입된 요소들은 기본적으로 오름차순(less)으로 정렬된다. 헤더 파일multiset을 사용하려면 다음의 헤더 파일을 불러와야 한다.#include  멤버 함수 사용 방법set과 사용 방법이 비슷하다.바로가기 : https://dev-astra.tistory.com/247 [C++] set(집합)set(집합) 특징 연관 컨테이너(Associative Container) 중 하나이다. 연관 컨테이너에는 set, multiset, map, multimap 이 ..

set(집합) 특징연관 컨테이너(Associative Container) 중 하나이다.연관 컨테이너에는 set, multiset, map, multimap 이 있다.특정 순서에 따라 고유한 요소를 저장하는 컨테이너이다.기본적으로 요소들은 오름차순(less)으로 정렬되어 삽입된다.중복되는 요소는 없고, 오로지 희소한(Unique) 값만 저장된다.map과 거의 동일하지만, set은 map과 다르게 키(Key)와 값(Value)이 같다고 생각하면 된다.키(Key)라 불리는 요소들의 집합으로 이루어진 컨테이너라고 생각하면 된다.노드 기반 컨테이너이며, 균형 이진 트리로 구현되어 있다.이터레이터(Iterator)는 자동으로 중위 순회(Inordered Traversal)를 통하여 순서대로 키(Key)를 출력한다...

multimap(멀티 맵) 특징map과 거의 동일하지만, 키(Key) 값이 중복 가능한 컨테이너 키(Key)와 값(Value)이 삽입될 때, 키(Key)가 정렬이 되면서 삽입된다. 헤더 파일멀티 맵을 사용하려면 다음의 헤더 파일을 불러와야 한다.#include  멤버 함수 사용 방법map과 사용 방법이 비슷하다.바로가기 : https://dev-astra.tistory.com/244 [C++] 맵(Map)맵(Map) 특징 연관 컨테이너(Associative Container) 중 하나이다. 연관 컨테이너에는 set, multiset, map, multimap 이 있다. string : int 형태로 값을 할당해야 할 때 맵을 사용한다. 키(Key)와 값(Value) 형태로 이루dev-astra.tisto..

unordered_map 특징map보다 더 빠른 탐색을 하기 위한 컨테이너해시 테이블(Hash Table)을 기반으로 구현되었다.삽입, 삭제, 탐색에 대해서 $O(1)$ 정도의 시간 복잡도를 가진다. 가장 최악의 경우 $O(N)$ 정도의 시간 복잡도를 가진다.map의 삽입, 삭제 탐색 시간 복잡도는 $O(\log n)$ 이다.중복된 데이터를 허용하지 않는다.map에 비해 데이터가 많을 경우 월등히 좋은 성능을 보인다.하지만, 키(Key)가 유사한 데이터가 많을 경우, 해시 충돌로 인해 성능이 떨어질 수도 있다.  헤더 파일unordered_map을 사용하려면 다음의 헤더 파일을 불러와야 한다.#include  멤버 함수 사용 방법요소가 삽입될 때 키(Key)가 정렬되지 않는다는 것을 빼고는 map과 사용..

map(맵) 특징연관 컨테이너(Associative Container) 중 하나이다.연관 컨테이너에는 set, multiset, map, multimap 이 있다.string : int 형태로 값을 할당해야 할 때 맵을 사용한다.키(Key)와 값(Value) 형태로 이루어져 있고, 레드-블랙 트리(Red-Black Tree)라는 구조를 내장하고 있다.노드 기반으로 이루어져 있고, 균형 이진 트리 구조이다.pair 객체 형태로 키(Key)와 값(Value)이 저장된다.Key는 고유한 값이므로 중복이 불가능하다.중복 Key를 사용하려면 multimap을 사용하면 된다.삽입, 삭제, 탐색에 대해서 $O(logN)$ 정도의 시간 복잡도를 가진다.집합(Set)과 마찬가지로 삽입이 되면서 자동으로 정렬이 된다.데이..

문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 숫자란 어떤 수에 6이 적어도 3개이상 연속으로 들어가는 수를 말한다. 제일 작은 종말의 숫자는 666이고, 그 다음으로 큰 수는 1666, 2..

문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8..

이산 확률 변수 이산 확률 변수의 의미 동전을 두 번 던지는 게임에서 앞면이 나온 횟수를 `X` 로 나타내면, `X` 를 이용하여 앞면이 나온 횟수라는 특성에 따라 구분된 사건을 다음과 같이 간단히 표현할 수 있다. $$ \eqalign{ \{ HH \} &\Leftrightarrow X = 2 \\ \{ HT, TH \} &\Leftrightarrow X = 1 \\ \{ TT \} &\Leftrightarrow X = 0}$$ 그러므로 앞면이 나온 횟수인 `X` 는 아래와 같이 표본 공간 `S` 에서 실수 전체의 집합 `R` 로의 함수로 생각할 수 있다. 이 때 앞면이 나온 횟수인 `X` 를 확률 변수(Random Variable)라고 한다. 확률 변수(Random Variable) 표본 공간 `S`..

동치 관계와 부분 순서 관계 관계 `R` 이 어떤 성질을 갖느냐에 따라 관계에 의미를 부여하여 그 의미에 따라 관계의 순서쌍을 구성하는 원소들을 활용할 수 있다. 관계에 부여되는 의미에는 동치 관계나 부분 순서 관계가 있는데, 동치 관계의 경우 그 관계의 순서쌍을 구성하는 원소들이 같은 의미라는 것을 뜻하며, 부분 순서 관계의 경우는 그 관계의 순서쌍을 구성하는 원소들 사이에 순서가 존재한다는 것을 뜻한다. 동치 관계(Equivalence Relation) 반사 관계, 대칭 관계, 추이 관계가 모두 성립하는 관계 동치는 표현이 달라도 의미가 같아서 동등하게 사용할 수 있음을 의미한다. 예) 10진수 $7_{10}$ 과 2진수 $111_{2}$ 이 표현은 다르지만 같은 값으로 사용되므로 동치라고 할 수 있..

관계의 폐포 학번을 입력하면 학생의 이름을 비롯한 학생의 기타 정보를 검색할 수 있는 시스템이 있다고 하자. 하지만, 이 시스템은 등록된 전체 학생 중 재학생만 검색할 수 있다. 이 시스템에서 휴학생의 정보도 검색할 수 있으려면 휴학생의 학번과 정보도 추가해야할 것이다. 이처럼 자료 집합에 필요한 원소를 추가하여 특정 조건을 만족하도록 만드는 것을 관계의 폐포라고 한다. 관계의 폐포(Closure) 집합 `A` 에 대한 관계를 `R` 이라 하고 관계 `R` 이 가져야 하는 성질을 `P` 라고 할 때, 관계 `R` 을 포함하면서 성질 `P` 를 갖는 가장 작은 집합 `A` 에 대한 관계 `S` 성질 `P` 를 갖지 않는 관계 `R` 이 성질 `P`를 갖도록 순서쌍을 추가할 때는 반드시 필요한 최소한의 순서..

pair(페어)와 tuple(튜플) pair(페어)개념사용자가 지정한 2개의 타입의 데이터를 저장하기 위해 사용되는 클래스서로 연관된 2개의 데이터를 한 쌍으로 묶어서 다룰 때 사용하면 편리하다.구조체(struct) 대신 편리하게 2개의 데이터를 관리할 수 있다. 헤더 파일페어(pair)를 사용하려면 다음의 헤더를 불러와야 한다.#include 하지만, , 헤더를 사용할 경우, 헤더가 포함되어 있어 따로 불러와 주지 않아도 된다.#include // 헤더 포함#include // 헤더 포함 형태페어(pair)의 형태는 다음과 같다. template struct pair;T1에 첫 번째 인자를, T2에 두 번째 인자를 넣어주면 된다. 사용 방법초기화다음과 같이 페어(pair)를 초기..

문제 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼..

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력 첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다. 예제 입력 1 216 예제 출력 1 198 출처 ICPC > Regionals > Asia ..

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다. 이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다. N장의 카드에 써져 있는 숫자가 주어졌을 때, ..

브루트 포스(Brute Force) 개념 브루트(Brute)와 포스(Force)가 결합되어 만들어진 단어이며, "난폭한 힘(폭력)" 이라는 뜻이다. 문제 해결을 위해 오래 걸리고 자원이 많이 들어서 무식하다고 생각될 수도 있지만, 항상 100%의 정확성을 보인다. 정답(Solution)이 발견될 때까지 가능한 모든 선택지를 찾는 방법이다. 예) 4자리 숫자의 패스워드를 찾기 위해 0000부터 9999까지 하나씩 입력하여 찾아보는 경우 따라서 브루트 포스 알고리즘은 완전 탐색 알고리즘이라고 할 수 있다. 간단하고 일관적이지만, 매우 느리다는 단점이 있다. 거의 완벽하게 병렬 작업이 가능하여 병렬 프로그래밍에서 사용된다. 패턴 매칭(Pattern Matching) 등의 작업에 사용될 수 있다. 너비 우선 탐..

하노이 탑(Tower of Hanoi) 개념 프랑스의 수학자 에두아르 뤼카(François Édouard Anatole Lucas)가 1883년 소개한 유명한 문제 재귀(Recursion)를 연습하는데 도움이 되는 알고리즘 다음과 같이 3개의 막대와 N개의 원판(Disk)이 있을 때, 원판을 다음의 순서를 지키면서 A에서 C로 옮기는 작업 각 원판의 크기는 모두 다르다. 원판의 크기는 아래에서부터 위로 갈수로 점점 작아진다. ① 한 번에 하나의 원판만 이동한다. ② 맨 위에 있는 원판만 이동한다. ③ 크기가 작은 원판 위에 큰 원판을 쌓을 수 없다. 이 조건에서 다음을 구하는 것이 하노이 탑의 문제가 된다. ① 최소의 이동 횟수로 옮기는 가짓수 ($2^{N} - 1$) ② 최소의 이동 횟수로 옮길 때, ..

문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. 입력 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. 출력 첫째 줄에 옮긴 횟수 K를 출력한다. 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈..

문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 입력 첫째 줄에 $N$이 주어진다. $N$은 3의 거듭제곱이다. 즉 어떤 정수 $k$에 대해 $N=3^k$이며, 이때 $1 ≤ k < 8$이다. 출력 첫째 줄부터 N번째 줄까지 별을 출력한다. 예제 입력 1 27 예제 출력 1 ***************..

문제 오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자. 크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다. merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음) 4810 2613 2251 56.887% 문제 정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다. 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다. 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의 isPalindrome 함수는 주어진 문자열이 팰린드롬이면 1, 팰린드롬이 아니면 0을 반환하는 함수다. #incl..