BangBang's Devlogs

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[..

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 �� programmers.co.kr [LEVEL 4] 처음에 문제를 이해할 때, 인접한 집이 아니면 된다는 생각에 홀수 또는 짝수 인덱스로 되어있는 집끼리 money 값을 더해서 구했었으나 반례를 찾아냄 money = {1, 1, 1, 8, 1, 1, 7, 1, 1} 이런 경우 두 칸이 띄어져있더라도 8,7을 훔치는게 더 나음으로.. 해결 방안 1. 처음 집을 훔치고 마지막 집을 안 훔칠때와 ..

https://programmers.co.kr/learn/courses/30/lessons/43163# 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr dfs를 이용하여 구현함 해결 방안 1. begin이 target과 같을 때의 depth와 minDepth를 비교하여 최소값을 minDepth에 저장함. 그리고 변환 과정이 words 배열의 크기보다 크면 변환할 수 없는 경우이므로 0을 저장함 2. words 전체를 돌면서 dfs를 통해 가장 짧은 변환 과정을 찾아줌..

https://programmers.co.kr/learn/courses/30/lessons/43105?language=java 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함 이 과정을 통해 점화식을 세우는게 중요함 그리고 메모제이션을 해서 시간을 줄이는게 중요함 =>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로 메모제이션 방법으로는 아래와 같은 방법이 있음 1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법 (BOTTOM-UP) 2. 그 순간 필요하면 계산해서 저장하는 방법(..

https://programmers.co.kr/learn/courses/30/lessons/42898#qna 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 동적계획법 문제를 풀기위해서는 큰 문제를 작은 문제로 나누는 과정이 필요함 이 과정을 통해 점화식을 세우는게 중요함 그리고 메모제이션을 해서 시간을 줄이는게 중요함 =>값을 저장해놓음으로써 함수 호출의 시간을 단축시킬수 있으므로 메모제이션 방법으로는 아래와 같은 방법이 있음 1. 반복문을 이용하여 미리 값들에 대한 계산을 다 해서 저장하는 방법..