Programming
-
[백준] 1261번 알고스팟 (by Python)Programming/Algorithm 2021. 2. 10. 19:52
문제 정말 많은 고민을 하게 하는 문제였다. 많이 볼 수 있는 길 찾기 문제였지만 우선사항이 최단거리가 아니라 최대한 적게 벽을 부수는 방법이었으므로 visited를 활용해 갔던 곳을 못가게 하는 것이 아니라 빙 돌아왔어도 부순 벽의 수가 적다면 수정할 수 있게 하는 것. 이러한 문제의 특징에서 다익스트라를 활용한 포착해낼 수 있었는지의 여부를 묻는 문제였던 것 같다. 나는 아직 미숙해서 거기까지는 눈치채지 못했는데, 앞으로도 더 많은 알고리즘들에 익숙해져 문제에 본질에 어울리는 해결법을 찾는 능력을 길러야겠다. 풀이 import sys import heapq input = sys.stdin.readline INF = int(1e9) m, n = map(int, input().split()) maze =..
-
[백준] 5014번 스타트링크 (by Python)Programming/Algorithm 2021. 2. 7. 18:04
문제 변수가 많았지만, 문제를 제대로 이해하기만 한다면 간단하게 BFS로 해결할 수 있는 문제이다. 개인적으로 각 변수를 필요한 자리에 놓는 과정이 즐거웠던 문제이다. 풀이 from collections import deque INF = int(1e9) f, s, g, u, d = map(int, input().split()) distance = [INF] * (f + 1) distance[s] = 0 q = deque([s]) while True: if not q: print('use the stairs') break temp = q.popleft() if temp == g: print(distance[temp]) break else: if 0 < (temp + u)
-
[백준] 1700번 멀티탭 스케줄링 (by Python)Programming/Algorithm 2021. 2. 7. 17:55
문제 보자마자 운영체제가 생각났던 문제. 실제 운영체제에서는 이렇게 앞으로 어떤 프로세스들이 들어올지 모르기에 최적의 알고리즘을 수행할 수는 없지만, 만약 안다면 이런 식으로 알고리즘을 운영할 수 있다고 배운 것이 어렴풋이 기억이 났다. 앞으로 사용하지 않을 것을 최우선으로 빼고, 가장 나중에 사용할 것은 차선으로 빼는 것. 풀이 from copy import deepcopy n, k = map(int, input().split()) arr = list(map(int, input().split())) now = [] answer = 0 temp = -1 for idx, item in enumerate(arr): if item not in now: if len(now) < n: now.append(item..
-
[백준] 14226번 이모티콘 (by Python)Programming/Algorithm 2021. 2. 7. 00:48
문제 처음에는 떠오르는대로 BFS로 풀었지만 코드를 짜는 와중에도 뭔가 문제를 다 파악하지 못한 풀이라는 생각이 들었고, 아니나 다를까 나보다 시간을 90% 정도 절약한 분들은 Dynamic Programming을 통해 푸신 분들이었다. 간결한 코드에 끌려 원리를 고민해봤지만 수학적인 증명은 스스로 해내지 못했다. 고민해보았고, 앞으로도 더 고민해보겠지만 지금은 더 다양한 테스트 케이스에서 해당 원리가 적용된다는 확신이 없으므로 이런 유형의 문제를 만났을 때는 확실한 풀이를 먼저 시도해볼 것 같다. 좀 느릴지라도, 스스로 납득되는 코드를 짜고 싶다. 첫 번째 풀이 (by BFS) from collections import deque s = int(input()) q = deque() next_q = de..
-
[백준] 1707번 이분 그래프 (by Python)Programming/Algorithm 2021. 2. 6. 00:39
문제 처음에 이분 그래프의 정확한 의미를 모르겠어서 조금 헤맸지만 결국 핵심은 각 노드가 인접한 노드들과 다른 색깔을 가지고 있으면서, 총 2가지 색깔로 다 표현할 수 있는 그래프 라고 생각하면 될 것 같다. 이전의 연결 요소의 개수를 찾는 문제에서 BFS 방법보다 DFS 방법이 더 시간이 낮게 나오는 것을 확인하고 DFS로 들이댔지만 풀고 나니 BFS로 푸는 것이 더 나은 문제였다는 생각이 들어 BFS로도 풀어봤다. 그리고 DFS로 풀려면 sys.setrecursionlimit()을 일단 크게 줘야겠다는 교훈을 얻게 된 문제! 첫 번째 풀이 (by DFS) import sys input = sys.stdin.readline sys.setrecursionlimit(100000) k = int(input(..
-
[백준] 10971번 외판원 문제 2 (by Python)Programming/Algorithm 2021. 1. 31. 16:13
문제 문제의 구성이 기본적인 측면이 있어 사전지식 없이 아이디어를 떠올려 풀 수 있었으나 더 나은 해법을 찾던 중 해당 문제가 TSP(Traveling Salesperson Problem)라는 유명한 문제라는 것을 알았고, 관련된 알고리즘을 체계적으로 공부해보는 계기가 되었다. 덕분에 비트 연산 및 Dynamic Programming 방법에 대해 생각해볼 수 있어서 좋았다. 풀이 def isIn(i, A): return (A & (1
-
[백준] 9019번 DSLR (by Python)Programming/Algorithm 2021. 1. 29. 17:29
문제 다른 것을 하다가 싫증이 나서 가볍게 머리도 풀 겸 고른 BFS 문제인데, 나에게 또다른 시련을 안겨줄 줄은 몰랐다. 논리적으로 풀기 어려운 문제는 아니었으나, 구현하는 내가 자잘한 실수를 발견하지 못한 탓에 성공까지 시간이 좀 걸렸다. PS는 논리력만큼이나 꼼꼼함도 중요하다는 것을 되새기게 된 문제이다. 풀이 from collections import deque import sys def check(x, char): global parents global q global b global a global temp if parents[x][0] == -1: parents[x][0] = temp parents[x][1] = char q.append(x) if b == x: answer = '' whil..
-
[백준] 10972번 다음 순열 (by Python)Programming/Algorithm 2021. 1. 27. 16:54
문제 언뜻 보면 단순한 문제이지만, 내게는 그리 단순하지 않았다. 순열이 나열되는 순서를 논리적으로 표현하는 것에서 어려움을 겪었기 때문이다. 그렇기 때문에 처음에는 permutations 라이브러리를 사용해서 단순하게 해결하려고 시도를 했다. 첫 번째 풀이 from itertools import permutations n = int(input()) target = list(map(int, input().split())) array = list(map(list, permutations(range(1, n + 1)))) answer = array.index(target) if answer == len(array) - 1: print(-1) else: for i in array[answer + 1]: pri..