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..

대 AI 시대를 맞이한 신입 개발자들빠르게 변화하는 AI시대를 맞이하면서 신입개발자 모두가 AI를 활용해 개발을 하고 있다…방대한 프로젝트도 짧은 시간 내에 AI 복붙으로 서비스를 만들 수 있게 되었고,기존에 하루를 쏟아도 해결할 수 없는 문제를 1시간안에 해결할 수 있게 되었다. 우리 모두가 느낄 것이다...지난 2년과는 사뭇다른 프로젝트의 퀄리티로 결과물이 나온다는 것을… 하지만 그것이 본질적으로 나의 힘이라고 할 수 있을까? A: 아니다.. 기술에 대한 비교는 의미가 없어진 시대가 왔다는 것이다. 비슷한 사례로 지금껏 30년간 무공을 연마해온 절대 고수가 이제 어린 아이가 쏜 총 한방에 목숨을 잃는 그런 상황이 IT업계에서도 벌어지기 시작했다는거다 절대 고수들도 그런데 신입 개발자들은 당연히 점자 ..

고민의 시작근래 들어 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_..