백준 초급
1.백준 9093 단어 뒤집기
문장이 주어졌을 때, 단어를 모두 뒤집어서 출력하는 프로그램을 작성하시오. 단, 단어의 순서는 바꿀 수 없다. 단어는 영어 알파벳으로만 이루어져 있다.첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다.
2.백준 9012 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “(
3.백준 1874 스택 수열
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out
4.백준 1406 에디터
한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽)
5.백준 1158 요세푸스 문제
요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모
6.백준 17413 단어 뒤집기2
문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.문자열의 시작과 끝은 공백이 아니
7.백준 10799 쇠막대기
한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. 괄호가 나오면 열에 아홉은 stack문제이다...여는 괄호를 만나면 무조건 push, 닫는 괄호를 만나면 그 앞 요소를 살펴보고 여는 괄호이면 레이
8.백준 17298 오큰수
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를
9.백준 1935 후위 표기식2
후위 표기식과 각 피연산자에 대응하는 값들이 주어져 있을 때, 그 식을 계산하는 프로그램을 작성하시오.첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로
10.백준 10808 알파벳 개수
알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.알파벳 문자열을 만든다.map을 만들어 알파뱃
11.백준 10809 알파벳 찾기
알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳
12.백준 10820 문자열 분석
문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오.각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있다첫째 줄부터 N번째 줄까지 문자열이 주어진다. (1 ≤ N ≤ 100) 문자열
13.백준 11655 ROT13
ROT13은 카이사르 암호의 일종으로 영어 알파벳을 13글자씩 밀어서 만든다.예를 들어, "Baekjoon Online Judge"를 ROT13으로 암호화하면 "Onrxwbba Bayvar Whqtr"가 된다. ROT13으로 암호화한 내용을 원래 내용으로 바꾸려면 암호
14.백준 10824 네 수
네 자연수 A, B, C, D가 주어진다. 이때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오.두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다.첫째 줄에 네 자연수 A, B
15.백준 11656 접미사 배열
접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열이다.baekjoon의 접미사는 baekjoon, aekjoon, ekjoon, kjoon, joon, oon, on, n 으로 총 8가지가 있고, 이를 사전순으로 정렬하면, aekjoon, baekj
16.백준 2309 일곱 난쟁이
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지
17.백준 1476 날짜 계산
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때,
18.백준 1107 리모컨
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로
19.백준 6064 카잉 달력 (해결 x)
최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 &l
20.백준 1748 수 이어 쓰기1 (수학)
1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.1234567891011121314151617181920212223...이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.첫째 줄에 N(1 ≤ N
21.백준 9095 1, 2, 3 더하기
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작
22.백준 15650 N과 M(2)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다.첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)조합 구
23.백준 15651 N과 M(3)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)중복을 허용하는 순
24.백준 15649 N과 M(1)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)dfs를 이용해 풀 수 있다.인프런 강의
25.백준 15652 N과 M (4)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤
26.백준 15654 N과 M(5)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의
27.백준 15655 N과 M(6)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열고른 수열은 오름차순이어야 한다.첫째 줄에 N과 M이 주어진다. (1 ≤ M
28.백준 15656 N과 M(7)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.첫째 줄에 N과 M이 주어진다. (1 ≤ M
29.백준 15657 N과 M(8)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.고른 수열은 비내림차순이어야 한다.길이가 K인
30.백준 15663 N과 M(9)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수
31.백준 15664 N과 M (10)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열고른 수열은 비내림차순이어야 한다.길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면
32.백준 15665 N과 M (11)
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)둘째 줄에 N개의 수가
33.백준 15666 N과 M (12)
같은 요소로 중복 제거한 조합
34.백준 10972 다음 순열
입력이 최대 10,000이라 백트래킹(재귀)로는 풀 수 없다.규칙을 알아내 이용해서 풀어야한다.문자를 뒤에서부터 탐색하며 오름차순이 끊나는 인덱스를 찾는다.그리고 그 문자보다 큰 값 중 작은 값을 다시 뒤에서부터 찾은 다음 교환해준다.그리고 찾은 인덱스 뒤에 부분은 정
35.백준 10974 모든 순열
문제 제한 사항 입출력 예 풀이
36.백준 10819 차이를 최대로 (백트래킹)
최대값이 되는 경우를 특정할 수 없어서 모든 경우를 비교했다.
37.백준 10971 외판원 순회 2
dfs에 약간의 아이디어를 더해 완성 시켰다. 매개변수를 활용해 문제를 쉽게 만들 수 있는 것을 기억하자.
38.백준 6603 로또 (백트래킹)
조합문제이다.입력, 출력을 착각해서 괜한 시간을 잡아먹었다. 잘 읽자!
39.백준 9095 1, 2, 3 더하기
다이나믹 프로그래밍 방식의 해법이다.0 -> 0, 1 -> 1, 2 -> 2, 3 -> 4 이고 이걸 answer배열에 넣는다.4부터는 앞 요소 3개를 더한것이 값이 된다. 즉 1 + 2 + 4 = 7 이된다.깊이 우선 탐색 방식으로 풀었다.입력이 크기 않아서 가능했다
40.백준 1759 암호 만들기
조합구하기 문제이다.조건 몇가지가 추가로 있다.
41.백준 14501 퇴사
다이나믹 프로그래밍 방식으로 풀어야한다.i는 idex이면서도 몇일째 인지를 표현해준다. 그래서 i + cost의 값을 비교하는 조건문을 사용하였다.최대값을 넘어가면 할 수 없는 일이니 다음 요소를 본다.넘어가지 않았다면 dp배열에 값을 누적한다. 그리고 i+cost 인
42.백준 1182 부분수열의 합 (백트래킹)
부분 집합 알고리즘s가 0일 경우에만 -1해주는데 그이유는 아무것도 포함안한것 부분집합의 합이 0이기 때문에 그것은 제외해준 것이다.
43.백준 13023 ABCDE
서로 다른 노드끼리 연속적으로 4번 연결되면 조건을 만족한다.그래서 dfs의 조건문이 저런식으로 나왔다.인접행렬로 graph를 표현했을 때 시간초과가 나와서 인접리스트로 바꿨다.
44.백준 1260 DFS와 BFS
이상하게 애를 먹었다.함수를 나눴으면 좀 더 예뻣을텐데 나중에 시도해보자.
45.백준 11724 연결 요소의 개수
프로그래머스 섬의 개수 문제와 동일한 문제이다.
46.백준 1707 이분 그래프
임시
47.백준 2667 단지번호붙이기
마찬가지로 섬의 개수와 비슷한 유형의 문제이다.카운트를 어디서 하냐에 따라 마을의 수, 아파트의 수가 갈린다.아파트의 수를 카운트하려면 dfs론 안될 것 같아서 풀다가 bfs로 바꿨다.
48.백준 2178 미로탐색
인프런 미로탐색과는 조금 다르다.그 문제는 가능한 경로의 개수이고, 이문제는 최단거리이다.최단거리이기 때문에 bfs로 푸는 것이 좋다.dis배열은 값을 누적해나가기 때문에 잘 활용하면 문제를 푸는데 꽤 도움이 된다.
49.백준 7576 토마토
bfs의 변형 문제이다.처음에 토마토가 들어있는 좌표를 큐에 넣어주고 bfs를 시작한다.zeroCount 변수를 이용해 0의 개수를 세어준다.queue.shift()를 사용하면 되지만 수행시간 이슈가 생겨서 index변수를 이용했다.
50.백준 16929 Two Dots
모든 점은 시작 점이 될 수 있다.내부 dfs를 돌면서 시작점과 같은 알파벳이고 방문하지 않은곳은 방문하고 그렇지 않은 곳은 지나친다.cnt가 4이상(최소 사각형)에 다음점이 시작점과 같아지는 순간이 오면 flag에 1을 할당해 리턴 조건을 만족 시켜준다.중요한 포인트
51.백준 2146 다리 만들기
dfs를 이용해 섬에 번호를 부여한다.1번째로 방문한 육지와 그와 연결된 땅은 전부 1, 2번째로 방문한 육지와 그와 연결된 땅은 전부 2가 되는 것.bfs를 이용해 다음 섬까지의 거리를 측정(코드의 주석 참고)
52.백준 1697 숨바꼭질
인프런 강의에 비슷한 문제가 있는데, 거기선 dis배열을 만들어 값을 저장했지만 여기선 큐에 넣을 때 변수를 하나 더 추가하는 식으로 풀었다.주석은 dis배열을 사용하는 방식이다.
53.백준 13913 숨바꼭질 4
숨바꼭질 문제의 업그레이드 버전path 배열을 만들고 경로에 이전 값을 넣어주고 후에 추적할 때 사용한다.
54.백준 14226 이모티콘
클립보드의 처리가 중요하다.클립보드도 노드마다 개별의 값을 가져야하기 때문에 visited 배열을 2차원 배열로 선언하고 노드의 방문과 클립보드의 방문 여부를 확인한다.
55.백준 13549 숨바꼭질 3
\*2하는 경우가 시간이 추가되지 않는 것으로 바뀌었다.시간이 늘어나지 않은 것을 먼저 처리해줘야 함으로 unshift를 이용해 큐의 가장 앞에 넣어줬다.
56.백준 1261 알고스팟
벽을 안 부시는걸 먼저 처리해줘야 함으로 unshift를 사용해줬다.
57.백준 1991 트리 순회
백트래킹을 이용하고, 정답을 나타낼 result 문자열에 더하는 타이밍에 따라 전위, 중위, 후위 순회가 나뉜다.인프런 강의에 비슷한 문제가 있다.
58.백준 11725 트리의 부모 찾기
인접 리스트 형태로 tree를 생성한다.bfs를 이용하고 check 배열에 부모노드를 저장한다.예를 들어 check 노드 4번 인덱스의 값이 5이면 3번노드의 부모노드가 5라는 뜻이다.
59.백준 1644 소수의 연속합 (투포인터)
아래 코드론 해결이 안됐는데 왜 그런지 모르겠다.
60.백준 1450 냅색 문제 (이분 탐색)
솔직히 잘 모르겠다. 일단 패턴을 외우도록 하자.배열을 반으로 나눈다.각 집합의 부분집합의 합을 포함하는 배열을 만들고 하나는 정렬해준다.이분탐색으로 조건을 만족하는 부분집합의 개수를 구한다.
61.백준 10430 나머지 (수학)
간단한 수학 구현 문제
62.백준 2609 최대공약수와 최소공배수 (수학)
최대공약수와 최소공배수유클리드 호제법
63.백준 1934 최소공배수 (수학)
최소공배수 입력을 복수로 받는 형태
64.백준 1929 소수 구하기 (수학)
숫자 범위가 정해진 소수 구하기
65.백준 1676 팩토리얼의 0의 개수 (수학)
뒤에서 부터 0을 구하는 것은 5로 몇번 나눌 수 있냐 묻는 문제임.정석은 2와 5로(2\*5 = 1이니까) 나눈 횟수 중 작은 값인데 5가 더 작을 수 밖에 없다.
66.백준 2004 조합 0의 개수 (수학)
조합 계산식 : n! / (n-m)! \* m!n!, (n-m)!, m!이 가지고 있는 2와 5의 개수를 각자 구하여 n!의 2의 개수에서 (n-m)!와 m!의 2의 개수를 합친 값을 뺀다. 5의 경우에도 동일한 방법으로 계산한다. 그냥 식이다.2의 개수, 5의 개수를
67.백준 9613 GCD 합 (수학)
최대공약수 응용 문제이다.
68.백준 17087 숨바꼭질 6 (수학)
동생들의 위치에서 수빈이의 위치를 뺀 절댓값을 새로운 배열에 저장해주고 그 배열 요소의 최대공약수가 답이된다.입출력 예제를 보고 구하는 법을 알아냈다.
69.백준 1373 2진수 8진수 (수학)
그냥 2진수를 10진수로 변경하면 2의 제곱의 값이 커져서 안 풀린다.그래서 2진수를 3자리씩 끊어서 10진수로 바꾸고 그것을 8진수로 바꾼 값을 oct에 누적한다.
70.백준 1212 8진수 2진수 (수학)
2진수 8진수 문제처럼 해줘야한다.
71.백준 2089 -2진수 (수학)
일단 외우거나 참고하도록 하자.
72.백준 11005 진법 변환 2 (수학)
js에서 진수 변환은 parseInt와 toString이면 해결된다.
73.백준 10828 스택 (자료구조)
class로 stack을 구현했다.
74.백준 10845 큐 (자료구조)
class로 큐 자료구조를 구현하여 풀었다.
75.백준 2745 진법 변환 (수학)
B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오.10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다.A: 10, B: 11, ..., F: 15, ..., Y: 34,
76.백준 11654 소인수분해 (수학)
정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.어떤 수를 2부터 차례대로 나누면서
77.백준 11399 ATM
인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게
78.백준 2606 바이러스
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1
79.백준 1012 유기농 배추
차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아
80.백준 24479 깊이 우선 탐색 1
오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든