짧은코딩

해결법 1. 이 문제에서 값을 일차 배열로 준다. 그렇기에 우린 이것을 이차 배열로 바꿔야 한다. 2. 오른쪽과 오른쪽 위, 아래로 이동할 수 있다는 것은 반대로 생각하면 왼쪽과 왼쪽 위, 아래에서 온다는 의미이다. 3. 쭉 더하고 마지막 열 중에서 가장 큰 값을 찾는다. 코드 answer = [] for t in range(int(input())): n, m = map(int, input().split()) ary = list(map(int, input().split())) dp = [] index = 0 for i in range(n): dp.append(ary[index:index + m]) index += m for j in range(1, m): for i in range(n): # 왼쪽 위면 ..

해결법 이 문제는 원하는 숫자 x의 가장 첫번째 위치와 마지막 위치를 구해서 빼면 되는 문제이다. -bisect 라이브러리 from bisect import bisect_left, bisect_right bisect_right(ary, x) bisect_left(ary, x) ary는 집합, x는 원하는 값 이렇게 작성하면 된다. 예를 들어 bisect_right는 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾아준다. 시작 복잡도는 O(logN)이다. 교재 코드 from bisect import bisect_left, bisect_right n, x = map(int, input().split()) ary = list(map(int, input().split())) a..

https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 해결법 이 문제를 처음 보고 너무 복잡하게 생각했다. 곰곰히 생각을 하다가 "이 지문에 나온 정렬 조건을 반대로 실행하면 어떨까?" 생각이 들었다. 그래서 구글링을 했고 파이썬에 다중 정렬을 봤다. 이 문법을 자주 사용했지만 매번 잊어버렸고 정식 이름을 알게된건 이번이 처음이다. 그레서 잘 기억해야 겠다고 생각했다. -다중 정렬 ary = sorted(ary, key = la..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 해결법 -다익스트라(91% 정도에서 틀림) 사실 처음 보고 이 문제는 무조건 다익스트라로 풀어야겠다고 생각했다. 하지만 왜인지 91%에서 계속 틀렸다. -bfs(이게 정답) 1. distance에 모든 노드의 값을 -1로 저장하고 시작 노드만 0으로 바꿔준다. 2. queue를 만들고 시작 노드 번호를 담는다. 3. 연결되어..

https://www.acmicpc.net/problem/18406 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 해결법 이 문제는 숫자를 입력 받고 mid로 왼쪽 값과 오른쪽 값을 나눌 수 있다. 그리고 left, right에 값을 저장하고 left와 right가 같으면 LUCKY를 출력하고 다르면 READY를 출력한다. 코드 n = input() ary = [] for i in range(len(n)): ary.append(int(n[i])) left = 0 right = 0 mid = len(n) // 2 for i in range(mid): left +..

내 풀이 from collections import deque n = int(input()) ary = list(map(int, input().split())) ary.sort() ary = deque(ary) answer = 0 while ary: max = ary.pop() - 1 while True: if ary: ary.popleft() max -= 1 if max == 0: answer += 1 break else: break print(answer) 일단 각 인원들의 공포도를 입력 받고 오름차순으로 정렬한다. 그리고 answer에 완성된 팀의 수를 저장한다. 내가 푼 풀이로는 가장 큰 수를 max에 저장하고 그 인원이 들어왔으니 -1을 해서 저장한다. 그리고 공포도가 낮은 인원을 max가 0이..

해결법 이 문제는 위상 정렬로 풀면 되는 문제이다. 위상 정렬로 구현은 잘 했지만 디테일한 해결법은 생각하지 못했다. 처음에 각 과목이 걸리는 시간을 저장한 리스트를 만든 다음에 현재 노드에서의 시간과 다음으로 할 과목의 시간을 더한 값을 리스트에 갱신하면서 해결하면 된다. 이때 copy 라이브러리에서 deepcopy 함수를 사용한다. 이것을 사용하지 않으면 얕은 복사가 이루어져서 값이 꼬이게 된다. 자세한건 코드에서 보면 될 것 같다. 코드 from collections import deque import copy n = int(input()) indegree = [0] * (n+1) graph = [[] for i in range(n+1)] weight = [0] * (n+1) for i in ran..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 해결법 이 문제는 최소 비용을 구하는 문제이고 신장 트리를 만들어야 하는 문제라서 크루스칼 알고리즘으로 풀어야 한다. 다만 유의할 부분은 임의의 두 집 사이에 경로가 항상 존재해서 길을 더 없앨 수 있기 때문에 길 유지비를 최소로 하려면 가장 큰 값을 가진 길 하나를 없애면 된다. 그렇기에 가장 작은 유지 비용을 가진 길부터 연결한다고 했을 때 가장 마지막에 ..

해결법 문제를 보고서 이 문제는 경로 압축으로 루트 노드를 찾는 함수를 팀 합치기 연산으로 사용한다. 그리고 루트 노드가 같은지 판단하는 함수를 같은 팀 여부 확인으로 풀었다. 코드(한번에 맞음) n, m = map(int, input().split()) def find_parent(parent, x): if parent[x] != x: find_parent(parent, parent[x]) return parent[x] def union(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b parent = [i for i in range(n+1)] answ..

위상 정렬 위상 정렬은 정렬 알고리즘의 일종이다. 순서가 정해져 있는 작업을 차례대로 수정할 때 사용하는 알고리즘이다. 예시로는 선수 과목을 고려한 학습 순서 설정이 있다. 예를 들어 자료구조, 알고리즘, 고급 알고리즘이 있다. 그리고 (알고리즘의 선수 과목은 자료구조), (고급 알고리즘의 선수 과목은 알고리즘)이면 자료구조 -> 알고리즘 -> 고급 알고리즘으로 수업을 들어야한다. 위상 정렬은 먼저 진입차수를 알아야 하는데, 진입차수느 특정 노드로 들어오는 간선의 개수를 의미한다. 잔입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지, 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 위 과정을 거치다가 모든 원소를 방문하기 전에 큐..