작심 24/7

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. findTop 0열부터 W - 1열까지 돌면서 0행부터 탐색하며 맨 위에 있는 벽돌을 찾아내는 함수이다. 이 행위를 재귀로 N번 반복하면 N개 중 N개를 중복 포함에서 뽑는 중복 순열이 된다. 맨 위에 있는 벽돌을 찾아내면 거기에 구슬을 떨어뜨리고 다음 동작들을 (연쇄 벽돌 없애기, 벽돌 재 정렬하기) 실행한 뒤 돌아와서 재귀로 구슬을 떨어뜨릴 다음 위치를 찾는다. 2. findChain 구슬을 떨어뜨린 벽돌을 기준으로 연쇄된 모든 벽돌을 찾아 0으로 바꿔주는 함수이다. 상하좌우를 DFS 탐색하며 명중된 벽돌들을 찾아서 큐에 넣어준 뒤 0으로 바꿔주고 다음 ..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 기본적인 Union-Find 문제이다. 좀 더 효율적인 비교를 위해 union 연산에서 트리의 깊이(rank)를 이용하여 rank가 더 높은 집합에 rank가 낮은 집합을 붙이게 하였다. rank가 같을 때는 어쩔 수 없이 둘 중 하나는 증가돼야 하므로 + 1 해주었다. rank가 다를 때 rank가 동일할 때 import java.util.Scanner; public class D4_7465_창용마을_무리의개수 { static int T, N, M, res; static int parentOf[], rank[]; static int find(int a) { if..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 기본적인 로직은 상, 하, 좌, 우를 탐색하여 이전 봉우리보다 낮은 경우 → 한 칸 더 갈 수 있다. 이전 봉우리보다 높거나 같은 경우 → 현재 봉우리의 높이를 1~K 만큼 깎아서 (이전 봉우리 높이 - 1) 로 만들 수 있는지 판단. →만들 수 있으면 한 칸 더 갈 수 있다. 이때, 깎을 수 있는 기회는 한 번뿐이므로 깎았다고 표시를 해줘야 한다. 이렇게 가장 긴 길이를 찾는 문제이므로 DFS로 풀면 되지만 굳이 굳이 BFS로 접근해서 방문 체크 때문에 머리 아팠다. DFS는 깊이 우선 탐색이기 때문에 방문 배열 한 개 가지고 재귀 호출을 통해 체크했다가 지웠다..

1082번: 방 번호 문방구에서 파는 숫자의 개수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 문방구에서 파는 숫자는 0보다 크거나 같고, N-1보다 작거나 같은 정수이다. 예를 들어, N=4이면, 문방구에서 파는 www.acmicpc.net 가장 큰 수를 만들기 위한 우선순위는 아래와 같다. 1. 자릿수가 최대한 길어야 한다. 2. 맨 앞자리부터 최대한 큰 수가 들어가 있어야 한다. 먼저 1번을 만족하려면 무조건 숫자를 많이 모아야 하기 때문에 비용이 가장 적은 숫자를 최대한 많이 산다. 이때, 비용이 가장 적은 숫자가 0이라면 맨 앞자리에 0이 오면 안 되므로 비용이 두 번째로 적은 숫자를 하나 사서 맨 앞자리에 배치한 다음에 나머지는 비용이 가장 적은 숫자로 채운다. 2번을 만족하기 위해..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 일단 Core 중에서도 가장자리에 있는 것들은 전선을 연결하지 않기 때문에 고려해줄 이유가 없으므로 코어의 목록에서 제외하고 시작한다. 최대한 많은 Core에 전원을 연결해야 하기 때문에 코어의 개수를 M개라 칭하면, M개 중 M개를 뽑는 조합부터 시작하여 M - 1, M - 2, ... , 0개를 뽑는 경우까지 차근차근 생각해주어야 한다. M개 중 R개를 뽑는 조합을 구하면, 즉 R개의 Core를 사용할 때, 전선 길이의 합이 최소가 되는 경우를 구해야 한다. DFS를 사용하여 상, 하, 좌, 우 방향으로 전선을 만들 수 있는지 판단한다. → 만들 수 있는 경우..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 최단 거리를 구하는 문제이므로 BFS를 쓰는 게 적합하다. 일단 큐에는 x, y좌표 뿐만 아니라 현재까지의 이동 횟수, 이전에 벽을 부쉈는지의 여부 도 저장해주어야 한다. 벽을 한 번만 부술 수 있기 때문에 이전에 벽을 부순 적이 있으면 그 루트는 앞으로 벽을 뚫고 지나가지 못 한다. 그리고 방문 체크를 해줄 때 벽을 한 번 부순 경우와 벽을 부수지 않은 경우 두 가지로 나누어서 체크해주어야 하기 때문에 3차원 배열 visited를 사용..

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 시간 초과와의 싸움이었다. N번만큼 for문을 돌면서 visited 배열을 초기화해줬는데 이게 시간 초과의 주된 원인이라고 한다. 그래서 초기화는 테스트 케이스마다 한 번씩만 해주고 재귀에서 빠져나올 때마다 visited 배열의 값을 false로 바꿔주는 방식으로 대체하였다. 1. 각 원소는 무조건 어떤 원소를 가리킨다. 마지막엔 무조건 사이클로 끝나게 된다. 2. 한 번 방문한 곳은 visited, 예전에 검사가 끝난 곳은 done으로 표시할 때, done으로 표시..

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 예시 그림을 보면 괄호 문자가 세 가지 유형으로 나뉘는데 이에 따른 규칙을 찾아서 풀어주면 된다. ( 1. 새로운 막대기 추가 cnt++(막대기 개수 증가시킴) ) 2. 막대기 끝 cnt-- (막대기 개수 감소시킴) res++ (자르고 남은 조각 한 개 증가시킴) () 3. 막대기 자르기 res += cnt (자를 수 있는 막대기 개수만큼 증가시킴) import java.util.Scanner; public class D4_5432_쇠막대기_자르기 { public static void main(String[] args) { Scanner sc = new Scann..