23563번: 벽 타기 출발하자마자 오른쪽으로 한 칸 이동하고, 위로 한 칸 벽을 타고 이동하면 총 1의 시간이 소요된다. www.acmicpc.net 벽 타기를 하려면 내가 현재 있는 곳이 벽과 인접해야하고 내가 가야할 곳이 벽에 인접해야한다 최단경로를 구해야할 때 경로 중간에 최적의 경로가 생길 수 있다면 다익스트라로 구현해야한다 제목 벽 타기 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 루시우는 높이가 H이고 너비가 W인 맵의 시작점에서 끝점까지 이동하려고 한다. 맵은 H개의 행과 W개의 열로 이루어진 격자판 모양이다. 각 칸은 벽 또는 빈칸이다. 루시우는 상, 하, 좌, 우 방향 인접한 칸으로 한 칸씩 이동할 수 있다. 벽으로는 이동할 수 없다. 루시우가 한 칸을 이동하는 데에는 ..
실력진단 결과 코드트리 8주차 실력진단 결과 오늘의 학습 Parametric Search 다음 문제는 어떻게 해결해 볼 수 있을까요? 1부터 n까지의 자연수의 합이 100이상인 경우 중 가능한 n의 최솟값을 구하는 프로그램을 작성해보세요. 단, 답은 1에서 30사이라고 가정합니다. 무작정 코드를 작성한다면, 1, 2, 3 ..., 30 전까지 계속 더해보며 최초로 그 합이 100을 넘는 순간을 찾아 바로 그 직전의 숫자를 구하게 될 것입니다. 넘어야 하는 합을 s라 했을 때 시간복잡도는 O(S)가 됩니다. 하지만 만약 이 문제가 수학 문제로 나왔다면, 다음과 같이 시도하게 될 것입니다. 1차 시도 (n = 15) 1부터 15까지의 합은 120이므로, 일단 15은 답의 후보 중 하나입니다. 이제 더 작은 ..
실력진단 결과 코드트리 7주차 실력진단 결과 오늘의 학습 Tree DP 각 정점에 값이 적혀있는 트리 정보가 아래와 같이 주어졌을 때, 각각의 노드마다 자신을 포함하여 자손 노드들에 적혀있는 수들의 합을 구해보려고 합니다. 위 그림에서 예를 들어 6번 노드의 경우 자신을 포함한 자손 노드 번호가 6, 2, 3, 5 이므로 각 노드에 적혀있는 수들의 합인 2 + 3 + 3 + 4 = 12가 나와야 합니다. 즉, 우리가 얻고 싶은 결과는 아래와 같습니다. 이를 각 노드를 정한 뒤 해당 노드에서 자식 노드로 움직이는 것을 재귀적으로 반복하는 탐색을 진행하는 완전탐색 방법을 통해 구현한다면, 각 노드를 정하는데 O(N), 각 노드마다 최대 확인해야 하는 노드 수가 O(N)이 되어 총 O(N^2)의 시간복잡도를 ..
실력진단 결과 코드트리 6주차 실력진단 결과 오늘의 학습 Bitmask DP 다음 문제는 어떻게 해결해볼 수 있을까요? 아래와 같이 노드가 4개 간선이 x개 있는 양방향 그래프가 주어져있습니다. 3번 노드에서 시작하여 모든 노드를 정확히 한번씩만 방문하되, 이동거리의 합이 최소가 되도록 해보세요. 3번에서 시작하여 모든 정점을 단 한번씩만 방문해야 하는 문제이므로 가장 간단한 방법은 모든 순열을 만들어보는 백트래킹을 이용하는 것입니다. 백트래킹을 이용해 모든 순열을 만드는 방법에 대해 아직 잘 모르신다면, 순열 만들기 유형을 공부하시고 나서 다시 이 설명을 읽는 것을 추천드립니다. 수열 만들기 링크 : https://www.codetree.ai/missions/2/problems/n-permutation..
실력진단 결과 코드트리 5주차 실력진단 결과 오늘의 학습 Bit Operator 다양한 비트 연산자에 대해 다뤄보도록 하겠습니다. 비트 연산은 기본적으로 2진법을 기반으로 합니다. Bit 연산는 컴퓨터의 기본 연산이기에 속도가 굉장히 빠릅니다. and 연산자 (|) and 연산자 |는 두 수 a, b를 이진법으로 표현한 뒤 각 자리에 적혀있는 bit에 대해 and 연산을 진행한 후 그 결과를 다시 10진수로 표현해줍니다. and 연산이란 둘 다 1일 때만 1, 아니라면 0이 되는 연산입니다. 예를 들어 5 | 6은 4가 됩니다. 101 (5) 110 (6) and ---------- 100 (4) or 연산자 (|) or 연산자 |는 두 수 a, b를 이진법으로 표현한 뒤 각 자리에 적혀있는 bit에 ..
30017번: 치즈버거 만들기 승현이가 일하는 햄버거 가게에는 요리 재료로 사용할 햄버거 패티가 $A$개, 슬라이스 치즈가 $B$개 있다. 치즈버거를 만들기 위해서는 패티와 치즈를 각각 한 개 이상 고른 후 햄버거 빵 사이에 www.acmicpc.net 2 * A - 1와 2 * B + 1의 최소 제목 치즈버거 만들기 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 승현이가 일하는 햄버거 가게에는 요리 재료로 사용할 햄버거 패티가 A개, 슬라이스 치즈가 B개 있다. 치즈버거를 만들기 위해서는 패티와 치즈를 각각 한 개 이상 고른 후 햄버거 빵 사이에 패티와 치즈를 번갈아 쌓아야 한다. 단, 패티의 개수는 치즈의 개수보다 정확히 한 개 더 많이 골라야 한다. 승현이는 가게에 있는 요리 재료를..
실력진단 결과 코드트리 4주차 실력진단 결과 오늘의 학습 Trie & 트라이 6개의 문자열 "app", "apple", "apply", "apart", "ban", "banana"이 주어졌다고 생각해봅시다. 여기서 "ap"로 시작하는 서로 다른 문자열의 수를 구하기 위해서는 각 문자열과 일일이 비교를 해봐야 할 것입니다. public class Main { // 변수 선언 public static int n = 6; // 주어진 문자열 public static String[] words = new String[]{ "app", "apple", "apply", "apart", "ban", "banana" }; // 찾고자 하는 문자열 (prefix) public static String target = "..
14699번: 관악산 등산 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미 www.acmicpc.net Dynamic Programming 높은 위치부터 계산 제목 관악산 등산 조건 시간 제한 : 1 초 메모리 제한 : 512 MB 문제 서울대학교에는 “누가 조국의 미래를 묻거든 고개를 들어 관악을 보게 하라”라는 유명한 문구가 있다. 어느 날 Unused는 Corea에게 조국의 미래를 물었고, Corea는 직접 관악산에 올라가 조국의 미래를 보고 답해 주기로 했다. 관악산의 등산로는 1부터 N까지의 서로 다른 번호가 붙어 있는 N개의 쉼터와 두 쉼..
28333번: 화이트 칼라 전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다. 오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 www.acmicpc.net BFS + BFS 제목 화이트 칼라 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 전미 최고의 사기꾼. 안 해본 도둑질, 안 해본 사기가 없는 닐 카프리는 오늘 저녁 세계 최고의 미술품 중 하나인 “뮤직박스”를 훔칠 예정이다. 오늘 아침, 이 정보를 입수한 AdbyMe, Inc. 는 그를 검거하기 위한 작전을 세우고 있다. AdbyMe, Inc. 는 그가 현재 어느 도시에 있는지, 그리고 뮤직박스가 어느 도시에 있는지 파악했고, ..
18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 배낭 문제 블럭의 개수가 오름차순으로 주어지지 않는다. 제목 함께 블록 쌓기 조건 시간 제한 : 1 초 메모리 제한 : 256 MB 문제 1번부터 N번까지의 학생들은 각각 블록들을 가지고 있다. 학생마다 최대 M개의 블록을 가지고 있을 수 있으며, 한 명의 학생이 가지고 있는 모든 블록들의 높이는 서로 다르다. 이 때 1번부터 N번까지의 학생들이 가진 블록을 차례대로 사용하여 바닥에서부터 쌓아올려 하나의 탑을 만들고자 한다...
30045번: ZOAC 6 2023년 9월, 여섯 번째로 개최된 ZOAC의 오프닝을 또 맡은 성우는 영과일의 마스코트인 영일이를 이용해 대회를 홍보하기로 했다. 성우는 홍보 글이 주어질 때 각 문장에 01 또는 OI가 포함되어 있다 www.acmicpc.net 문자열 순회 제목 ZOAC 6 조건 시간 제한 : 1 초 메모리 제한 : 1024 MB 문제 2023년 9월, 여섯 번째로 개최된 ZOAC의 오프닝을 또 맡은 성우는 영과일의 마스코트인 영일이를 이용해 대회를 홍보하기로 했다. 성우는 홍보 글이 주어질 때 각 문장에 01 또는 OI가 포함되어 있다면 문장 끝에 한 개의 영일이 이모티콘을 넣기로 했다. 이때, 홍보 글에 영일이 이모티콘을 총 몇 번 넣어야 하는지 구하여라. 입력 첫 번째 줄에 홍보 글..
2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 백트래킹 제목 스도쿠 조건 시간 제한 : 2 초 메모리 제한 : 256 MB 문제 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜..
