우노

문제 링크 https://leetcode.com/problems/maximum-subarray/description/ 풀이 해당 문제는 그리디 알고리즘(Greedy Algorithm)의 한 종류인 카데인 알고리즘(Kadane’s Algorithm)을 사용해서 해결할 수 있습니다. 카데인 알고리즘(Kadane's Algorithm)은 배열에서 연속된 부분 배열의 최대 합을 구하는 효율적인 알고리즘입니다. 이 알고리즘은 O(N)의 시간 복잡도를 가지며, 다음과 같은 단계로 진행됩니다. "현재 합"과 "최대 합"을 -inf(음의 무한대)로 초기화합니다. 배열을 순회하며 다음 두 가지 경우 중 큰 값을 “현재 합”으로 갱신합니다. 이전 인덱스까지의 “현재 합” + 현재 인덱스의 값 현재 인덱스의 값 “현..

문제 링크 https://www.acmicpc.net/problem/17609 풀이 왼쪽 포인터 값과 오른쪽 포인터 값이 동일할 경우, 양쪽 포인터를 그 다음 포인터로 이동 왼쪽 포인터 값과 오른쪽 포인터 값이 동일하지 않을 경우 왼쪽 포인터를 오른쪽으로 이동했을 때, 양쪽 포인터 내부 문자열이 회문이 되는지 확인 오른쪽 포인터를 왼쪽으로 이동했을 때, 양쪽 포인터 내부 문자열이 회문이 되는지 확인 나머지 경우(회문이나 유사회문도 아닌 일반 문자열인 경우) 코드 import sys t = int(sys.stdin.readline()) for i in range(t): result = 0 str = list(sys.stdin.readline().rstrip()) left_idx = 0 right_idx =..

문제 링크 https://www.acmicpc.net/problem/2812 풀이 큰 수가 되려면 높은 자리수의 숫자가 커야합니다. 그래서 스택을 이용합니다. 예를 들어, 4177252841 이고 k = 4이면 775841이 최대값이겠죠? 먼저 4를 stack에 집어넣습니다. stack = [4] 다음 1을 stack에 넣어야 하는데, stack의 최근 값인 4보다 1이 작거나 같죠? 그래서 그냥 stack에 1을 넣습니다. stack = [4, 1] 다음 7을 stack에 넣어야 하는데, stack의 최근 값인 1보다 7이 크죠? 그래서 1을 pop 합니다. stack = [4], k = 3 아직 stack의 최근 값인 4보다 7이 크죠? 그래서 4를 pop 합니다. stack = [], k = 2 이..

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42884 풀이 차량의 이동 경로를 진출 시간을 기준으로 오름차순 정렬한 뒤, 모든 차량의 이동 경로를 순서대로 탐색하며, 현재 설치된 카메라의 위치보다 다음 차량의 진입 지점이 클 경우, 카메라를 새롭게 설치합니다. 세부 알고리즘은 아래 코드와 같습니다. 코드 def solution(routes): # 진출 시간을 기준으로 오름차순 정렬 routes.sort(key = lambda x:x[1]) # 카메라 설치 위치 초기화 camera = -int(1e9) # 카메라 설치 개수 count = 0 # 차량의 이동 경로 탐색 for route in routes: # 현재 설치된 카메라의 위치보..

문제 링크 https://www.acmicpc.net/problem/4307 풀이 "두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다." 해당 문구는 전혀 고려하지 않아도 되는 문제입니다. 예를 들어, 길이 10의 막대기가 있고, 개미 3마리가 순서대로 2, 6, 7의 위치에 존재한다면, 각 개미가 땅으로 떨어지는 최소 시간과 최대 시간은 아래와 같습니다. 개미 1 최소 : 2, 최대 : 8 개미 2 최소 : 4, 최대 : 6 개미 3 최소 : 3, 최대 : 7 모든 개미가 땅으로 떨어지는 최소 시간과 최대 시간을 구하는 문제이므로, 각 개미가 땅으로 떨어지는 최소 시간 중 제일 큰 값은 4, 각 개미가 땅으로 떨어지는 최대 시간 중 제일 큰 값은 8이므로, 주어진 예제의 정답과 같게 됩니다..

