알루 코딩

일단, 나도 처음에 틀렸던 문제다. 그리디 문제로 접근을 했었고, 문제를 풀었는데, '예제 입력 5' 와 같은 반례에 부딪혔다. 나의 로직은 이러했다. 문제에서 1번 사람부터 N번 사람까지 순서대로 잃는 체력리스트와 얻는 기쁨 리스트를 입력받는다. 세준이가 얻을 수 있는 최대 기쁨을 출력하는 것이므로, [hp(체력), joy(기쁨)]을 쌍으로 갖는 새로운 리스트를 만든 후에, joy(기쁨)을 기준으로 내림차순 정렬을 한다. 그러면, 큰 joy(기쁨)를 가지는 쌍이 앞에 오겠고 해당하는 hp(체력)을 초기 HP(100)에서 빼가면서 음수나 0이 아니면, 해당 joy(기쁨)을 그대로 더해주면서 for문을 순회하도록 로직을 짰다. 처음에 짠 로직은 아래와 같다. import sys input = sys.std..

작년에 풀었던 문제인데, 제대로 이해를 하지 않고 넘어갔었던 느낌이 들어 다시 풀어본 문제이다. 거의 기억이 안나서 새로 푼 문제나 다름이 없었는데, 총 3번의 시련을 겪었다. 가장 먼저, 잘못된 로직으로 문제를 풀어나가기 시작했다. 예를 들어, 입력값이 3 1 98 98 99 99 100 이 주어졌다고 하면, 답은 어떻게 나올까? 답은 3이 나와야 한다고 생각한다면, 나와 똑같은 실수를 한 셈이다. 답은 1이 나와야 한다. 1~98 , 98~99, 99~100 이렇게 겹치지 않고, 1강의실만을 이용해서 강의를 배정할 수 있기 때문이다. 첫 번째 시련을 겪고, 빠르게 로직에 대해서 생각해봤다. 대충 로직은 이러했다. 입력 받은 "강의가 시작되는 시간"과 "강의가 끝나는 시간"을 강의 리스트를 (강의 시작..

그리디(Greedy) 알고리즘 : 욕심쟁이 알고리즘이라고도 하는 탐욕 알고리즘은 단순하지만 강력한 문제 해결법이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘으로, 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 와 같은 기준을 문제에서 알게 모르게 제공해준다. 정렬 알고리즘을 사용했을 때, 효과적으로 풀 수 있어, 보통 정렬 알고리즘과 짝을 이루어 출제되곤 한다. 대표적인 그리디 알고리즘 예제 - 1) 동전 거스름돈 문제 import sys input = sys.s..

