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

고민의 시작redis의 Redlock과 원자적 연산에 대해 개념을 헷갈리는 것 같아 정리했다.  RedLockredlock은 redis를 이용한 분산 락 알고리즘이다.redis를 여러 개의 인스턴스에서 실행할 때, 동일한 키에 대해 신뢰성 높은 락을 보장하는 방법단일 redis 노드에서 SETNX (SET if Not Exists)로 락을 구현하는 방식이 신뢰성이 부족한 문제를 해결하기 위해 고안됐다.  Redlock이 필요한 이유기본적으로 redis의 SETNX 를 사용하면 단일 인스턴스에서만 락이 보장된다.하지만 단일 Redis 서버가 다운되면 락이 풀릴 수 잇는 문제가 있다.이를 해결하기 위해 여러 개의 Redis노드에 락을 분산 저장하여 가용성과 신뢰성을 높이는 것이 Redlock의 핵심 아이디어..

고민의 시작 프로젝트을 진행하면서, 다른 사람들이 구현한 기능에는 간단한 지식만으로 알고 넘어간 부분이 있었다.하지만, 팀원이 구현한 코드 일지라도 우리 서비스에 대한 문제 해결 방식을 설명하기 위해 팀원이 구현한 해결 방법은 설명할 수 있어야 한다고 생각한다.번외로 만약 내가 구현했다면 어떻게 해결할 것인가? 라는 질문이 왔을때, 명확하게 대답하지 못하는 내 자신을 보고 아는것과 본 것에 대한 명확한 구분선을 지어야 겠다고 생각했다.    왜 이 고민이 필요해?💡 Race Condition 문제에서 MYSQL의 낙관적 락과 비관적 락으로 해결 했을때 어떤 장단점이 있는가? Redis 도입 시, 관리포인트 문제를 고려하지 않을 수 없다.만약, mysql로 쿠폰 발급을 한다면 어떻게 해결할 수 있을까? ..