꾸준함

문제 링크입니다: https://www.acmicpc.net/problem/1497 문제를 잘 못 읽어서 한참을 고생한 브루트 포스(Brute Force)문제였습니다.(문제를 빨리 읽지 말고 꼼꼼히 읽읍시다 ㅠㅠ) 알고리즘은 아래와 같습니다.1. 기타의 조합을 모두 확인해봅니다.(재귀 함수 이용)2. 최대 곡을 갱신할 때마다 maxBit에 최대곡을 result에 기타의 개수를 초기화해줍니다.3. 최대 곡과 동일한 곡을 연주할 수 있을 경우 result와 cnt를 비교해서 더 작은 값을 result에 넣어줍니다.4. 만약 최대 곡이 0이라면 곡을 연주할 수 없기 때문에 -1을 출력해주고 1 이상이라면 result를 출력해줍니다. #include #include #include #include //memse..

문제 링크입니다: https://www.acmicpc.net/problem/11011 간단하게 문제 번역을 해보겠습니다.wen, dream, moon은 기준 점수를 넘지 못해 보충 시험을 치뤄야했습니다. 보충 시험은 객관식 시험이였습니다. 한 문제당 1점이고 사지선다형(A, B, C, D) 시험입니다.wen, dream, moon은 시험을 다 끝내고 OMR 답안지를 제출했는데 그들의 제일 친한 친구 drazil이 그들이 전부 오답을 제출했다는 것을 알아차렸습니다.drazil은 wen, dream, moon이 우울해하는 것을 느끼고 컴퓨터에 입력된 답을 조작하기로 마음을 먹었습니다. drazil은 세 명 중 최소 점수를 최대화시키고자 합니다. 예를 들자면, 보충 시험에 세 문제가 있었고 wen이 ABC, ..

문제 링크입니다: https://www.acmicpc.net/problem/11009 조합을 이용하여 확률을 계산하는 문제였습니다.간단하게 문제를 해석하면 아래와 같습니다.매주 주말에 drazil과 dreamoon은 공원에서 노는데 둘 중 한명이 모두의 음료수를 사야합니다. 그들은 다음과 같은 절차를 통해 누가 음료수를 살지 정하기로 약속했습니다.1. n개의 빨간 구슬과 m개의 하얀 구슬을 가방에 넣습니다.2. dreamoon과 drazil이 번갈아가면서 공을 꺼냅니다. 공을 꺼낼 때마다 가방에서 해당 구슬이 제거됩니다.3. 빨간 구슬을 먼저 꺼내는 사람이 음료수를 사야합니다. dreamoon이 drazil보다 연장자이기 때문에 drazil은 dreamoon이 먼저 뽑게 해줍니다. 어느날 dreamoon..

문제 링크입니다: https://www.acmicpc.net/problem/11008 단순 브루트 포스(Brute Force) 문제였습니다.KMP 알고리즘을 적용할까도 생각을 했지만 굳이 그럴 필요가 없었기 때문에 KMP 알고리즘을 이용하진 않았습니다. 알고리즘은 아래와 같습니다.1. s 문자열의 처음부터 끝까지 반복문을 돌립니다.2. s 문자열을 탐색하는 도중 부분문자열이 p와 같을 때 인덱스를 p만큼 건너뛰고 시간을 업데이트해줍니다.3. 반복문이 끝나면 업데이트 된 시간을 출력합니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 int test_c..

문제 링크입니다: https://www.acmicpc.net/problem/11006 간단한 수학 문제였습니다. 알고리즘은 아래와 같습니다.1. 두 다리가 모두 있는 닭의 최대 개수는 lower_bound(다리의 수 / 2)마리입니다.2. 따라서 1에서 구한 값부터 반복문을 돌리면서 조건이 맞는지 확인합니다.3. 조건이 맞으면 반복문을 탈출하고 다리가 한 개인 닭과 다리가 두 개인 닭의 마리 수를 출력합니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 int test_case; cin >> test_case; for (int t = 0; t < test_case; ..

