케이스윔의 개발 블로그

문제총 M명의 사람이 최소한의 시간으로 N개의 입국심사대를 통과해야할 때 최소한의 시간을 구하시오. 문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/3079), 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/43238) 풀이이분탐색으로 푸는 문제입니다. 처음에는 무슨 방법으로 풀어야하지? 생각이 들었는데 최소한의 시간을 구하기 위해 최대한의 범위를 잡은 다음, 그 범위 안에 M명의 사람이 심사가 가능하다면 시간을 줄여가고 가능하지 않다면 시간을 늘려가며 구할 수 있겠다는 생각이들었습니다. 이분탐색의 개념은 다른 문제와 비슷하게 low, mid, high를 통해 그대로 구현하면 되지만 여기선 값이 너무 큰 탓에..

문제각 나라별 필요한 예산과 총 예산이 주어지고, 가장 최대한의 예산을 써서 각 나라에 배정하는 예산의 상한액을 구하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2512), 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/43237) 풀이이분탐색을 통해서 푸는 문제입니다. 최대한 많은 예산을 나눠야하고, 해당 상한액보다 작은 경우엔 모두 배정해줄 수 있고 상한액보다 높다면 상한액까지 배정해줄 수 있습니다. 사실 이 문제를 통해서 이분탐색을 활용해서 푸는 문제를 처음 다뤄볼 수 있었고 처음에 이분탐색 카테고리라는 걸 알았지만 어떻게 이분탐색을 적용해야하는지 감이 오지 않았습니다.(이분탐색에 대한 개념이 없..

문제제일 왼쪽 위칸에서 제일 오른쪽 아래칸까지 갈 수 있는 경로의 수를 구해야한다. 각 칸에는 점프할 수 있는 거리가 적혀져있고 오른쪽 또는 아래쪽으로만 점프할 수 있다.문제출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1890) 풀이처음에는 BFS로 접근했었다. 첫 칸을 큐에 넣어준다음 while문을 통해서 큐에 값을 빼내고 해당하는 위치에서 갈 수 있는 칸들을 큐에 넣도록 했다. 처음엔 모두 큐에 넣어버리고 (0, 0)을 시작으로 했을 때 (N-1, N-1)이 큐에서 나오면 카운트를 해주도록 했다. 그렇게 했더니 큐에 너무나 많은 경로들이 들어가서 메모리 초과가 났다. 메모리 초과를 해결하기 위해서 visited배열을 만들었고, 만약 이미 해당하는 칸에 이미 갔었다..

문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 보관하는 격자모양의 상자들의..

문제음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1038) 문제 풀이오르막 수와 비슷한 문제다. 그 문제는 dp를 통해서 N자리 수까지의 오르막 수를 구하는 거였는데 이 문제는 N번째 감소하는 수를 구해야한다. 처음에는 dp로 몇번째 자리수에 N번째 감소하는 수가 있는지를 찾은 다음 브루트포스를 통해서 해당하는 수를 찾으려..

문제이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다. -3 -2 -1 0 1 2 3 -------------------- -3 |37 36 35 34 33 32 31 -2 |38 17 16 15 14 13 30 -1 |39 18 5 4 3 12 29 0 |40 19 6 1 2 11 28 1 |41 20 7 8 9 10 27 2 |42 21 22 23 24 25 26 3 |43 44 45 46 47 48 49이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가..

문제아기 상어와 물고기들이 존재하는 공간이 주어지고, 아기 상어는 물고기를 먹으며 크기를 증가시키는데 조건에 맞춰서 먹을 수 있는 물고기가 있고 커지는 조건이 있다. 아기 상어가 몇 초 동안 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는지 구하는 프로그램을 작성하는 문제이다.출처: 백준 온라인 저지 https://www.acmicpc.net/problem/16236 풀이아무리 풀어봤더라도 잘 이해하고 넘어갔는지가 중요한 거니까 오랜만에 풀이를 남긴다. 이 문제 처음에 봤을 때는 당황스러웠다. 꽤 복잡해 보였고, 이렇게 풀어도 되나? 하는 몇 가지 방법만 떠올랐는데 그 방법을 정리해서 푸니 풀렸다. 우선 아기 상어는 처음 크기가 2이고, 자신보다 작은 크기의 물고기만 먹을 수 있다. 그리고..

문제 정의로봇 청소기의 주어진 작동방법을 통해서 청소하는 영역의 개수를 구하는 프로그램을 작성하는 것이다.로봇 청소기는 다음과 같이 작동한다.현재 위치를 청소한다.현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며,..