BangBang's Devlogs

https://www.acmicpc.net/problem/14501 문제 나는 DFS로 풀었다. 풀고나서 다른 사람들의 풀이를 보니 DP를 이용하여 푼 것을 확인하였다. 다음 복습에는 꼭 DP로 풀어봐야겠다. 해결 방안 1부터 N일 까지 상담이 가능하며 하루에 1개씩만 상담이 가능하다. 이 부분에서 걸리는 시간 비교를 통한 DFS를 이용하면 구할 수 있을 것이라고 생각하였다. 1. DFS 탐색 시작 부분에서 반복문을 이용해서 1~N일까지 DFS 탐색을 하는데 i + T[i] 가 N+1이 넘어가는 순간은 제외하고 진행하였다. (문제에서 퇴직날까지 상담이 가능하다고 하였므르로) 2. 그리고 DFS 탐색 부분에서 기저 사례는 dfs 함수에서 보내준 index 값과 T[index]의 합이 N+1이 넘어가는 순간..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 쉬운듯 안쉬운듯... 처음 풀기엔 어려웠다... 다른사람의 풀이를 많이 참고함 해결 방안 최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록값을 구하는 문제로써 5의 깊이를 가지는 DFS를 이용하여 문제를 풀어야겠다고 생각하였다. 1-1. 일단 기저사례에 도달하였을 때 해당 board의 가장 큰 값을 구하고 그 값과 지금까지 깊이가 5가 됬을 때 board의 가장 ..

https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. www.acmicpc.net 문제 해결 방안 문제 전체 다 꼼꼼히 읽어봐야하는 Simulation(구현) 문제이다. 먼저 크게 1. 전체 입력 받는 부분 2. 게임 돌아가는 부분 두 가지로 나누어서 생각을 해봤다. 1. 전체 입력 받는 부분 1-1 보드의 크기 사과의 위치가 행, 열 그대로 주어져서 N+1 x N+1로 설정하였다. 1-2 사과의 위치 보드 위치 위에 사과가 있는 경우 1을 저장해주었다. (board[row][col]..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 문제 N x M 종이 위에 5가지 도형 중 1가지를 놓아서 해당 도형이 놓인 칸에 있는 수들의 최대 값을 출력하는 문제이다. 해결 방안 1. ㅜ 모양으로 생긴 도형 외 4가지는 dfs를 이용하여 구할 수 있다. - 위와 같이 ㅜ 모양을 제외한 4가지 도형의 각각의 모든 경우(회전, 대칭 포함)은 depth가 4인 DFS 탐색 모양이다. - depth가 4일때 최댓값을 구해준다. 2. ㅜ 모양으로..

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 문제 해결방안 구현 문제이다. 주사위가 굴러갈때마다 지도의 좌표와 주사위를 계속 바꿔주면 된다. 1. 좌표의 경우 동쪽, 서쪽인 경우 y값을 변화시켜주고 이 때 지도의 범위에서 넘어가는지 확인하는 과정이 필요하다. 1-1. 지도에서 넘어갈 경우 해당 명령을 무시하고 넘어가면 된다. 1-2. 지도에서 넘어가지 않는 경우 문제에 주어진..

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제 해결 방안 문제를 이해하고 단순히 구현하는 문제이다. 1. 총 감독은 시험장마다 1명씩 있어서 시험자 응시자 수 배열 a[]에서 b(총감독이 맡을 수 있는 응시자 수)만큼 다 빼주고 cnt++해주고 시작하였다. 2. b만큼 빼준 a[i] 값이 0보다 작거나 같으면 부감독이 필요없으므로 continue 해줬다. 3. 그렇지 않는 경우 a..

https://programmers.co.kr/learn/courses/30/lessons/42883?language=java 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 코드 // 큰 수 만들기 class Solution { public String solution(String number, int k) { StringBuilder answer = new StringBuilder(); if(number.charAt(0) == '0') return "0"; int idx = 0; char max; for(int i=0; i

https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr 탐욕법은 최적의 해에 도달하기 위한 문제 해결 방안이 필요하다. 해결 방안 1. 제일 무거운 사람과 제일 가벼운 사람이 limit에 걸리지 않으면 둘다 나가고 아니면 무거운 사람부터 나가도록 구현함 코드 import java.util.*; // 구명보트 class Solution { public int solution(int[] peo..

https://programmers.co.kr/learn/courses/30/lessons/49189?language=java 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 처음에 간선 간의 가중치를 1로 생각하여 다익스트라그램을 이용하여 최단 경로를 구한다음 가장 먼 거리에 있는 것들을 찾았는데 테스트케이스 9, 10 에서 시간이 넘어갔다. 그래서 BFS를 이용하여 구현하였다. 해결방안 1. BFS를 이용하였으며 각각 vertex들과 start의 거리를 distance에 배열에 저장해줌 2. distance 배열에 저장되어있는 것들 중 가장 먼 vertex들의 거리를 fart..

https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번� programmers.co.kr 해결 방안 문제에 따른 단순 구현으로 해결함 1. answer에 전체 사람 수 만큼 저장 2. lost, reverse에 같이 포함되어있는 학생이 있으면 -1로 바꿈 3. lost 돌면서 reverse에서 빌려 줄수 있는지 확인하고 못빌려주면 answer-- 코드 // 체육복 class Solution { public int solution(int n, int[..