Simple Explain

#11047번 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 걍 짰는데 맞아서 당황했다. N, k = map(int, input().split()) money = [] for _ in range(N): x = int(input()) if x

#11659번 구간 합 구하기 4 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 어렵진 않았지만 시간초과가 나서 너무 짜증났던 문제 틀린코드 1 n, m = map(int, input().split()) nums = list(map(int, input().split())) for _ in range(m): i, j = map(int, input().split()) print(sum(nums[i-1:j])) 매 케이스 마..

#1780번 종이의 개수 https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 평범한 분할정복 문제라고 생각하고 열심히 짰다. 틀린코드 N = int(input()) matrix = [list(map(int, input().split())) for _ in range(N)] answer = [0, 0, 0] # 0, 1, -1 def check(mat): pivot = None for r in mat: for c in r: if pivot..

#1541번 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 모든 경우의 수를 구해야겠다는 판단에 BFS 그래프탐색으로 진행했다. 틀린코드 from collections import deque import sys # 데이터 변환 t = input() data = [] prev = 0 for i in range(len(t)): if t[i] in ["+", "-"]: data.append(str(int(t[prev:i]))) ..

#1389번 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 확실히 문제가 안풀리는 날에는 문제 이해를 제대로 안한 경우가 많아서 속상하다. 신중에 신중을 기하는 내가 되길 바란다. 내 코드 from collections import deque N, M = map(int, input().split()) network = [[] for _ in range(N+1)] for..

1. K번째 수 i,j,k가 입력되면, 전체 배열에서 i~j까지의 수를 정렬한 뒤 k번째 수를 구하면 된다. 내 코드 def solution(array, commands): answer = [] for i,j,k in commands: answer.append(list(sorted(array[i-1:j]))[k-1]) return answer 이게 조금 더 정석적인 코드라고 생각하지만 추천순 1위에는 lambda 함수를 이용한 한 줄 짜리 코드가 있었다. 그래서 나도 한 줄로 짜봤다. 한 줄 짜리 def solution(array, commands): return [sorted(array[i-1:j])[n-1] for i, j, n in commands] 하지만 이 전에도 말했든 별로 직관적이지 않아 그..

1. 기능개발 큐를 사용하면 충분히 해결할 수 있는 문제이다. 다른 사람의 코드를 보다보면, 극단적으로 짧은 코드가 많은 추천 수를 받는걸 확인할 수 있다. 너무 좋은 코드이지만 이해가 어려워 나는 아래와 같은 형태의 조금 더 직관적인 코드를 선호하는 편이다. (컴팩트하게 못짜서 그러는거 맞음ㅋㅋ) 내 코드 from collections import deque def solution(progresses, speeds): answer = [] progresses = deque(progresses) speeds = deque(speeds) while progresses: result = 0 while len(progresses) > 0 and progresses[0] >= 100: progresses.pop..

1. 완주하지 못한 선수 : 두 리스트에 중복하여 존재하지 않는 값을 찾는 문제이다. 내 풀이 def solution(participant, completion): player = {} for p in participant: try: player[p] += 1 except: player[p] = 1 for c in completion: player[c] -=1 for i in player: if player[i]: return i 베스트 풀이 import collections def solution(participant, completion): answer = collections.Counter(participant) - collections.Counter(completion) return list(an..

분할 정복 (Divide and Conquer) : 문제를 나눌 수 없을 때까지 나누어 각각의 부분을 연산한 뒤 다시 합치며 답을 얻는 알고리즘이다. 의사코드(psuedo code)를 작성해 본다면 다음과 같다. function F(x): if 문제를 더 이상 나눌 수 없는 조건: return 계산한 값 else: x를 문제의 조건 내에서 분할 return F(x1), F(x2) .... 분할한 데이터로 함수를 재귀적으로 호출 이 의사코드를 보고난 후, 문제를 어떻게 풀어야 할지 감이 바로 왔다. #2630번 색종이 만들기 https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 3..

자료구조 - 힙 (heap) : 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진트리. (Heap Tree) 영어단어 heap은 쌓아올린 더미를 의미한다. 상위 노드의 값은 항상 하위 노드보다 크거나 작아야하는 규칙이 있다. 클 경우 -> 최대 힙 (Max Heap) 작을 경우 -> 최소 힙(Min Heap) 이런 특성은, 우선순위 큐 (priority queue)를 만드는데 주로 사용된다. 데이터의 삽입과 삭제의 시간복잡도가 O ( log N ) 인 만큼 최댓값, 최솟값 탐색에 유용하게 사용된다. 힙을 직접 구현하는 작업도 언젠가 필요한 일이지만 당장에 다음주 주말 코딩테스트가 급하기 때문에 지금은 python 라이브러리를 활용한 방법을 중심으로 알아보자. 파이썬 라이브러리 이름..