친절한 도현씨 친절한 도현씨

★ 접근 모든 경우의 수를 살펴봐야하고, 엄청난 크기의 병사, 최대 백만인 라운드 수 이 요소들을 종합적으로 미루어 봤을 때 그리디 알고리즘을 떠올릴 수 있다. 근데 여기서 그리디만을 가지고는 풀 수 없다. 그리디인데도 불구하고 시간초과가 날 것이다. 우선순위 큐 알고리즘도 접목시켜야 풀 수 있다. ★ 풀이 매번 라운드 적군과 맞서 싸운다. 그러다가 아군 병사의 숫자가 적군의 병사의 숫자보다 부족할 경우 무적권을 써야한다. 이 때 무적권이 한 장도 남지 않았다면 게임을 종료시킨다. 무적권이 남아있다면 음수가 돼도 괜찮으니 현재 남은 아군 병사에 현 라운드 적군 병사의 숫자만큼 뺀다. 그리고 현재 적군 숫자를 우선순위 큐에 넣은다음 이제까지 치뤘던 전투 중 가장 적군이 많았던 숫자를 꺼낸 다음 현재 병사에..

＠★＠ 읽게 된 계기와 독후 생각 워낙 유명한 책이기도 했고 읽어보라는 권유를 받아서 읽게 됐다. 읽겠다고 생각한 이후 구두쇠 같은 성격 때문에 1년 후에 책을 읽게 됐다. 1년이라는 시간 + 많은 호평들이 겹쳐져 한껏 기대에 찬 마음으로 책을 읽게 됐다. 허나 미리 작가가 책의 앞 부분에서 비전공자도 읽기 쉽게 썼다고 말은 했지만 책을 다 읽고 난 후 조금의 실망감은 감출 수 없었다. 이미 대부분 알고있는 객체지향의 사실과 오해였다. ＠★＠ 책 요약 책에 대해서 4단어로 요약해보자면 역할, 책임, 협력 이 3가지와 메시지 라고 할 수 있다. 책의 초반부에서는 저 3가지를 위해 초석을 쌓으시고 중반부터 역할, 책임, 협력에 대한 장점과 객체란 이 3가지이며 어째서 객체가 저 3가지인지 기본 개념들을 하나..

★ 접근 - 문제 + 입력 + 예제 입력을 미루어 보았을 때 그래프 이론을 떠올렸고 dfs로 풀었다가 반례를 찾아서 bfs로 풀었다가 반례를 못 찾아서 알고리즘 분류를 보고 dp로 풀었다. 그래프 문제인데도 불구하고 dp로 풀 수 있는 이유는 물은 무조건 번호가 작은 양동이 => 번호가 큰 양동이로 흘러간다는 조건이 있기 때문에 dp로 풀 수 있는 것 같다. ※ bfs로도 풀 수 있지만 bfs로 풀면 + 위상정렬을 같이 사용해야 해서 문제 난이도가 골드 1 ~ 2 수준으로 올라간다고 한다. ★ 풀이 1. 물의 양을 기록해놓을 dp 테이블을 만들고 1번 양동이를 100으로 초기화 해 놓은다. 2. 물은 무조건 작은 양동이에서 큰 양동이로 흘러가니가 가장 바깥 for문을 1번부터 n+1까지 해놓은다. 3. ..