정답률이 낮은 이유는 아마 제출 수가 적은 것도 그렇지만, 예외처리 때문일 것이다. 나도 한 2번 틀리고 반례를 발견했으니 말이다. 우선, 시간제한도 2초로 넉넉한 편이어서 for문이나 while문 사용에 거부감이 없었다. 이번 코드리뷰는 내가 제출했었던 코드들을 순차적으로 살펴보자. 맨 처음 제출해서 틀렸던 코드는 아래와 같다. import sys input = sys.stdin.readline n = int(input()) vote_list = [] count = 0 for i in range(n): vote_list.append(int(input())) dasom = vote_list[0] not_dasom = sorted(vote_list[1:], reverse=True) print(not_das..

이 문제도 처음에 시간제한에 걸려서 시간초과가 났었던 문제이다. 로직은 간단한데, 시간초과가 났다면, 분명 어떤 라이브러리를 사용하는 것이거나 더 효율적인 자료구조가 있는 것이다. 방법을 고수하지말고 바꿔야 하는 것을 명심하자. 문제마다 어떤 자료구조로 풀어야 효과적인지 판단하는 것도 중요한 것 같다. 맨 처음 풀었던 코드는 아래와 같다. import sys input = sys.stdin.readline N = int(input()) number_list = [int(num) for num in input().split()] sorted_number_list = sorted(number_list) for i in number_list: order = 0 seen = -1 for j in sorted_n..

정답 비율이 높지 않아서, 뭔가 시간초과와 관련된 문제이겠거니 싶었다. 역시나 처음 풀었던 코드는 시간초과에 걸렸다. 아래는 처음 시간초과에 걸렸던 코드이다. import sys import collections input = sys.stdin.readline a, b = map(int, input().split()) answer = [] no_heard = [input().strip() for i in range(a)] no_seen = [input().strip() for i in range(b)] if a < b: for word in no_heard: if(word in no_seen): answer.append(word) else: for word in no_seen: if(word in no_..

맨 처음에 시간초과가 났던 코드였다. 심지어 PyPy3로도 시간초과가 났었다. 로직은 단순한데, 시간초과가 났다면 다른 라이브러리의 힘을 빌려야 하는 순간이다. 기존 리스트로 카드 세트를 생성하고 처음엔 remove나 del 함수를 사용했지만, 단순히 pop 함수를 사용해도 되는데, 파이썬의 list는 중간에 있는 요소를 pop할 때 시간복잡도가 O(n)이지만, collections.deque는 시간복잡도가 O(1) 라고 한다. 먼저 맨 처음에 작성했던 코드는 아래와 같다. import sys input = sys.stdin.readline n = int(input()) card_list = [] for i in range(n, 0, -1): card_list.append(i) while(len(card..

맨 처음에, 솔직히 문제가 잘 이해가 가지 않았다. 일단 예제 입력을 그대로 문제에 적용해보면, 입력으로 주어진 배열 A의 원소 2 3 1 은 아래와 같이 표현할 수 있다. B[P[0]] = A[0]->B[1] = 2 B[P[1]] = A[1]->B[2] = 3 B[P[2]] = A[2]->B[0] = 1 다시한번, 문제를 잘 읽어보면, 여기서 B배열은 A배열의 비내림차순 배열이라는 것을 알 수 있었다. 우리는 A배열로부터 B배열을 만들었는데, 그럼 자연스럽게 P배열은 A배열의 원소 크기 순이라는 것을 알 수 있다. 여기서 만약, 동일한 크기의 원소라면, 앞서 있는 것을 먼저 출력하면 된다. 예를 들어 A 배열이 1 3 2 2 라고 하면 P배열은 0 3 1 2 순으로 출력 될 것이다. 작성한 코드는 아래..

기말고사가 끝나고 다시 백준문제를 풀어봤다. 이 문제의 로직은 간단했다. 그냥 사용자에게 섞는 순서를 가리키는 알파벳을 입력받고, 해당 알파벳마다 섞는 방법이 다르기 때문에 방법에 따라 그냥 위치만 바꿔주면 됐다. 흔히들 swap할 때는, temp라는 변수를 정해서 원소를 뒤바꾸는데, 파이썬이어서 좋은 점은 temp라는 변수를 따로 안 정하고, 그냥 배열 원소를 서로 바꿀 수 있다는 점이었다. 처음엔, 틀렸었다. 맨 처음 틀린 코드는 아래와 같다. import sys input = sys.stdin.readline order_list = input() ball_position = [1, 0, 0, 1] for alpha in order_list: if(alpha == 'A'): ball_position[..

맨 처음에 문제를 이해하는데 시간이 좀 걸렸다. 이해한 바로는 이렇다. 「첫 줄에 n 이 입력되면, 둘째 줄 부터는 1부터 n 까지의 수를 차례로 입력한다. 그렇게 입력된 n 개의 수가 수열을 형성하도록 push 연산은 +, pop 연산은 - 로 표현하도록 출력하면 된다.」 이해가 안되면, 힌트를 보면 된다. 첫 번째 예제입력은 [4,3,6,8,7,5,2,1] 순으로 입력되었다. 이렇게 수열을 이루려면(출력이 예제입력처럼 되려면), 빈 stack = []에 차례로 push(1) → push(2) → push(3) → push(4) → pop() → pop() → push(5) → push(6) → pop() → push(7) → push(8) → pop() → pop() → pop() → pop() → ..