본문 바로가기

Python48

[백준] 12865번 - 평범한 배낭 (파이썬, C++) 문제) 백준 - 동적 계획법 (Dynamic Programming) - 평범한 배낭 -> www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1 2 3 4 5 6 7 ( 6, 13 ) 0 0 0 0 0 13 13 ( 4, 8 ) 0 0 0 8 8 13 13 ( 3, 6 ) 0 0 6 8 8 13 14 ( 5, 12 ) 0 0 0 0 12 13 14 (물건 무게, 가치)가 (3, 4)인 경우를 주목.. 2021. 3. 11.
[Algorithm] 위상 정렬 - Topology Sort (파이썬, C++) 위상 정렬 - Topology Sort 위상 정렬은 순서가 정해져 있는 노드들을 차례대로 정렬할 때 사용할 수 있는 알고리즘이다. 더 개념적으로 정의하자면, 위상 정렬이란 "방향 그래프의 모든 노드를 방향성에 따라 정렬"하는 것이다. 위상 정렬에서 그래프는 방향 그래프이므로 각 방향에 대한 간선이 존재한다. 이때 어떤 노드가 다른 노드를 가리킬 때, 들어오는 간선의 개수를 "진입 차수"라 한다. 위상 정렬 알고리즘 ① 진입 차수가 0인 노드를 큐에 넣는다. ② 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. ③ 새롭게 진입 차수가 0이 된 노드를 큐에 넣는다. ④ 큐가 빌 때까지 ②,③ 과정을 반복한다. 파이썬 소스 코드) C++ 소스 코드) 위상 정렬의 시간 복잡도 위상 정렬을 .. 2021. 3. 10.
[백준] 2252번 - 줄 세우기 (파이썬) 문제 및 풀이 문제) 백준 - 위상 정렬 (Topology Sort) - 줄 세우기 -> www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 전형적인 위상 정렬 문제. 각 학생들의 키 비교를 진입 차수로 생각하여 위상 정렬하면 된다. 소스 코드) from collections import deque v, e = map(int, input().split()) #진입 차수 indegree = [0] * (v + 1) graph = [[] for i.. 2021. 3. 10.
[백준] 11054번 - 가장 긴 바이토닉 부분 수열 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic programming) - 가장 긴 바이토닉 부분 수열 -> www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net (백준 - 11053번)가장 긴 증가하는 부분 수열 문제와 (백준 - 11722번) 가장 긴 감소하는 부분 수열 문제를 합치면 풀 수 있다. 가장 긴 증가하는 부분 수열의 아이디어를 채택해 우리는 1~n까지 탐색( i )하면서 그 이전까지 i번째 숫자보다 작으면서도 가장 긴 증가하는 부분 수열의 길이를 저장한다. 가장 긴 증가.. 2021. 3. 9.
[백준] 11722번 - 가장 긴 감소하는 부분 수열 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 가장 긴 감소하는 부분 수열 -> www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net 참고) 2021.03.02 - [Algorithm_note/틀린 문제] - [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) [백준] 11053번 - 가장 긴 증가하는 부분 수열 (파이썬) 문제) 백준 - 동적 계획법 .. 2021. 3. 9.
[백준] 1890번 - 점프 (파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 점프 -> www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 오른쪽이나 아래로 점프가 가능한 경우 dp 리스트에 +1 해준다. (0, 0)부터 시작해 (n - 1, n - 1)까지 재귀로 완전 탐색하며 (n - 1, n - 1)일 때 기저 사례를 처리해 1을 반환한다. 소스 코드) import sys sys.setrecursionlimit(1000000) input = sys.s.. 2021. 3. 9.
[백준] 1520번 - 내리막 길 (C++, 파이썬) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 내리막 길 -> www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 각 지점까지 이동할 수 있는 경로의 수를 저장한 2차원 리스트(dist)에 메모이제이션을 적용한다. dist 리스트의 초기값을 -1로 선언해 방문 여부를 판단한다. 각 지점까지 이동할 수 있는 경우의 수는 dfs를 이용하여 경로가 겹치는 지점에서 서로의 경로 수를 합친다. Python 소스 코드) C++ 소스 코드) Python .. 2021. 3. 9.
[프로그래머스] 2019 카카오 공채 - 실패율 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2019 카카오 공채 - 실패율-> 코딩테스트 연습 - 실패율 | 프로그래머스 (programmers.co.kr)코딩테스트 연습 - 실패율실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스programmers.co.kr ① 나의 풀이관찰을 하다 보면 플레이어가 도달한 스테이지( j )와 해당 스테이지( i )를 비교하여 실패율을 계산하여 실패율과 해당 스테이지를 result 리스트에 넣어준다. 플레이어가 도달한 스테이지가 해당 스테이지보다 높은 경우( j > i ): 플레이어는 스테이지에 도달했고 성공한 경우이므로 participant만 1을 늘린.. 2021. 3. 4.
[프로그래머스] 2019 카카오 공채 - 오픈채팅방 (파이썬) 문제 및 풀이 문제) 프로그래머스 - 2019 카카오 공채 - 오픈채팅방 -> 코딩테스트 연습 - 오픈채팅방 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr ① 나의 풀이 Dictionary 형태로 record의 유저 아이디와 닉네임을 취합하기 위해서 collections의 Counter 모듈을 이용하자. 각 record의 원소를 split 하여 order 리스트로 받아준다. record탐색을 두 번 해주는데, 첫 탐색에서 유저 아이디에 대한 최종 닉네임을 결정해주고 두 .. 2021. 3. 4.
반응형

티스토리툴바