겜돌이의 개발일지

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

문제 백준 1715 카드 정렬하기 C++ 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 최소로 비교하는 방법은 작은 값부터 합치는 것이다. 방법은 다음과 같다. 1. 오름차순으로 queue를 정리한다. 2. 최소값 두 개를 꺼내고 합친 값을 queue에 다시 푸쉬 3. queue 사이즈가 1이라면 출력 소스 코드 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 ..

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

문제 백준 11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si 따라서 pq2.top의 종료시각이 pq1.top의 시작시각보다 커질때까지..

문제 백준 17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 투포인터를 사용합니다. 앞과 뒤에서 인덱스를 조절하며 팰린드롬인지 검사합니다. 만약 팰린드롬이 아니라면, check를 true로 바꿔주고 유사회문인지 검사하기 위하여 isPalin함수를 재귀호출합니다. 검사 후에, isP가 true고 check가 false면 팰린드롬, isP가 true고 check가 true면 유사회문, isP가 false인 경우에는 회문이 아니므로 각각에 맞는 정답을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..

문제 백준 2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 N자리 숫자에서 K개만큼을 꺼내 줘야 합니다. 예제 입력 3의 경우를 보겠습니다. 10 4 4177252841 10자리 숫자에서 4자리를 제거해 가장 큰 숫자를 만들어야 합니다. 스택이 비지 않았고, 꺼낼 수 있으며, 현재 넣을 수가 stack의 top보다 클 때 stack을 pop 하고, cnt를 증가시켜줍니다. [1번째 자리] 스택에 4를 push 합니다. (stack : 4) [2번째 자리] 1은 4보다 크지 않으므로 스택에 psuh 합니다. (stack : 41) [3번째 자리] 7은 1보다 크므로 스택을 ..