본문 바로가기
728x90
반응형

분류 전체보기141

[백준(Baekjoon)] 1260. DFS와 BFS [백준(Baekjoon)] 1260. DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [입력] 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. [출력] 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 B.. 2021. 8. 26.
[백준(Baekjoon)] 2257. 화학식량 [백준(Baekjoon)] 2257. 화학식량 2257번: 화학식량 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. www.acmicpc.net [입력] 첫째 줄에 화학식이 주어진다. 화학식은 H, C, O, (, ), 2, 3, 4, 5, 6, 7, 8, 9만으로 이루어진 문자열이며, 그 길이는 100을 넘지 않는다. [출력] 첫째 줄에 화학식량을 출력한다. 분자량이 10,000이 넘는 고분자는 입력으로 주어지지 않는다. [풀이] 각 화학식을 H -> 1 C -> 12 O -> 16 으로 변환해주어 계산해주는 문제이다. 위 문자와 숫자를 HashMap을 사용하여 저장해주었다. 스택을 .. 2021. 8. 25.
[백준(Baekjoon)] 1759. 암호 만들기 [백준(Baekjoon)] 1759. 암호 만들기 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net [입력] 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. [출력] 각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다. [풀이] 우선 C개의 문자열에서 L개의 문자를 택하여 암호를 만드는 방식이라 순열을 사용했다. 순열 사용하여 암호를 만들면서 암호길이가 2이상일 경우 .. 2021. 8. 24.
[백준(Baekjoon)] 17086. 아기 상어 2 [백준(Baekjoon)] 17086. 아기 상어 2 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. www.acmicpc.net [입력] 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸의 개수가 한 개 이상인 입력만 주어진다. [출력] 첫째 줄에 안전 거리의 최댓값을 출력한다. [풀이] 문제를 보자마자 BFS가 생각났는데 변형하는 과정에서 조금 버벅였다. 8방탐색하며 거리마다 1씩 더.. 2021. 8. 24.
[백준(Baekjoon)] 2407. 조합 [백준(Baekjoon)] 2407. 조합 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net [입력] n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) [출력] nCm을 출력한다. [풀이] 재귀로 풀 수 있지만 이 경우엔 시간초과가 발생한다. 그래서 다이나믹 프로그래밍을 이용했다. n과 m은 모두 100이하이다. 배열을 100으로 만들면 인덱스는 99까지 존재하기 때문에 배열을 더 편리하게 사용하기 위해 101로 설정하였다. 1C1과 1C0은 1이다. 그리고 10C1 은 10인데 이것은 9C1 + 9C9 와 같다. 즉 nCr = n-1Cr + n-1Cr-1 이다. 이 식을 사용하여 배열을 채워준.. 2021. 8. 16.
[백준(Baekjoon)] 2961. 도영이가 만든 맛있는 음식 [백준(Baekjoon)] 2961. 도영이가 만든 맛있는 음식 2961번: 도영이가 만든 맛있는 음식 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 www.acmicpc.net [입력] 첫째 줄에 재료의 개수 N(1 ≤ N ≤ 10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다. [출력] 첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다. [풀이] 재료를 조합하는 경우이고 선택.. 2021. 8. 13.
[백준(Baekjoon)] 3040. 백설 공주와 일곱 난쟁이 [백준(Baekjoon)] 3040. 백설 공주와 일곱 난쟁이 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net [입력] 총 아홉개 줄에 1보다 크거나 같고 99보다 작거나 같은 자연수가 주어진다. 모든 숫자는 서로 다르다. 또, 항상 답이 유일한 경우만 입력으로 주어진다. [출력] 일곱 난쟁이가 쓴 모자에 쓰여 있는 수를 한 줄에 하나씩 출력한다. [풀이] 조합을 구하는 문제이다. 9개 중 순서 상관없이 7개를 택하여 그 합이 100이 되는 것만 출력한다. 조합은 재귀를 이용해서 구현했다. publi.. 2021. 8. 13.
[백준(Baekjoon)] 2563.색종이 [백준(Baekjoon)] 2563.색종이 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net [입력] 첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다 [출력] 첫째 줄에 색종이가 붙은 검은 .. 2021. 8. 11.
[백준(Baekjoon)] 2493. 탑 [백준(Baekjoon)] 2493. 탑 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [입력] 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다. [출력] 첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하.. 2021. 8. 10.
728x90
반응형