문제 링크입니다: https://www.acmicpc.net/problem/13900 세그먼트 트리(Segment Tree) 알고리즘을 이용하여 푼 문제였습니다. 알고리즘은 아래와 같습니다.1. 중복 여부를 떠나서 nC2 가지의 경우를 따지는 문제였습니다.2. 따라서 이중 반복문을 돌려서 i는 1 ~ (N-1)까지 반복문을 돌리고 j는 (i+1) ~ N까지 반복문을 돌려서 arr[i] * arr[j]를 모두 더해주면 되는 문제였습니다.3. 2번 방법으로 진행할 경우 시간이 오래걸리기 때문에 세그먼트 트리의 query를 이용하여 시간 복잡도를 O(N^2) -> O(NlogN)으로 단축시켰습니다. #include #include #include #include using namespace std; //세그먼..

문제 링크입니다: https://www.acmicpc.net/problem/11003 세그먼트 트리 알고리즘을 통해 풀어도 되고 슬라이딩 윈도우 기법을 통해 풀어도 되는 문제였습니다.저는 슬라이딩 윈도우 기법을 이용하여 풀었습니다. 알고리즘은 아래와 같습니다.1. 배열을 입력 받습니다.2. pair 형 덱(deque)에 숫자와 인덱스를 저장하는데 범위가 (i - L + 1) ~ i 사이에 있는 숫자들에 대해서 최소값을 찾아야하므로 덱에는 최대 L개의 숫자만 저장되어있습니다.3. 덱에 있는 숫자들은 오름차순으로 정렬되어 있고 arr[i]가 덱에서 제일 큰 숫자가 되도록 덱을 조정합니다.4. 각 인덱스마다 덱의 제일 앞에 있는 숫자를 출력해줍니다.->오름차순 정렬이므로 해당 범위 내에 최소 숫자입니다. #i..

문제 링크입니다: https://www.acmicpc.net/problem/11007 문제에서는 전반적으로 Move-to-Front(MTF) transform이 어떻게 동작하는지 설명해줍니다.간단하게 요약하자면 아래와 같습니다.1. 인덱스를 입력받습니다.2. 해당 인덱스에 있는 알파벳을 결과 문자열에 추가하고 문자열의 제일 앞으로 이동시킵니다.3. 1~2번을 N번 반복합니다. 알고리즘 또한 설명대로 진행해주면 됩니다.string을 사용할 줄 안다면 쉽게 풀 수 있는 문제였습니다! #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); //cin 실행속도 향상 int test_case; ..

문제 링크입니다: https://www.acmicpc.net/problem/7469 정해는 Persistent Segment Tree 혹은 Merge Sort Tree를 통해 푸는 문제였지만 아직 세그먼트 트리에 대한 개념을 완벽히 이해한 상태가 아니였기 때문에 다른 방식으로 풀었습니다.백준님의 세그먼트 트리 강의와 코드를 참고하여 세그먼트 트리 개념을 익힌 후 다시 풀어볼 생각입니다! 알고리즘은 아래와 같습니다.1. pair 배열을 선언하여 first에는 값, second에는 인덱스를 저장합니다.2. 값을 기준으로 오름차순 정렬을 합니다.3. 배열을 처음부터 순회하는데 인덱스 즉, second가 start 이상이고 end 이하인 숫자를 발견하면 cnt를 증가시킵니다.4. cnt가 K가 되면 주어진 범위..

문제 링크입니다: https://www.acmicpc.net/problem/10799 분류는 스택 알고리즘으로 되어있지만 굳이 스택을 이용하지 않아도 되는 문제였습니다. 알고리즘은 아래와 같습니다.1. '(' 다음에 바로 ')'가 나올 경우는 파이프가 아니고 레이저이므로 prev를 통해 이전 괄호의 모양을 저장합니다.2. 레이저를 제외하고는 전부 파이프이므로 '('가 나올 때마다 pipe를 증가시킵니다.3. 레이저가 나올 경우 여태까지 누적 pipe 개수만큼 잘리므로 결과에 pipe 개수만큼 증가시킵니다.4. 레이저가 아닌데 ')'가 나올 경우 파이프의 끝이므로 pipe 개수를 감소시키고 결과를 하나 증가시킵니다.-> 마지막 레이저에 잘린 뒤 남은 부분이므로 결과를 하나 증가시킵니다.5. 1번 ~ 4번을..