Simple Explain

#1865 웜홀 (https://www.acmicpc.net/problem/1865)  처음 사용하는 알고리즘이었던지라 많이 애먹었다.다익스트라는 좀 써봤지만 벨만 포드는 처음인지라.. 처음에는 너무 어려워보여서 이런 저런 조건들을 마구 넣었다.하지만 생각보다 풀이가 심플해서 놀랐다.플레티넘을 풀다보면 꼭 뇌가 이상하게 꼬인다. 하지만 골드까지는 그런 꼬임이 필요하지 않다는 것을 꼭 기억하자. 정답코드import sysinput = sys.stdin.readlineINF = int(1e9)tc = int(input())def bf(): # 벨만 포드 : 매 단계마다 모든 간선을 전부 확인하면서 모든 노드간의 최단 거리를 구해 # 모든 라운드 반복 for i in range(n): ..

#13305 주유소 https://www.acmicpc.net/problem/13305  어제 기하학 플래티넘 문제를 풀고 멘탈이 나가있던 상황에서, 오늘은 이 문제를 풀게됐다.  그냥 쉬웠다. 그리디 알고리즘인 만큼 논리적으로 최적해를 찾아내면 된다.  n = int(input())distance = [int(x) for x in input().split()]oil_cost = [int(x) for x in input().split()]answer = 0i = 0while i

#1708 볼록 껍질 https://www.acmicpc.net/problem/1708  진짜 말도안되는 문제이다.엄청 복잡한 논리적 구조로 접근했는데, 그냥 개념을 알아야 풀 수 있는 문제였다. 필요한 개념은 다음 두 가지이다. (기하학 문제이다 보니..) 1. Counter Clockwise세 점 a, b, c가 있을 때, a를 기준으로 b, c가 어느 방향으로 위치하는지를 검사하는 공식이다.방법은 간단하다. a를 기준으로 두 개의 벡터를 만든다. ab, ac이 두 벡터를 외적(Cross Products)한다. 외적은 특이한 성질이 있는데, V X W를 진행했을 때, 결과값이 양수라면 -> V벡터가 W벡터의 오른쪽(시계방향)에 존재한다.반면, 결과값이 음수라면 V벡터가 W벡터의 왼쪽(반시계방향)에 존..

#11375 열혈강호 https://www.acmicpc.net/problem/11375 처음엔 열심히 풀었다. 틀린 코드n, m = map(int, input().split())people = {x: [] for x in range(1, n + 1)}for i in range(1, n + 1): tmp = list(map(int, input().split())) if tmp[0]: people[i] = tmp[1:]works = [0] * (m + 1) # 인덱스 1부터 사용# print(people)def allocate(idx): # input() target = people[idx] if len(target): # 1. 가장 첫 번째 일에 연결..

#9251 LCS https://www.acmicpc.net/problem/9251 아.. 그제 풀었던거 오늘 포스팅 하려니까 기억이 가물가물... 단순히 dfs로 풀었다.모든 경우의 수를 탐색하는 것이다. (브루트포스?) 그리고 역시나 메모리 초과를 맞이했다. 틀린 코드s1 = input().strip()s2 = input().strip()n1 = len(s1)n2 = len(s2)visited1 = [False] * n1visited2 = [False] * n2N = max(n1, n2)result1 = {x: [] for x in range(1, n1 + 1)}result2 = {x: [] for x in range(1, n1 + 1)}def dfs(depth, s, origin, n): if..

#1167 트리의 지름 https://www.acmicpc.net/problem/1167 문제를 풀이하는 과정이 너무 복잡했다. (결국 블로그 참고함) 다음 세 가지를 배울 수 있었다. 1. DFS 구현의 두 가지 방식(재귀 vs 스택)의 장단점결론부터 말하면, 스택으로 구현해야 메모리를 덜 사용한다.재귀로 짰더니 계속 메모리 초과가 났다. 2. 비트마스크로 visited를 처리하는 방법기존의 리스트나 셋을 사용해서 노드 방문 여부를 체크하는 것과 달리 비트마스크로 구현하면 메모리 사용량을 줄일 수 있다.쉽게 생각하면 기존에 [ 0, 1, 0, 1, 0, ... ] 이렇게 저장하던 visited 0/ 1을 그냥 붙여서 이진수로 표현하는 것이다.Ob01010... 되게 심플하다.따라서 원하는 인덱스 만큼 ..

#12865 평범한 배낭 https://www.acmicpc.net/problem/12865 과거 풀다가 해결을 못해서 버렸던 문제다.  틀린코드n, k = map(int, input().split())dp = [0] * (k + 1)obj = []for _ in range(n): w, v = map(int, input().split()) dp[w] = v obj.append([w, v])for i in range(k + 1): for w, v in obj: if i + w  왜 자꾸 틀릴까? 의문이었다..  근데 잘 생각해보니, 물품의 중복이 가능한 코드였다. 주어진 테스트케이스에서 극단적인 상황을 가정해보자.무게 1, 가치 100짜리 물건이 있다면 어떻게 될까이렇게,..

#1197 최소 스패닝 트리 (https://www.acmicpc.net/problem/1197) 오랜만에 풀었다. 그래프 문제풀이는 여러가지 개념이 필요한데... 하나씩 살펴보자  그래프를 어떻게 저장할 것인가?그래프를 저장하는 방법은 세 가지가 있다.인접행렬 > 인접리스트 인접행렬이 구현이 쉽다. 대신 그만큼 메모리와 시간을 많이 쓴다.인접리스트는 비교적 메모리와 시간을 적게 쓴다. 사실, 가장 효율적인 방법은 우선순위 큐라고 할 수 있다. 다만 이는 저장 방법이 아니라, 탐색 방법이다.우선순위 큐는 큐에 우선순위를 부여한 방식인데, 파이썬에서 이를 어떻게 구현할 수 있을까? heapq라이브러리를 쓴다. 이는 최소힙을 구현한 자료구조로, 0번 인덱스에 있는 값을 기준으로 정렬된다고 생각하면 된다.따라..

#1715 카드 정렬하기 https://www.acmicpc.net/problem/1715 다음과 같이 사고했다.테스트 케이스의 모든 경우의 수를 작성해본 결과, 작은 수의 카드 집합끼리 합치는게 최소값을 도출하는 방법이란걸 알 수 있었다.  음 좀 어려웠다. 처음 사고대로 구현했는데 시간초과가 났다. 틀린코드from collections import dequen = int(input())nums = [int(input()) for _ in range(n)]nums.sort()nums = deque(nums)answer = 0while len(nums) >= 2: # print(answer, nums) tmp = nums.popleft() + nums.popleft() answer += ..

#1987 알파벳 (https://www.acmicpc.net/problem/1987) 과거 소마를 준비하던 시절 포기했던 문제였다.    틀린 코드r, c = map(int, input().split())graph = [[x for x in input()] for _ in range(r)]alpha = set(graph[0][0])dr = [1, -1, 0, 0]dc = [0, 0, 1, -1]answer = 0def solve(x,y, length): global answer answer = max(answer, length) for i in range(4): nr = x + dr[i] nc = y + dc[i] if 0  무엇이 문제였을까?? 아..