작심 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 일단 Core 중에서도 가장자리에 있는 것들은 전선을 연결하지 않기 때문에 고려해줄 이유가 없으므로 코어의 목록에서 제외하고 시작한다. 최대한 많은 Core에 전원을 연결해야 하기 때문에 코어의 개수를 M개라 칭하면, M개 중 M개를 뽑는 조합부터 시작하여 M - 1, M - 2, ... , 0개를 뽑는 경우까지 차근차근 생각해주어야 한다. M개 중 R개를 뽑는 조합을 구하면, 즉 R개의 Core를 사용할 때, 전선 길이의 합이 최소가 되는 경우를 구해야 한다. DFS를 사용하여 상, 하, 좌, 우 방향으로 전선을 만들 수 있는지 판단한다. → 만들 수 있는 경우..

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

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 위 그림처럼 항상 우, 하, 좌, 상 순서로 꺾이는 형태를 가지고 있다. 0,0 부터 오른쪽 방향으로 시작해서 가려는 방향에 이미 다른 숫자가 채워져 있거나 벽을 만나면 그 다음 방향으로 전환하고 다시 나아가게 하면 된다. import java.util.Scanner; public class D3_1954_달팽이_숫자 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for(int t = 1; t = N || arr[X][Y] != ..

16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 1. 괄호로 묶지 않는 경우 이전까지의 값 OP 숫자 = res a[idx] a[idx+1] 2. 괄호로 묶는 경우 이전까지의 값 OP (숫자 OP 숫자) = res a[idx] (a[idx+1] a[idx+2] a[idx+3]) 재귀 호출을 이용해 수식의 처음부터 끝까지 돌면서 1번 경우는 무조건 계산하고 2번 경우는 뒤에 남은 수식이 괄호를 추가할 수 있을 만큼 남아있는 경우에만 계산한다. #include #include #include #in..

9202번: Boggle 문제 상근이는 보드 게임 "Boggle"을 엄청나게 좋아한다. Boggle은 글자가 쓰여 있는 주사위로 이루어진 4×4 크기의 그리드에서 최대한 많은 단어를 찾는 게임이다. 상근이는 한 번도 부인을 Boggle�� www.acmicpc.net 단어 사전을 만들 때 트라이 알고리즘을 이용하여 트리를 만들면 트리 생성 시 O(L*M), 탐색 시 O(L) (L : 제일 긴 문자열의 길이, M : 총 문자열의 수) 로 빠르게 문자열을 탐색할 수 있다. Boggle 보드의 모든 칸마다 가로, 세로, 대각선으로 인접한 칸을 DFS로 글자 수 1부터 8까지 탐색한다. 탐색하면서 사전에 이 단어가 있는지 찾는데 해당 단어가 있다면 set에 있는 단어인지 체크해준 뒤 (중복 찾기 방지 위해) s..

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 블록을 옮기는 방향에 따라 다르게 검사하며 1. 위로 옮길 때 -> 각 열 위에서부터 검사 2. 아래로 옮길 때 -> 각 열 아래에서부터 검사 3. 왼쪽으로 옮길 때 -> 각 행 왼쪽에서부터 검사 4. 오른쪽으로 옮길 때 -> 각 행 오른쪽에서부터 검사 같은 숫자가 연속해서 나오면 (빈칸 무시) 그 두 숫자를 더한 값을 큐에 넣고 같은 숫자가 연속하지 않을 때는 그 숫자만 큐에 넣는다. 한 줄의 검사가 끝나면 큐에 있는 숫자를 보드판에..

13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net ▷다른 방식 풀이 보러가기 상, 하, 좌, 우 방향으로 굴리면서 DFS 한다. 빨간 구슬과 파란 구슬이 일직선 상에 있을 경우 order 함수를 통해서 어느 구슬 먼저 굴려야 할지 판단해준 뒤 그 순서에 따라서 다음 경우에 맞게 처리해준다. 1. 빨간 구슬이 구멍에 들어가건 안 들어가건 상관없이 파란 구슬이 구멍 안으로 들어가는 경우 -> 실패이므로 구슬들의 위치만 원 상태로 복귀 후 다음 방향으로 넘어감(cont..