분류 전체보기
[백준] 1916 최소비용 구하기 파이썬
문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다. 입력 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘..
[HTTP] HTTP 상태코드
HTTP 상태코드 소개 • 1xx (Informational): 요청이 수신되어 처리중 • 2xx (Successful): 요청 정상 처리 • 3xx (Redirection): 요청을 완료하려면 추가 행동이 필요 • 4xx (Client Error): 클라이언트 오류, 잘못된 문법등으로 서버가 요청을 수행할 수 없음 • 5xx (Server Error): 서버 오류, 서버가 정상 요청을 처리하지 못함 만약 389처럼 클라이언트가 인식할 수 없는 상태코드를 보낸다면 클라이언트는 3xx, 즉 상위 상태코드로 해석해서 처리한다 1xx 요청 처리중 코드는 거의 사용되지 않는다. 2xx - 성공 200 OK - 요청 성공 - 매우 자주 사용됨 201 Created - 요청 성공해서 새 리소스 생성됨 - Locat..
[프로그래머스] 2021 카카오 블라인드 - 합승 택시 요금 파이썬
문제 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다. 위 예시 그림은 택시가 이동 가능한 반경에 있는 6개 지점 사이의 이동 가능한 택시노선과 예상요금을 보여주고 있습니다. 그림에서 A와 B 두 사람은 출발지점인 4번 지점에서 출발해서 택..
그래프 알고리즘 정리 - 파이썬
그래프 알고리즘 분류 그래프는 최소신장트리와 최단거리 문제로 나눌 수 있다. 각기 사용되는 알고리즘이 다르다. MST (최소신장트리) 크루스칼 - 간선기준 가장 작은것부터 연결, 음의 간선 가능 프림 - 정점기준 정점에 연결된 가장 작은 간선으로 연결, 음의 간선 가능 간선 개수가 적으면 크루스칼, 정점 개수가 적으면 프림 적용 최단경로 다익스트라 (우선순위큐 heapq 사용, 단일 정점 최단경로) 벨만-포드 (음의 가중치, 경로 추적 가능) 플로이드 와샬 (음의 가중치, 3중포문, 모든 정점 사이 최단거리) shortest path faster algorithm 크루스칼 간선을 정렬하여 가중치가 작은 간선부터 연결 사이클이 발생하면 연결하지 않음 O(E * log(E)) 프림 한 정점의 간선 중 가중치..
[백준] 1700 멀티탭 스케줄링 파이썬
문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 현재 탭에 꽂혀있는 제품 중 가장 나중에 사용되는 제품을 뽑는 그리디 문제였다. next에 현재 스케줄 뒤로 제품별로 가장 빨리 사용되는 순번을 저장해놓는다. 멀티텝에 꽂힌 제품 중 next에서 가장 번호가 큰 것을 제거한다. n, k = map(int, input().split()) order = list(map(int, input().split())) next = {} for i i..
[백준] 1806 부분합 파이썬
문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 그냥 투포인터로 풀면 되는 문제였다. st 부터 ed까지의 합이 s 미만이면 ed를 한 칸 뒤로 옮기고 s 이상이면 st를 한 칸 뒤로 옮겨 sum 에서 st에 해당하는 값을 뺐다. 불가능할 경우 0을 출력하라는 문구를 못 봐서 틀렸었다. n, s = map(int, input().split()) arr = list(map(int, input().split())) st =..
[백준] 1062 가르침 파이썬
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 공통으로 포함되는 알파벳 a c n t i를 제외하고 중복을 없애기 위해 set으로 각 단어를 읽기 위해 추가로 필요한 알파벳들을 구한다. 그 다음 전체 알파벳에서 a c n t i 를 제외한 k-5개의 조합을 만들어 각 조합별로 몇 개의 단어를 읽을 수 있는지 세려고 했다. 그런데 조합 만들어서 테스트하는 부분에서 연산이 엄청 많이 시행될 것 같았다. 뭔가 시간초과의 느낌이 나..
[백준] 14719 빗물 파이썬
문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 가장 아래쪽부터 반복문을 돌며 왼쪽이 뚫려 있을 때는 -1 막혀있으면 0으로 바꿔주고 그 다음 블록부터 카운트를 시작해서 비어있는 칸이 있을 때마다 1씩 더해줬다. O(n^2)이라 이게 될까? 싶었는데 통과했다. h, w = map(int, input().split()) heights = list(map(int, input().split())) answer = [0]*..