케이스윔의 개발 블로그

문제각 나라별 필요한 예산과 총 예산이 주어지고, 가장 최대한의 예산을 써서 각 나라에 배정하는 예산의 상한액을 구하시오.문제 출처: 백준 온라인저지(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은 가..

사실 팁이라고 하기에는 거창하지만 제가 자료구조, 알고리즘 관련 문제들을 풀다 보며 기억해두면 좋을 것 같은 내용을 기록하고 남겨두는 글입니다. 계속 수정을 통해 업데이트해나가도록 하겠습니다! printf("%*d", 출력폭, 변수); 미리 특정 숫자가 아닌 계산하는 결과에 따라 출력하고자 하는 변수의 출력 폭을 지정할 수 있습니다.priority_queue 에서는 pop()은 반환값이 없기 때문에 empty()로 잘 체크해줘야 합니다. 체크를 안 해주고 반복문에서 사용할 경우(VS환경에서는 컴파일 시 에러가 나서 확인가능) 백준 온라인 저지와 같은 사이트에서 히든케이스로 존재할 경우 무한루프에 빠지고 시간초과가 납니다. 또한 비어있을 때 top()은 어떤 값을 return 할지 모르기 때문에 우연히 예..

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

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