본문 바로가기

코딩테스트(Coding Test)

(9)
백준 4150 - 피보나치 수 (BigInteger) ▷문제 : https://www.acmicpc.net/problem/4150 4150번: 피보나치 수 문제 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력하는 프로그램을 작성하여라. 예제 입력 1 복사 100 예제 출력 1 복사 354224848179261915075 힌트 해당 테스트 데이터의 모든 정답은 1000자를 넘지 않는다. ( f(20) = 6765 이므 www.acmicpc.net Note 피보나치 수를 구하는 알고리즘을 먼저 알아야 하는데 (재귀)피보나치 수열(Fibonacci Sequence) 를 ..
백준 10757 - 큰수 (문자열조작) ▷ 문제 : https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 첫째 줄에 A와 B가 주어진다. (0 0 2 10의..
백준 9442 - Sort Me (정렬, 룩업테이블) 문제 : https://www.acmicpc.net/problem/9442 9442번: Sort Me The input will contain one or more datasets. Each dataset will start with a line containing an integer n and a string s, where s is a permutation of the English uppercase alphabet, used as the Gorellians' alphabet in the coming year. The next n lines (1 www.acmicpc.net Note Sort Me 문제는 정렬 문제이긴 한데 정렬을 하기위한 비교함수와 문자열 비교함수를 직접 구현해야만 하는 문제이다. ..
백준 2947 - 나무조각 (버블정렬) ▷문제 : https://www.acmicpc.net/problem/2947 2947번: 나무 조각 문제 동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다. 동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치 www.acmicpc.net Note 이 문제는 알고리즘(Algorithm) → 정렬(Sort) → 거품정렬(Bubble Sort) 를 문제로 풀어 쓴 ..
백준 7785 - 회사에 있는 사람 문제링크 : https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 문제 상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다. 각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다. 상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성 www.acmicpc.net Note 이 문제는 출근시(enter) 사람의 이름을 특정 자료에 저장해 놓고 퇴근시(leave) 자료에서 삭제한 ..
백준 1620 - 나는야 포켓몬 마스터 이다솜 문제링크 : https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 www.acmicpc.net Note 이 문제는 해시테이블(HashTable) 자료구조를 이해하면 아주 쉽게 풀수 있는 문제이다. 해..
백준 5639 - 이진 검색 트리 문제링크 : https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 문제 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, www.acmicpc.net Note 이 문제를 풀기위한 설명은 이진탐색트리(Binary Search Tree) POST를 참고하면 되는데 pre..
백준 1920 - 수 찾기 문제링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다. www.acmicpc.net Note 이 문제는 N개의 정수 A[1], A[2], …, A[N] 중에서 입력된 정수가 있는지 없는지를 찾아야 하는 탐색(검색)문제이다. 사실 A[1], A[2], …, A[N] 중에서 특정 정수가 있는지 없는지 확인하기 위한 가장 간단한 방법은 선형(순차) 탐색(Linear..