Simple Explain

https://school.programmers.co.kr/learn/courses/30/lessons/12934# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr음.. 쉬운 문제라고 생각하고 풀었는데, 채점 케이스에서 마지막 케이스가 오류가 나왔다.  보통 이런 경우는 극단값을 생각하면 된다. 틀린 코드def solution(n): answer = -1 for i in range(1, n//2): # print(i) if i**2==n: return (i+1)**2 return answer 이 코드에서 생각해볼 수 있는 극단값은 무엇일까?입력..

#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번 인덱스에 있는 값을 기준으로 정렬된다고 생각하면 된다.따라..

#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  무엇이 문제였을까?? 아..