본문 바로가기

Algorithm705

[자료구조/리스트] 백준 2605 줄 세우기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 2605번: 줄 세우기 점심시간이 되면 반 학생 모두가 한 줄로 줄을 서서 급식을 탄다. 그런데 매일 같이 앞자리에 앉은 학생들이 앞에 줄을 서 먼저 점심을 먹고, 뒷자리에 앉은 학생들은 뒤에 줄을 서 늦게 점심을 www.acmicpc.net 2. 문제 풀이 뽑은 번호만큼 앞으로 가서 서는 문제입니다. 0부터 앞 사람의 수만큼 번호를 뽑을 수 있으며, 뽑은 번호만큼 앞으로 전진합니다. 입력에는 순서대로 뽑은 번호가 주어지며, 줄은 선 순서를 출력해야 합니다. list.insert(index, n): list의 index 위치에 n을 삽입 파이썬은 연결리스트가 기본 자료구조로 내장되어 있습니다. 따라서 그대로 list 자료구조를 사용하면 됩니다. 뽑은 번호 .. 2022. 5. 20.
[브루트포스] 백준 3040 백설 공주와 일곱 난쟁이 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 3040번: 백설 공주와 일곱 난쟁이 매일 매일 일곱 난쟁이는 광산으로 일을 하러 간다. 난쟁이가 일을 하는 동안 백설공주는 그들을 위해 저녁 식사를 준비한다. 백설공주는 의자 일곱개, 접시 일곱개, 나이프 일곱개를 준비한다. www.acmicpc.net 2. 문제 풀이 9개의 수 중, 합이 100이 되는 7개의 수를 고르는 문제입니다. 2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법? [Algorithm] 브루트 포스(Brute Force)는 노가다 기법? [ Contents ] 1. 브루트 포스란? Brute(짐승 같은, 난폭한) + Force(힘, 폭력)의 합성어입니다. 무식하게 .. 2022. 5. 19.
[탐색/다익스트라] 백준 11779 최소비용 구하기 2 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 문제 풀이 최소의 버스비용으로 A에서 B로 이동하는 문제입니다. 최소비용과 경로를 출력해야 합니다. 2022.05.17 - [Algorithm] - [탐색/다익스트라] 백준 1916 최소비용 구하기 - 파이썬(Python) 이전 문제인 '최소비용 구하기'에서, '경로 출력'이 추가되었습니다. 다익스트라 알고리즘으로 최적 거리를 찾은 뒤, 역추적해서 경로를 출력해야 합니다. 202.. 2022. 5. 18.
[탐색/다익스트라] 백준 1916 최소비용 구하기 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 2. 문제 풀이 최소의 버스비용으로 출발지에서 도착지로 이동해야 합니다. 2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지까지의 최적 경로를 탐색해주는 알고리즘입니다. 다익스트라의 이론적.. 2022. 5. 17.
[탐색/다익스트라] 백준 1504 특정한 최단 경로 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 2. 문제 풀이 1번 정점에서 N번 정점으로 가는 최단 거리를 구하는 문제입니다. 단, 정점 v1, v2를 꼭 지나야 합니다. 2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지.. 2022. 5. 16.
[탐색/다익스트라] 백준 1753 최단경로 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 2. 문제 풀이 시작점에서 다른 모든 노드로의 최단 거리를 구하는 문제입니다. 2022.03.22 - [Algorithm] - [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 [Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지까지의 최적 경로를 탐색해주는 알고리즘입니다. 다익스트라.. 2022. 5. 15.
[분할정복/DQ] 백준 11444 피보나치 수 6 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 풀이 n번째 피보나치 수를 구하는 문제입니다. 본래 피보나치 수열은 동적계획법 DP를 이용해서 효율적으로 구할 수 있지만, 이 문제에서는 최대 n이 1,000,000,000,000,000,000입니다. 아주 큰 수의 피보나치를 빠르게 구하기 위해서는 분할정복을 이용한 '행렬의 거듭제곱'을 사용해야 합니다. 피보나치 규칙을 행렬로 나타내면 아래와 같습니다. 2022.05.10 - [Algorithm] - [분할정복/DQ] 백준 10830 행렬 제곱 - 파이썬(Python) 결국 행렬의.. 2022. 5. 14.
[수학/소수] 백준 1418 K-세준수 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1418번: K-세준수 첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 풀이 N 이하 자연수 중에서 소인수의 최댓값이 K보다 작은 수들의 개수를 구하는 문제입니다. N: 10, K: 3일 때, 10이하의 자연수 중 소인수가 3보다 작은 수들의 개수는 7입니다. 숫자 1 2 3 4 5 6 7 8 9 10 최대 소인수 x 2 3 2 5 3 7 2 3 5 위 예제에서 5, 7, 10은 3보다 큰 소인수를 갖고 있습니다. 따라서 K-세준수는 7개입니다. 2022.02.08 - [Algorithm] - [Algorithm] 소수 판별 알고리즘,.. 2022. 5. 13.
[구현/수학] 백준 1434 책 정리 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 1434번: 책 정리 첫째 줄에 박스의 개수 N, 책의 개수 M이 주어진다. 둘째 줄에는 박스의 용량 A1, A2, ..., AN이 주어지고, 셋째 줄에는 B1, B2, ..., BM이 주어진다. www.acmicpc.net 2. 문제 풀이 1. 현재 책이 현재 박스에 들어가지 않으면, 3번으로 간다. 아니면 2번으로 간다. 2. 현재 책을 현재 박스에 넣는다. 다음 책을 손에 집고 1번으로 간다. 3. 현재 박스를 다른 쪽으로 치운 다음에, 테이프로 못 열게 봉인한다. 다음 박스를 앞으로 가져오고 1번으로 간다. 책을 박스에 보관할 때, 낭비되는 박스 용량을 구하는 문제입니다. 다국어 문제라서 번역이 조금 어색합니다. 위 로직을 조금 쉽게 풀어쓰면 아래와.. 2022. 5. 12.

티스토리툴바