1223v

sort를 이용한 풀이 (메모리 : 622180KB, 실행시간 : 3452ms)import sysinput = sys.stdin.readlineN, K = map(int,input().split())A = list(map(int,input().split()))A.sort()print(A[K-1])위 코드는 단순히 파이썬의 timsort를 사용해 정렬 후, K번째의 인덱스를 가져왔다.시간복잡도파이썬의 내장 sort() 함수의 시간복잡도는 평균적으로나 최악의 경우로나 O(NlogN)이다.정렬 후 원소를 찾는 것은 O(1)이므로따라서, 전체 시간복잡도는 정렬에 의해 결정되어 O(NlogN)이다. heap을 이용한 풀이 (메모리 : 626184KB, 실행시간 : 5164ms)import sysimport hea..

고민의 시작근래 들어 PS 지식이 부족함을 느꼈다.특히 이진 탐색에 굉장히 약하다고 느꼈는데, 아무래도 동작 방식을 너무 두루뭉실하게 알고 있던게 아닐까 생각한다.      왜 이 고민이 필요해?명확한 동작방식을 이해하고, binary_search를 응용한 문제를 통해 문제해결을 명확하게 하고자 한다.이후, 파이썬에서는 bisect라는 라이브러리를 제공하는데 이에 내부 구현을 살펴보고, 구현 및 응용을 해보고자 한다.     Binary Search란?이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다.동작 원리현재 데이터 셋의 중앙값을 선택한다중앙값 > 타깃 데이터 일 때 중앙값 기준으로 왼쪽 데이터 셋을 선택한다중앙값 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐..

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 다익스트라 응용 문제이다.1. a, b 각각 가는 비용을 다익스트라로 구한다.2. a, b 각각 구한 비용을 중심으로 비교할 대상을 반복을 돌며, (s -> i 의 동행 거리) + (i -> a 거리) + (i -> b 거리) 가 최소가 되는 것을 찾으면 된다. import heapqdef solution(n, s, a, b, fares): answer = 0 graph=[[] for _ in range(n+1)] for sta..

https://www.acmicpc.net/problem/1719  플로이드 워셜로 푸는 대표적인 문제이다.거리 배열 외에도 정답배열을 통해 최단 경로시 가장 먼저 접근해야하는 노드의 값을 테이블로 만들어야 한다. import sysinput = sys.stdin.readlineN,M = map(int,input().split())distance = [[float('inf')] * (N+1) for _ in range(N+1)]graph = [[0] * (N+1) for _ in range(N+1)]for _ in range(M): s,e,cost = map(int,input().split()) if distance[s][e] > cost: distance[s][e] = cost ..

https://www.acmicpc.net/problem/17609   히든 케이스를 잘 고려해야하는 문제이다.또한, 파이썬은 시간 초과 상황이 발생할 수 있으므로 잘 확인하면 풀어야 한다. import sysinput = sys.stdin.readlineTC = int(input())for _ in range(TC): s = input().rstrip() if s == s[::-1]: print(0) continue start = 0 end = len(s) - 1 while start    회고.예외 상황이 너무 많고 히든케이스가 너무 많아 틀릴 수 있는 가능성이 너무 높았던거 같다...

https://www.acmicpc.net/problem/11404  대표적인 플로이드 워셜 문제이다. 모든 경로에서의 최단경로를 출력하는 문제이다. 3중 for 문을 통해 값을 최신화 한다. import sysinput = sys.stdin.readlineN = int(input())M = int(input())graph = [[] for _ in range(N+1)]distance = [[float('inf')]*(N+1) for _ in range(N+1)]for i in range(1, N+1): distance[i][i] = 0for _ in range(M): s,e,cost = map(int,input().split()) if distance[s][e] > cost: ..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  누적합을 응용한 문제이다.누적합 배열을 degree의 값을 응용하는 것으로 쓴다.def solution(board, skill): answer = 0 M, N = len(board[0]),len(board) tile = [[0 for _ in range(M+1)] for _ in range(N+1)] for type, r1, c1, r2, c2, degree in skill: if type == 1: ..

https://www.acmicpc.net/problem/19598 최소힙을 사용한 그리디 문제이다.우선 받은 배열을 정렬한다이후, 배열을 순회하며 힙 내에 도착지에 최소값이 다음 start 값보다 작다면 회의실을 연결되서 쓸 수 있다는 뜻이므로, 힙에서 나온 도착지의 최소값을 pop 해준다. 다음 최소힙에 무조건 값을 넣어준다. (회의실 무조건 배정) pythonimport sysimport heapqinput = sys.stdin.readlineN = int(input())s = sorted([list(map(int,input().split())) for _ in range(N)])hq = []for start, end in s: if hq and hq[0]  Rubyrequire 'set're..

https://school.programmers.co.kr/learn/courses/30/lessons/64064?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문자열 탐색 후, 조합을 사용해서 경우의 수를 새는 문제이다.주의해야 할 점은 "*" 로 꽉채워져 있는경우가 존재함으로 경우의 수끼리 겹치는게 있는데 문제에서는 중복을 허용하지 않는다고 했으니 중복 검증과 정렬을 통해 구분을 잘해야 하는 문제이다. Pythonfrom itertools import productdef solution(user_id, banned_id): answer = set() ban_..

https://www.acmicpc.net/problem/27961  그리디 문제이다. 횟수를 세는 부분으로 마지막 넘치는 것은 고려하지 않고 풀어도 되는 문제이다. Pythonimport sysinput = sys.stdin.readlineN = int(input())magic = 0cat = 0while N > cat: if cat == 0: cat += 1 else: cat *= 2 magic += 1print(magic) RubyN = gets.to_icat = 0magic = 0while N > cat if cat == 0: cat += 1 else cat *= 2 endendputs magic 회고.단순한 그리디 문제인데 마지막..