https://www.acmicpc.net/problem/1972 문제 풀이주어진 문자열의 간격을 이중 for문 혹은 while과 for문으로 구성해서 풀 수 있습니다.그리고 만들어진 쌍은 집합에 저장하여 효율적인 공간을 구성해주었습니다. 코드# 1972번 놀라운 문자열ALERTS = ['is surprising.', 'is NOT surprising.']while 1: word = input() if word == "*": break ALERTS_idx = 0 # 문자열 확인 코드 작성. # 이중 for문을 활용하여서 for j in range(i, num) # 그러고 나서 set에 저장. 그러나 이미 존재한다면 break D = 1 while D..

https://www.acmicpc.net/problem/1417 1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 문제 풀이 다솜보다 높은 득표 수를 가진 후보자들이 없어질 때 까지 표를 뺏는 코드를 작성해주었다. 후보자들 중 가장 높은 득표 수를 가진 후보자의 표를 우선으로 매수했습니다. 코드 # 1417번 국회의원 선거 import sys from heapq import heappop, heappush, heapify n = int(input()) dasom_vote = int(input()) ..

분할 정복(Divide and Conquer)을 사용한 거듭제곱 계산법은 수학적 문제 해결과 알고리즘 설계에서 매우 강력한 접근 방식입니다. 이 방법은 복잡해 보이는 문제를 더 작고 관리하기 쉬운 부분 문제로 나누고, 이를 재귀적으로 해결한 다음, 결과를 조합하여 최종 해답을 도출합니다. 특히, 거듭제곱 계산과 같은 수학적 연산에서 분할 정복 방법은 일반적인 반복 또는 직접 계산 방식보다 훨씬 더 효율적일 수 있습니다. 그 이유를 몇 가지 측면에서 설명해보겠습니다. 시간 복잡도의 개선 가장 직관적인 거듭제곱 계산 방법은 (a)를 (n)번 곱하는 것입니다. 이 방식의 시간 복잡도는 (O(n))입니다. 반면, 분할 정복을 사용한 거듭제곱 계산법은 (O(\log n))의 시간 복잡도를 가집니다. 이는 (n)이..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 풀이 우선순위 큐를 활용하여 문제를 구해주면 됩니다. 문제의 예시를 통해 직접 구해보면 알다시피 다음과 같은 로직이 성립하게 됩니다. 1. 큐 안에서 가장 작은 수 2개를 꺼내서 더해준다. 2. 더한 값을 총합(변수:ans)에 더해준다. 3. 더한 값을 다시 큐에 넣어준다. 4. 1-3과정을 큐 안에 원소가 2개 이상일 때까지 반복해준다. 코드 # 1715번 카드 정렬하기 fr..

https://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 문제 풀이 간단한 스택 구현 문제입니다. 조건문에 신경써서 문제를 풀어주세요. 코드 # 28278번 스택 2 import sys st = [] t = int(input()) for _ in range(t): order = sys.stdin.readline().rstrip().split() if len(order) == 2: st.append(order[1]) else: if order[0] == "2": if st: pri..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이 문제를 읽어보면 위상정렬 알고리즘임을 알 수 있다. 위상정렬 알고리즘: https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.c..

https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 기본적으로 가르쳐야할 알파벳은 남극의 기본문법인 "a", "c", "i", "t", "n" 총 5개이다. (위의 5개의 알파벳을 가르치지 않으면 어떠한 단어도 읽을 수 없다.) combinations로 조합을 통해 추가로 가르칠 알파벳을 골라주었다. 이를 통해서 완전탐색으로 단어를 읽을 수 있는지 없는지 확인해주었다. 시간초과 문제로 인해 PyPy3로 제출해주었습니다. 코드(PyPy3..