개발log

[문제 설명 및 파악] 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 먼저 문제의 요구가 무엇인지, 이러한 요구를 만족하기 위해 어떻게 접근해야 될지 알아보자. 일단 이 문제는 여러 치킨집 중 각 가정집들과의 거리가 최소가 될 수 있게 하는 M개의 치킨집을 선택하는 것이다. 그렇다면 이를 구하기 위해서는 어떻게 접근할까? 어렵게 생각이 들 수도 있지만, 이 문제는 모든 집과 모든 치킨집들이 고정되어 있기 때문에 단순하게 생각해서 각 집들의 모든 치킨집들 사이의 거리의 최솟값을 누적해서 반..

[문제 설명 및 파악] 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 일단 이 문제의 요구사항과 힌트 및 접근 방식에 대해서 알아보자. 해당 문제는 결국 중력을 이용해서 이리 저리 굴려 파란공이 구멍에 빠지지 않도록 빨간공을 빼내는 것이다. 물론 많은 제한과 여러 조건들이 있지만, 이는 코드 설명 시 언급하겠다. 그렇다면 어떻게 접근해야 될까? 이 문제도 결국 모든 경우를 알아야 한다. 현재 위치에서 갈 수 있는 모든 방향에 대해서 고려하여 이동 후 또 다시 ..

[문제 설명 및 파악] 백준 17837번: 새로운 게임 2 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 이 문제도 어떤 것을 요구하는지, 그 요구사항을 어떻게 풀어나가야 할지 코딩을 구현하기 전에 생각해보자. 먼저 이 문제가 요구하는 것은 정해진 맵에서 말들이 위치와 방향이 주어졌을 때 해당 조건들을 만족하며 맵의 한 칸에 말이 4개 이상 있을 수 있는지 파악하는 것이다. 그렇다면 이 문제는 어떻게 접근해야 할까? 주어진 조건들을 보면 말들의 위치가 같아지면 쌓인다라는 것을 알 수 있다. 이 힌트를 통해..

문제는 총 6문제, 시간은 2시간이 주어졌다. 코딩테스트를 준비하기 시작한 이후로 처음 경험한 실제 테스트였다. 결론적으로 나는 1문제만을 맞췄다. ㅋㅋㅋ.. 2시간에 6문제라면 한문제 당 20분 안에 풀어야 한다는 것이어서, 난이도는 적당히 나올 거라고 예상했다. 물론 풀어본 문제들 중에서는 막 어려운 편에 속하는 편은 아니였다. (그래 봤자 내가 지금까지 푼 문제들은 20개도 안지만..) 물론 현재 실력이 많이 부족하고 경험도 많이 부족해서 경험하자는 의미에서 적어도 2-3문제만은 완벽히 풀자라고 다짐했지만, 결국 그냥 꽁으로 주어진 문제 하나만을 맞추었다.. 아직 실력이 정말 많이 부족한 듯 싶다. 이번 코딩테스트 문제가 공개되면 다시 풀어보며 리뷰를 하겠지만, 아직 공개가 되지 않아서 대략적인 문..

[문제 설명 및 파악] 더보기 Q. 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열..

[문제 설명 및 파악] 더보기 문제 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오. 조건 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다. 코니와 브라운의 위치 p는 조건 0

[문제 설명] 더보기 Q. 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환하시오. dates[i]에는 i번째 ..

1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 반복해서 말하지만 항상 문제를 풀기 전에 생각해야 하는 것은 이 문제에서 결국 어떤 것을 구해야 하는지, 그것을 구하기 위해선 어떤 방식을 택해야 하는지 이다. 일단 이 문제에서 원하는 것은 '스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지'이다. 즉, 만들 수 있으면 push와 pop 연산 반환, 없다면 없다고 반환하..

더보기 Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오. numbers = [1, 1, 1, 1, 1] target_number = 3 항상 코드를 작성하기 전에 이 문제가 요구하는 것이 무엇인지, 어떤 방법으로 풀어나가야 할지에 대해서 ..

1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 항상 문제를 풀기 전엔 이문제가 요구하는 게 무엇이고 이 문제를 어떤 방식으로 풀어야 할지 생각하고 코드를 짜기 시작해야 된다. 이 문제가 요구하는 것은 결국 '주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오.'이다. 결국 0과 1중 최적의 수가 뭘까 생각하다가 한값에 대해서만 결과를 내는 것이 아닌, 두 결과를 모두 구한 후에 두 개를 비교해서 반환하라는 것이다. (최적의 경우를 찾는 것이 아닌 두 가지의 모든 경우를 참고하는.....