CODINGTEST
1.[PYTHON] 백준 2557 - Hello World
메모리: 113112 KB, 시간: 108 ms구현Hello World!를 출력하시오.없음Hello World!를 출력하시오.
2.[PYTHON] 백준 10869 - 사칙연산
메모리: 113248 KB, 시간: 112 ms수학, 구현, 사칙연산두 자연수 A와 B가 주어진다. 이때, A+B, A-B, A\*B, A/B(몫), A%B(나머지)를 출력하는 프로그램을 작성하시오.두 자연수 A와 B가 주어진다. (1 ≤ A, B ≤ 10,000)첫째
3.[PYTHON] 백준 2588 - 곱셈
메모리: 113112 KB, 시간: 108 ms수학, 사칙연산(세 자리 수) × (세 자리 수)는 다음과 같은 과정을 통하여 이루어진다.https://camo.githubusercontent.com/053c3071a8a86e0b13a83572064a125d46
4.[PYTHON] 백준 9498 - 시험 성적
메모리: 113112 KB, 시간: 116 ms구현시험 점수를 입력받아 90 ~ 100점은 A, 80 ~ 89점은 B, 70 ~ 79점은 C, 60 ~ 69점은 D, 나머지 점수는 F를 출력하는 프로그램을 작성하시오.첫째 줄에 시험 점수가 주어진다. 시험 점수는 0보다
5.[PYTHON] 백준 2753 - 윤년
메모리: 113112 KB, 시간: 116 ms수학, 구현, 사칙연산연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오.윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다.예를 들어, 2012년은 4의 배수이
6.[PYTHON] 백준 1085 - 직사각형에서 탈출
메모리: 113112 KB, 시간: 112 ms수학, 기하학한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을
7.[PYTHON] 백준 2739 - 구구단
메모리: 113112 KB, 시간: 116 ms수학, 구현N을 입력받은 뒤, 구구단 N단을 출력하는 프로그램을 작성하시오. 출력 형식에 맞춰서 출력하면 된다.첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 9보다 작거나 같다.출력형식과 같게 N1부터 N9까지 출력
8.[PYTHON] 백준 10950 - A+B - 3
메모리: 113112 KB, 시간: 112 ms수학, 구현, 사칙연산두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.첫째 줄에 테스트 케이스의 개수 T가 주어진다.각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (
9.[PYTHON] 백준 2438 - 별 찍기 - 1
메모리: 113112 KB, 시간: 116 ms구현첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.
10.[PYTHON] 백준 10871 - X보다 작은 수
메모리: 115588 KB, 시간: 136 ms구현정수 N개로 이루어진 수열 A와 정수 X가 주어진다. 이때, A에서 X보다 작은 수를 모두 출력하는 프로그램을 작성하시오.첫째 줄에 N과 X가 주어진다. (1 ≤ N, X ≤ 10,000)둘째 줄에 수열 A를 이루는 정
11.[PYTHON] 백준 2562 - 최댓값
메모리: 113112 KB, 시간: 112 ms구현9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오.예를 들어, 서로 다른 9개의 자연수3, 29, 38, 12, 57, 74, 40, 85, 61이
12.[PYTHON] 백준 8958 - OX퀴즈
메모리: 114488 KB, 시간: 124 ms구현, 문자열"OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 예를 들어, 10번 문제의
13.[PYTHON] 백준 4344 - 평균은 넘겠지
메모리: 114328 KB, 시간: 120 ms수학, 사칙연산대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다.첫째 줄에는 테스트 케이스의 개수 C가 주어진다.둘째 줄부터 각 테스트 케이스마다 학생의 수 N(
14.[PYTHON] 백준 2577 - 숫자의 개수
메모리: 113112 KB, 시간: 112 ms수학, 구현, 사칙연산세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.예를 들어 A = 150, B = 266, C
15.[PYTHON] 백준 15596 - 정수 N개의 합
메모리: 419048 KB, 시간: 20 ms수학, 구현, 사칙연산정수 n개가 주어졌을 때, n개의 합을 구하는 함수를 작성하시오.작성해야 하는 함수는 다음과 같다.EmptyEmpty
16.[PYTHON] 백준 11654 - 아스키 코드
메모리: 113112 KB, 시간: 112 ms구현알파벳 소문자, 대문자, 숫자 0-9중 하나가 주어졌을 때, 주어진 글자의 아스키 코드값을 출력하는 프로그램을 작성하시오.알파벳 소문자, 대문자, 숫자 0-9 중 하나가 첫째 줄에 주어진다.입력으로 주어진 글자의 아스키
17.[PYTHON] 백준 2675 - 문자열 반복
메모리: 113112 KB, 시간: 116 ms구현, 문자열문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다. S에는
18.[PYTHON] 백준 1152 - 단어의 개수
메모리: 122216 KB, 시간: 136 ms구현, 문자열영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.첫 줄에 영어
19.[PYTHON] 백준 2908 - 상수
메모리: 113112 KB, 시간: 112 ms수학, 구현상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다.
20.[PYTHON] 백준 2869 - 달팽이는 올라가고 싶다
메모리: 113112 KB, 시간: 112 ms수학땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다.달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다.달팽
21.[PYTHON] 백준 1978 - 소수 찾기
메모리: 113112 KB, 시간: 112 ms수학, 정수론, 소수 판정주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수
22.[PYTHON] 백준 9020 - 골드바흐의 추측
메모리: 117508 KB, 시간: 516 ms수학, 정수론, 소수 판정, 에라토스테네스의 체1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 =
23.[PYTHON] 백준 1065 - 한수
메모리: 114328 KB, 시간: 124 ms브루트포스 알고리즘어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한
24.[PYTHON] 백준 2628 - 종이자르기
메모리: 113112 KB, 시간: 108 ms정렬아래 <그림 1>과 같이 직사각형 모양의 종이가 있다. 이 종이는 가로방향과 세로 방향으로 1㎝마다 점선이 그어져 있다. 가로 점선은 위에서 아래로 1번부터 차례로 번호가 붙어 있고, 세로 점선은 왼쪽에서 오른쪽으
25.[PYTHON] 백준 10872 - 팩토리얼
메모리: 113112 KB, 시간: 120 ms수학, 구현, 조합론0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.첫째 줄에 정수 N(0 ≤ N ≤ 12)이 주어진다.첫째 줄에 N!을 출력한다.
26.[PYTHON] 백준 1914 - 하노이 탑
메모리: 153496 KB, 시간: 540 ms임의 정밀도 / 큰 수 연산, 재귀세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장
27.[PYTHON] 백준 9663 - N-Queen
메모리: 216816 KB, 시간: 30580 ms브루트포스 알고리즘, 백트래킹N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.첫째 줄에 N이 주
28.[PYTHON] 백준 1074 - Z
메모리: 113112 KB, 시간: 116 ms분할 정복, 재귀한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.N > 1인 경우, 배열
29.[PYTHON] 백준 2750 - 수 정렬하기
메모리: 114328 KB, 시간: 120 ms구현, 정렬N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보
30.[PYTHON] 백준 2751 - 수 정렬하기2
메모리: 199132 KB, 시간: 796 ms정렬N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,
31.[PYTHON] 백준 10989 - 수 정렬하기 3
메모리: 31256 KB, 시간: 9140 ms정렬N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작
32.[PYTHON] 백준 1181 - 단어 정렬
메모리: 119776 KB, 시간: 216 ms문자열, 정렬알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.길이가 짧은 것부터길이가 같으면 사전 순으로단, 중복된 단어는 하나만 남기고 제거해야 한다.첫째 줄에 단어
33.[PYTHON] 백준 2309 - 일곱 난쟁이
메모리: 113112 KB, 시간: 112 ms브루트포스 알고리즘, 정렬왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공
34.[PYTHON] 백준 10819 - 차이를 최대로
메모리: 120956 KB, 시간: 136 ms브루트포스 알고리즘, 백트래킹N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.|A0 - A1| + |A1 - A2| + ...
35.[PYTHON] 백준 10971 - 외판원 순회 2
외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1
36.[PYTHON] 백준 1920 - 수 찾기
메모리: 139992 KB, 시간: 256 ms자료 구조, 정렬, 이분 탐색N개의 정수 A1, A2, …, AN이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄
37.[PYTHON] 백준 2805 - 나무 자르기
메모리: 259740 KB, 시간: 568 ms이분 탐색, 매개 변수 탐색상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는
38.[PYTHON] 백준 2110 - 공유기 설치
메모리: 122888 KB, 시간: 212 ms이분 탐색, 매개 변수 탐색도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를
39.[PYTHON] 백준 2470 - 두 용액
정렬, 이분 탐색, 두 포인터KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리
40.[PYTHON] 백준 8983 - 사냥꾼
메모리: 116532 KB, 시간: 324 ms정렬, 이분 탐색KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고,
41.[PYTHON] 백준 11053 - 가장 긴 증가하는 부분 수열
메모리: 114488 KB, 시간: 128 ms다이나믹 프로그래밍수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {
42.[PYTHON] 백준 10828 - 스택
메모리: 116572 KB, 시간: 168 ms자료 구조, 스택정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 다섯 가지이다.push X: 정수 X를 스택에 넣는 연산이다.pop: 스택에서 가장 위에 있는 정수를
43.[PYTHON] 백준 10773 - 제로
메모리: 118100 KB, 시간: 152 ms자료 구조, 구현, 스택나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다.재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤
44.[PYTHON] 백준 9012 - 괄호
메모리: 114488 KB, 시간: 136 ms자료 구조, 스택, 문자열괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열
45.[PYTHON] 백준 17608
메모리: 122492 KB, 시간: 400 ms자료 구조, 구현, 스택아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 6, 9,
46.[PYTHON] 백준 2493
메모리: 223372 KB, 시간: 308 ms자료 구조, 스택KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각
47.[PYTHON] 백준 2504 - 괄호의 값
메모리: 157092 KB, 시간: 184 ms자료 구조, 그리디 알고리즘, 스택N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
48.[PYTHON] 백준 2812 - 크게 만들기
메모리: 157092 KB, 시간: 184 ms자료 구조, 그리디 알고리즘, 스택N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
49.[PYTHON] 백준 18258 - 큐 2
메모리: 258788 KB, 시간: 1192 ms자료 구조, 큐정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.명령은 총 여섯 가지이다.push X: 정수 X를 큐에 넣는 연산이다.pop: 큐에서 가장 앞에 있는 정수를 빼고,
50.[PYTHON] 백준 2164 - 카드2
메모리: 128136 KB, 시간: 188 ms자료 구조, 큐N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을
51.[PYTHON] 백준 11866 - 요세푸스 문제 0
메모리: 116108 KB, 시간: 152 ms자료 구조, 구현, 큐요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어
52.[PYTHON] 백준 3190 - 뱀
메모리: 116472 KB, 시간: 176 ms자료 구조, 덱, 구현, 큐, 시뮬레이션'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝
53.[PYTHON] 백준 11279 - 최대 힙
메모리: 118528 KB, 시간: 252 ms자료 구조, 우선순위 큐널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거
54.[PYTHON] 백준 1655 - 가운데를 말해요
메모리: 130680 KB, 시간: 472 ms자료 구조, 우선순위 큐백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수
55.[PYTHON] 백준 1715 - 카드 정렬하기
메모리: 121784 KB, 시간: 448 ms자료 구조, 그리디 알고리즘, 우선순위 큐정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의
56.[PYTHON] 백준 13334 - 철로
메모리: 128048 KB, 시간: 416 ms자료 구조, 우선순위 큐, 정렬, 스위핑집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위
57.[PYTHON] 백준 5904 - Moo 게임
메모리: 113112 KB, 시간: 112 ms분할 정복, 재귀Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다.Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다.Moo 수열은 다음과 같은 방법
58.[PYTHON] 백준 16120 - PPAP
메모리: 188052 KB, 시간: 268 ms자료 구조, 그리디 알고리즘, 스택, 문자열bryan은 PPAP를 좋아한다. bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.PPAP 문자열은 문자열
59.[PYTHON] 백준 10830 - 행렬 제곱
메모리: 114488 KB, 시간: 124 ms분할 정복, 분할 정복을 이용한 거듭제곱, 선형대수학, 수학크기가 N\*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머
60.[PYTHON] 백준 2178 - 미로 탐색
메모리: 116456 KB, 시간: 200 ms너비 우선 탐색, 그래프 이론, 그래프 탐색N×M크기의 배열로 표현되는 미로가 있다.미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여
61.[PYTHON] 백준 18352 - 특정 거리의 도시 찾기
성능 요약 메모리: 161420 KB, 시간: 1404 ms 분류 너비 우선 탐색, 데이크스트라, 그래프 이론, 그래프 탐색 문제 설명 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시
62.[PYTHON] 백준 7569 - 토마토
메모리: 213344 KB, 시간: 724 ms너비 우선 탐색, 그래프 이론, 그래프 탐색철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관
63.[PYTHON] 백준 3055 - 탈출
메모리: 116604 KB, 시간: 160 ms너비 우선 탐색, 그래프 이론, 그래프 탐색사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도
64.[PYTHON] 백준 2294 - 동전 2
메모리: 116580 KB, 시간: 156 ms다이나믹 프로그래밍n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동
65.[PYTHON] 백준 1991 - 트리 순회
메모리: 113112 KB, 시간: 116 ms재귀, 트리이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들
66.[PYTHON] 백준 5639 - 이진 검색 트리
메모리: 449416 KB, 시간: 3464 ms그래프 이론, 그래프 탐색, 재귀, 트리이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키
67.[PYTHON] 백준 1197 - 최소 스패닝 트리
메모리: 131776 KB, 시간: 372 ms최소 스패닝 트리, 그래프 이론그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트
68.[PYTHON] 백준 1260 - DFS와 BFS
메모리: 117916 KB, 시간: 188 ms그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼
69.[PYTHON] 백준 11724 - 연결 요소의 개수
메모리: 179788 KB, 시간: 416 ms그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.첫째 줄에 정점의 개수 N과 간선의 개수
70.[PYTHON] 백준 2606 - 바이러스
메모리: 113112 KB, 시간: 124 ms그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에
71.[PYTHON] 백준 11725 - 트리의 부모 찾기
메모리: 68244 KB, 시간: 332 ms그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.첫째 줄에 노드의 개수 N (2 ≤ N
72.[PYTHON] 백준 1707 - 이분 그래프
메모리: 230372 KB, 시간: 1288 ms너비 우선 탐색, 이분 그래프, 깊이 우선 탐색, 그래프 이론, 그래프 탐색그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프
73.[PYTHON] 백준 14888 - 연산자 끼워넣기
메모리: 115360 KB, 시간: 152 ms백트래킹, 브루트포스 알고리즘N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷
74.[PYTHON] 백준 2573 - 빙산
메모리: 218500 KB, 시간: 748 ms너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의
75.[PYTHON] 백준 2617 - 구슬 찾기
메모리: 115272 KB, 시간: 124 ms깊이 우선 탐색, 플로이드–워셜, 그래프 이론, 그래프 탐색모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무
76.[PYTHON] 백준 1916 - 최소비용 구하기
메모리: 125732 KB, 시간: 228 ms데이크스트라, 그래프 이론N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서
77.[PYTHON] 백준 1388 - 바닥 장식
https://www.acmicpc.net/problem/1388메모리: 116048 KB, 시간: 140 ms깊이 우선 탐색, 그래프 이론, 그래프 탐색, 구현형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는
78.[PYTHON] 백준 2667 - 단지번호붙이기
https://www.acmicpc.net/problem/2667메모리: 114488 KB, 시간: 120 ms너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이
79.[PYTHON] 백준 18405 - 경쟁적 전염
https://www.acmicpc.net/problem/18405메모리: 118172 KB, 시간: 272 ms너비 우선 탐색, 그래프 이론, 그래프 탐색, 구현NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스
80.[PYTHON] 백준 2748 - 피보나치 수 2
메모리: 113112 KB, 시간: 128 ms다이나믹 프로그래밍, 수학피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 +
81.[PYTHON] 백준 1904 - 01타일
https://www.acmicpc.net/problem/1904메모리: 122144 KB, 시간: 136 ms다이나믹 프로그래밍지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이
82.[PYTHON] 백준 9084 - 동전
https://www.acmicpc.net/problem/9084메모리: 114328 KB, 시간: 124 ms다이나믹 프로그래밍, 배낭 문제우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금
83.[PYTHON] 백준 9251 - LCS
메모리: 119708 KB, 시간: 144 ms다이나믹 프로그래밍, 문자열LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.예를 들어, ACAYK
84.[PYTHON] 백준 12865 - 평범한 배낭
https://www.acmicpc.net/problem/12865메모리: 115112 KB, 시간: 156 ms다이나믹 프로그래밍, 배낭 문제이 문제는 아주 평범한 배낭에 관한 문제이다.한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과
85.[PYTHON] 백준 11049 - 행렬 곱셈 순서
https://www.acmicpc.net/problem/11049 성능 요약 메모리: 117556 KB, 시간: 884 ms 분류 다이나믹 프로그래밍 문제 설명 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다.
86.[PYTHON] 백준 11053 - 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053메모리: 114488 KB, 시간: 120 ms다이나믹 프로그래밍수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10
87.[PYTHON] 백준 2253 - 외판원 순회
https://www.acmicpc.net/problem/2253메모리: 138348 KB, 시간: 236 ms다이나믹 프로그래밍N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은
88.[PYTHON] 백준 11047 - 동전 0
https://www.acmicpc.net/problem/11047메모리: 113112 KB, 시간: 116 ms그리디 알고리즘준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고
89.[PYTHON] 백준 1541 - 잃어버린 괄호
https://www.acmicpc.net/problem/1541메모리: 113248 KB, 시간: 112 ms그리디 알고리즘, 수학, 파싱, 문자열세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고
90.[PYTHON] 백준 1931 - 회의실 배정
메모리: 125232 KB, 시간: 432 ms그리디 알고리즘, 정렬한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사
91.[PYTHON] 백준 1946 - 신입 사원
https://www.acmicpc.net/problem/1946메모리: 221156 KB, 시간: 6108 ms그리디 알고리즘, 정렬언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면
92.[PYTHON] 백준 1700 - 멀티탭 스케줄링
https://www.acmicpc.net/problem/1700메모리: 113112 KB, 시간: 124 ms그리디 알고리즘기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등
93.[프로그래머스] 합승 택시 요금
https://school.programmers.co.kr/learn/courses/30/lessons/72413합승 택시 요금본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이
94.[프로그래머스] 하노이의 탑
https://school.programmers.co.kr/learn/courses/30/lessons/12946하노이의 탑하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐
95.[프로그래머스] 무인도 여행
https://school.programmers.co.kr/learn/courses/30/lessons/154540무인도 여행메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는
96.[프로그래머스] 전력망을 둘로 나누기
https://school.programmers.co.kr/learn/courses/30/lessons/86971전력망을 둘로 나누기n개의 송전탑이 전선을 통해 하나의 트리 형태로 연결되어 있습니다. 당신은 이 전선들 중 하나를 끊어서 현재의 전력망 네트워크를