문제 링크 https://www.acmicpc.net/problem/2839 풀이 남아있는 N이 5로 딱 나눠떨어질때까지 3씩 덜어냅니다. 세부 알고리즘은 아래 코드와 같습니다. 입력이 9일땐, N이 마지막에 0이 되더라도, if (n % 5 == 0) 의 조건은 만족하므로, 3으로만 나눈 결과값이 출력됩니다. 코드 import sys # 설탕 무게 n = int(sys.stdin.readline()) # 봉지 개수 bag = 0 while n >= 0 : if n % 5 == 0 : # 남은 설탕이 5로 나눠떨어진다면 bag += (n // 5) # 5로 나눈 몫을 봉지 개수에 추가 print(bag) break n -= 3 # 남은 설탕이 5로 나눠떨어지지않는다면, 3씩 덜어내기 bag += 1 # ..

문제 링크 https://www.acmicpc.net/problem/1541 풀이 최솟값을 만들기 위해서는 - 기준으로 괄호를 치면 됩니다. 예를 들어, 55 - 50 + 40 - 30 + 20 을 입력 받았을 때, - 기준으로 괄호를 친다면, 55 - (50 + 40) - (30 + 20) 가 되며, 이는 최솟값이 됩니다. 세부 알고리즘은 아래 코드와 같으며, ['55', '50 + 40', '30 + 20']로 전처리했을 때, 각 원소들을 원소들의 합으로 변환한 뒤, 맨 처음의 원소는 더하고 나머지 원소들은 빼주면 됩니다. 코드 import sys # 입력 문자열 input_ = sys.stdin.readline().rstrip() # 숫자 배열 num_ar..

문제 링크 https://www.acmicpc.net/problem/2457 풀이 회의실 배정 문제의 변형판입니다. 먼저, 입력 날짜가 1월 1일이면 101, 12월 31일이면 1231처럼, 월에 100을 곱해줘서 일이랑 더해줍니다. 꽃이 피는 날짜, 꽃이 지는 날짜순으로 오름차순 정렬합니다. 정원의 마지막 꽃이 지는 날짜 end_date를 3월 1일로 초기화합니다. 모든 꽃들을 탐색합니다. 남아있는 꽃들 중, 꽃이 피는 날짜가 end_date 이전이며, 가장 느리게 지는 꽃을 찾습니다. 확인한 꽃들은 탐색 배열에서 제거합니다. 가장 꽃이 느리게 지는 날짜를 end_date로 수정합니다. 정원의 마지막 꽃이 지는 날짜가 12월 1일 이상이 됐거나, 현재 확인할 꽃의 시작 날짜가 정원의 마지막 꽃이 지는 ..

문제 링크 https://www.acmicpc.net/problem/1339 풀이 해당 문제를 일반화하기 위해선, 각 알파벳의 자릿수를 기억해야합니다. 예를 들어, GCF + ACDEB 가 주어졌을 때, 각 알파벳의 자릿수를 별도로 저장합니다. A는 만의 자릿수를 가지기 때문에 10000 C는 천의 자릿수와 십의 자릿수를 둘 다 가지기 때문에 1010 G는 백의 자릿수를 가지기 때문에 100 D는 백의 자릿수를 가지기 때문에 100 E는 십의 자릿수를 가지기 때문에 10 B는 일의 자릿수를 가지기 때문에 1 F도 일의 자릿수를 가지기 때문에 1 이렇게 알파벳의 자릿수를 별도로 저장한 뒤, 자릿수를 내림차순 정렬하고, 자릿수가 높은 순서대로 숫자를 감소시켜가며 곱셈을 진행합니다. A = 10000 * 9 ..

문제 링크 https://www.acmicpc.net/problem/16953 풀이 B를 A로 바꾸는 방식으로 진행한다. B가 2로 나눠진다면, B를 2로 나누고 나눠지지 않으며, B의 가장 오른쪽이 1이라면, 가장 오른쪽에서 1을 제거한다. B가 2로 나눠지지도 않고, 가장 오른쪽이 1이 아닌 경우도 있다는 것을 주의해야한다. 코드 import sys # A와 B 입력 a, b = map(int, sys.stdin.readline().split()) # 변환 횟수 count = 1 # A보다 B가 클때까지 while (a < b): # B가 2로 나눠진다면, B를 2로 나누고 if (b % 2 == 0): b = b // 2 # 나눠지지 않는다면, else: # B의 가장 오른쪽이 1이라면 if (in..