(python 풀이가 하나도 존재하지 않아서 이 글을 써 봅니다.) ★ 접근 기다리기, a만큼 새치기, b만큼 새치기 3가지 경우를 혼합하여 최소한의 횟수로 앞으로 가야하는 상황입니다. 보통 이 상황에서 bfs를 떠올립니다. 필자도 bfs를 떠올렸지만 n의 최대 크기 때문에 불안한 감이 있었습니다. 역시나 시간 초과가 나왔고 dp로 풀기로 했습니다. ★ 풀이 (1로 만들기 문제와 다른 점이 하나 없습니다.) 1. 1,a+1, b+1을 0보다 크거나 같은 상황에서 빼면서 최소값을 구해나가면 된다. ★ 코드 from collections import deque import sys input = sys.stdin.readline n,a,b = map(int,input().split()) dp = [float(..

★ 접근 국회의원의 수가 최대 십만 명 + 각 국회의원 당 주어지는 명예 최대 십만 + 해커가 국회의원 한 명의 명예를 떨어트리는 점수 겨우 1점 = > 그리디 알고리즘 ★ 풀이 (국회의원 명예 점수는 1부터 시작해서 1씩 늘어나게 존재해야 한다. 이유는 "Defile"를 계속 하기 위함이다) 1. .일단 먼저 명예 점수를 오름차순으로 정렬한다. 2. 1부터 시작해서 현재 국회의원과 점수가 다르다면 2-1. 근데 현재 국회의원 점수가 크거나 같다면 차이를 빼서 더하면 된다. + 그리도 다음 num으로 넘어간다. 2-2. 작다면 그냥 무시하고 다음 단계로 넘어간다. 이유는 현재 data[idx]가 3이고 num이 4라했을 명예를 늘릴 방법이 없고 늘릴 이유도 없다. 문제는 명예 점수를 줄이는 것이 목표다...

★ 접근 데이터가 주어지고 문제 조건 상 데이터를 다시 정렬할 수 없다. 투 포인터를 활용해야 한다는 것을 알 수 있다. ★ 풀이 1. n이 1일 수도 있으니 조건문을 써준다. 2. n이 2 이상이라면 temp에 data[l]을 일단 더하는데 while문 안에 들어가서 r이 작다면 더하면서 앞으로 가면 되고 크다면 바로 l을 빼주면 되기 때문에 아무 조건 없이 data[l]을 더하면 된다. (처음에 필자는 data[l]이 m보다 작으면 더하고 크면 작는 경우가 나올 때까지 l과 r을 증가시키면서 찾았다.) - 코드 import sys input = sys.stdin.readline n,m = map(int,input().split()) data = list(map(int,input().split())) ..

★ 접근 문제를 보면 4방향으로 이동하면서 탐색하는 백트래킹을 떠올리기 쉽다. 하지만 n의 최대 크기가 10이고 방문했던 곳을 무한히 방문할 수 있기 때문에 백트래킹을 한다면 시간초과가 난다. 그렇다면 어떻게 해야할까? 우유가 있는 좌표를 따로 담아 놓는 백트래킹을 해야한다. ★ 풀이 1. 진우의 초기 좌표와 우유들이 있는 좌표를 구한다. 2. for i in range(len(mint)): 우유들을 처음부터 하나씩 꺼내보면서 if not visited[i]: 방문하지 않았으면서 현재 체력으로 꺼낸 우유 좌표까지 도달할 수 있다면 그 지역까지 가면서 dfs를 해주면 된다. ★ 코드 import sys input = sys.stdin.readline n,m,h = map(int,input().split()..

★ 접근 처음에는 단순하게 문제를 보고 bfs를 떠올렸다. 문제가 bfs를 떠올리게 유도했기 때문에 대부분의 사람들도 처음에 bfs를 떠올릴 수 밖에 없다고 생각한다. 그러나 구현을 하다보면 bfs로(풀 수도 있겠지만 필자는 실력이 부족해서 구현할 수가 없다) 풀기에는 쉽지 않다는 것을 떠올렸고 생각하면 할 수록 dp로 나를 이끌었다. ★ 풀이 1. 일단 토끼가 있던 위치를 찾아주고 해당 좌표에 dp를 0으로 처리함으로써 방문 처리를 해준다. 2. 토끼가 있던 다음 열부터 반복을 시작한다. 다음 열부터 하는 이유는 첫째, 토끼는 앞으로만 이동하기 때문이다. 두번쨰는 앞으로만 이동하기 때문에 뒤에 상황은 볼 필요가 없다. 세번째, 방향을 반대로 ↙,↖,← 이 3가지 방향으로 생각할 것이기 때문이다. 3. ..