1223v

고민의 시작근래 들어 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 회고.단순한 그리디 문제인데 마지막..

https://school.programmers.co.kr/learn/courses/30/lessons/70130 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  음수간선이 존재하는 벨만포드 문제이다.하지만, 음수 간선을 판별 혹은 음수 간선인 부분을 찾는 것이 아닌 음수 간선을 피해 값이 증가하는 방향으로 나아가 최대한 높은 값으로 도착지에 도착해야하는 문제이다.  하지만, 만약 사이클이 존재하고, 마지막 도착 지점이 음수 간선 사이클이라면, -1을 출력하는 문제이다. import sysinput = sys.stdin.readlineN,M = map(int,input().split())graph = ..