문제 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 오답 풀이 (시간초과) 아래 풀이는 시간초과가 발생한 풀이이다. 단순하게 i 번째 원소가 i+1 번째부터 전체 원소까지 탐색할 때 큰 원소를 만나면 인덱스 사이의 거리를 구해 결과에 추가하는 방법으로 코드를 작성하였는데 이렇게 하면 너무 많이 for문을 돌아서 시간초과가 발생한다. import sys input = sys.stdin.readline from collections imp..
Problem Solving
문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 printer 순서를 저장할 큐를 생성 후에 여기에 프린터 중요도를 순서대로 입력한다 인덱스 번호를 저장할 큐를 생성하고 0부터 n-1까지 입력한다. 주의할 점은 프린터 중요도는 1이상 9 이하 숫자이며 프린터 인덱스 번호는 0부터 n-1까지이며 프린터 출력 순서는 1부터 n까지 이다. 현재 프린터 큐에서 몇 번째에 문서가 놓여있는지를 나타내는 M이 0부터 N 사이이다. (M을 0부터 N ..
문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 문제란? 1차 유대-로마 전쟁 당시 요세푸스(Flavius Josephus)는 동료 40명과 함께 로마군에게 포위됐다. 이들은 투항하는 대신, 제비를 뽑아 둥글게 둘러 앉은 후 두 명씩 건너 뛰고 세 번째마다 자살하기로 하였다. 이렇게 하여 39명이 죽은 뒤 요세푸스는 아직 살아남은 동료와 투항했고, 훗날 역사가가 되어 이 일을 기록에 남겼다고 한다. [네이버 지식백과] 요세푸스 문제 (365일 수학) 이를 애니메이션으로 나타내면 다음과 같다. 이미지 출처: The Jose..
Palindrome 알고리즘이란? 팰린드롬(회문) 은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열(sequence of characters) 등이다 - https://ko.wikipedia.org/wiki/%ED%9A%8C%EB%AC%B8 구현 def palindrome(a): if a == a[::-1]: return True else: return False print(palindrome([w for w in input()])) 이를 짧게 풀어서 다음과 같이 나타 낼 수 있다. def is_palindrome(word): return word[::-1]==word # True print( is_palindrome("kayak") ) print( is_palindrome("mad..
문제 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 시도한 풀이 (시간 초과) 리스트를 사용하면 시간 초과가 생길 것 같아 리스트보다 시간복잡도가 유리한 딕셔너리를 이용하였다. 생각과 다르게 시간초과가 발생하였는데 혼자서 고민하여 답을 찾을 수 없어 질문탭에서 확인하였다. 힌트를 찾을 수 있었다. "dict를 쓰지 않고 단순히 pair로 list에 저장한 것과 차이가 없는 코드입니다. 입력을 받으면 그걸 키로 직접..
문제 https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 제출한 풀이 A B C D E F 는 0, 1, 2, 3, 4, 5 인덱스를 부여하고 0이 마주보는 면을 5, 1이 마주보는 면을 3, 2가 마주보는 면을 4 ... 이런식으로 딕셔너리에 해당면의 짝을 지정함 맨 아래 면을 1부터시작하여 맨 아래 면과 마주보는 면을 옆면에 올 수있는 면 리스트에서 제외하면 4개의 면이 남는데 이 중 가장 큰 면을 max_dice_list에 저장함. 맨 아래 주사위..
문제 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 제출한 풀이 import sys input = sys.stdin.readline n, m = map(int, input().split()) num_list = list(map(int, input().split())) sum_list = [0] * (n+1) sum_list[1] = num_list[0] for i in range(2, n+1): sum_list[i] =..
누적합 (Prefix sum) 누적합은 나열된 수의 누적된 합을 나타낸다. Sn은 An[0,0] 합, An[0,1]합, An[0,2]합 An[0,-1]합 을 나타낸다. 누적합의 점화식은 Sn = Sn-1 + An 이다. 위 그림은 인덱스가 0부터 4까지의 수열과 해당 수열의 누적합을 나타낸 이미지 이다. 누적합을 이용해서 인덱스가 2부터 4까지의 구간을 구하려면 [0부터 4까지의 누적합](녹색) - [0부터 1까지의 누적합](빨강색) 을 계산하면 된다. 즉, 구하고 싶은 구간은 보라색이며 누적합 0부터 4까지의 구간에서 빨강색 구간을 빼면 구할 수 있다. 누적합15-누적합3 = 12 (2부터 4까지의 구간) 인덱스가 2부터 4까지의 구간을 구하려면 2부터 4까지 인덱스를 돌면서 카운트 할 수 있겠지만 이..
문제 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 본인이 시도한 풀이는 다음과 같습니다. 먼저 순차적으로 위치별로 기둥의 높이를 리스트에 저장함 (info = [0] * 1001) 리스트에 저장하면서 가장 큰 기둥의 값과 인덱스를 다른 변수에 저장함 처음 기둥부터 가장 큰 기둥까지 좌에서 우로 기둥의 높이가 담긴 리스트들을 탐색한다 리스트를 탐색하면서 높이를 stack에 저장하고 stack의 마지막에 담긴 값을 area..
문제 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 제출한 풀이 n = int(input()) num_list = list(map(int,input().split())) result = 1 increase_temp = 1 decrease_temp = 1 for i in range(0, n-1): if num_list[i] result: result = increase_temp else: result else: increase_temp = 1 fo..
