겜돌이의 개발일지

문제 프로그래머스 132265 롤케이크 자르기 C++ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 토핑 최대 개수가 백만개이기 때문에, 시간복잡도에 유의해야 한다. 루프를 여러번 돌면 시간초과가 나므로, 처음 top2 확인에 1번, 토핑 전체 검사 후 answer 증가에 1번 루프를 돈다. 먼저 토핑 전체를 검사해서, 서로 다른 토핑의 개수를 top2에 저장한다. 그 후에 토핑을 하나하나 확인해서, top1에 없는 토핑이라면 top1을 늘려준다. top2에 토핑이 없어지면 top2를 1감소시킨다. top1와 top2가 같다면 answer를 1증가시..

문제 백준 2309 일곱 난쟁이 C++ 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 무난한 브루트 포스 문제이다. 아홉 난쟁이 중에 두 난쟁이는 합에 포함이 안 되고, 100이 되는 경우가 무조건 존재하므로 루프를 돌면서 포함이 안되는 두 난쟁이를 찾고 나머지 난쟁이를 벡터 result에 push해준다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40..

문제 백준 1065 한수 C++ 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 N까지 루프를 돌면서 N이 등차수열인지 아닌지 검사합니다. 한 자리, 두 자리 수는 무조건 등차수열이므로 주어진 범위에서는 세 자리 숫자만 검사하면 됩니다. (1000은 한수 아님) 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include using namespace std; int ..

문제 백준 17142 연구소 3 C++ 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 풀이 빡구현류의 브루트 포스 + BFS + 시뮬레이션 문제입니다. 1. 바이러스를 M개 만큼 선택한다. (조합 이용) 2. 바이러스를 확산하고 최소 시간을 갱신한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 5..

문제 백준 1339 단어 수학 C++ 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 처음에는 백트래킹을 활용하여 각 알파벳에 1~10까지 모두 넣어보는 브루트 포스 방법으로 풀었지만, 그리디로 접근하면 훨씬 효율적으로 풀 수 있습니다. 소스 코드 브루트 포스 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

문제 백준 1405 미친 로봇 C++ 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 DFS를 활용하여 전체 탐색합니다. 4^14이라 시간 초과가 발생할 것 같지만, 중간에 경로가 겹치면 그 이후 경로는 탐색하지 않는 식으로 접근하면 더 빨리 해결이 가능합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ..

문제 백준 15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 백트래킹을 통해 폐업하지 않을 치킨집을 선정합니다. M개만큼 선정했다면, 브루트 포스를 통해 최소 거리를 갱신해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57..

문제 백준 14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 8x8의 작은 배열이기 때문에 가능한 모든 경우의 수에 대해 벽을 만들어 주는 브루트포스 방법을 사용합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ..