겜돌이의 개발일지

문제 백준 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 ..

빅($O$) 표기법 정의 : 점근적 상한 어떤 함수 $g(n)$이 $O(f(n))$에 속한다는 말은 $n$이 커짐에 따라 $cf(n)$보다는 작은 값을 가지게 된다는 의미 따라서 $g(n)$은 $cf(n)$에 비해 좋다(빠르다)라고 할 수 있다. 즉, 어떤 알고리즘의 시간복잡도가 $O(f(n))$이라는 것은 입력 $n$에 대해 알고리즘의 수행시간이 늦어도 $cf(n)$은 된다는 말이다. (점근적 상한) 알고리즘의 수행시간이 $cf(n)$보다 느릴 수 없다는 말과 같다. 오메가($\Omega$) 표기법 정의 : 점근적 하한 어떤 함수 $g(n)$이 $\Omega (f(n))$에 속한 다는 말은 $n$이 커짐에 따라 $cf(n)$보다는 큰 값을 가지게 된다는 의미 따라서 $g(n)$은 $cf(n)$에 비해 ..

문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 map을 이용해서 풀었다. 개수가 50만개라서 시간초과를 걱정하고 풀었는데, 아슬아슬했던 것 같다. 이분 탐색을 쓰면 더 효율적으로 풀 수 있는듯? map 자체도 이분 탐색이긴 하다만 upper_bound와 lower_bound를 쓰면 더 빠르게 풀 수 있다고 함. 소스 코드 map으로 해결 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

문제 백준 1092 배 C++ 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 풀이 입력을 받은 뒤, 크레인과 상자를 정렬해주고 크레인과 상자 모두 큰 것 부터 처리한다. 소스 코드 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 #include #include using namespace std; int main() ..

문제 백준 11058 크리보드 C++ 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 풀이 DP 문제인데 점화식을 떠올리기가 어려웠다. 처음에 방문체크를 해주는 BFS로 풀려고 했지만... 경우가 많아도 너무 많아서 포기 dp[i]의 최댓값은 다음 중 하나이다. 1. dp[i-1] + 1 2. Ctrl + A, Ctrl + C의 2단계를 거쳐 복사, Ctrl + V로 한 번 붙..

문제 백준 12094 A와 B C++ 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 처음에 S에서 A, B를 붙여주는 BFS로 접근했다가, 길이가 1000 까지기 때문에 메모리 초과가 났습니다. 역으로 T 문자열의 뒤에서부터 접근하여, S와 똑같이 만들어 줄 수 있는지 검사합니다. 소스 코드 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 #include #include #inclu..

문제 백준 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..

맨날 헷갈려서 정리 출처 [C++] 순열(Permutation) 조합(Combination) 알고리즘 백준에서 완전 탐색 문제를 풀다가 항상 조합과 순열을 만들 때 헷갈려서 아예 시간을 내어 정리하였다. 이 네 가지 알고리즘의 뼈대를 이해하면, 여러 방면에 쓰여서 좋은 거 같다. 이후 나오는 hongchan.tistory.com

문제 백준준 1600 말이 되고픈 원숭이 C++ 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 풀이 방문을 [y][x][말 이동 사용 횟수]로 체크합니다. bfs를 돌면서, 각각의 지점에서 말 / 원숭이로 이동할 수 있는 지점을 queue에 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 41 42 43 44 45 4..