분류 전체보기
-
[Python] 백준 11404 플로이드알고리즘/문제풀이 2022. 1. 8. 22:38
1. 문제 링크 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 문제 요약 a → b로 가는 비용의 최솟값 모두 구하기 3. 아이디어 정리 플로이드 와샬. 모든 정점 최단 거리 구하기 참고 - 플로이드 와샬 💡 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용 플로이드 워셜 점화식 각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다. a에서 b로 가는 최단 거리, a에서 k를 거쳐 ..
-
[Python] 백준 17135 캐슬 디펜스알고리즘/문제풀이 2022. 1. 1. 16:46
1. 문제 링크 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 2. 문제 요약 3명 궁수 배치 적 공격: 거리가 D 이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 적 아래로 한칸 이동 모든 적이 없으면 끝! 출력: 궁수의 공격으로 제거할 수 있는 적의 최대 수 3. 아이디어 정리 구현 문제 3명 궁수 배치 ⇒ 삼성 문제라서 combinations 함수를 직접 구현하였다.⇒ 삼성 코테는 지원 안 함 ..
-
[Python] 백준 2252 줄세우기알고리즘/문제풀이 2021. 12. 15. 18:04
1. 문제 링크 https://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 2. 문제 요약 학생들을 키 순서대로 줄을 세운 결과를 출력한다. 3. 아이디어 정리 위상 정렬 진입 차수가 0인 모든 노드에 큐 넣기 큐가 빌 때까지 반복 큐에서 한 개 빼고 결과에 넣기 큐에서 원소를 꺼내 나가는 간선 제거 새롭게 진입차수가 0이 된 노드에 큐 넣기 4. 문제 풀이 4-1. 내풀이 import sys from colle..
-
[Python] 백준 2623 음악프로그램알고리즘/문제풀이 2021. 12. 15. 17:58
1. 문제 링크 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 문제 요약 PD들이 만든 가수 순서 주어질 때, 전체 가수 순서를 정하여 순서를 출력한다. 3. 아이디어 정리 위상 정렬 진입차수가 0인 모든 노드에 큐 넣기 큐가 빌 때까지 반복 큐에서 한 개 빼고 결과에 넣기 큐에서 원소를 꺼내 나가는 간선 제거 새롭게 진입차수가 0이 된 노드에 큐 넣기 4. 문제 풀이 4-1. 내풀이 import sys from co..
-
[Python] 백준 14567 선수과목알고리즘/문제풀이 2021. 12. 15. 17:31
1. 문제 링크 https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 2. 문제 요약 1번 과목부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지 출력한다. 3. 아이디어 정리 위상 정렬 진입 차수가 0인 모든 노드에 큐 넣기 큐가 빌 때까지 반복 큐에서 원소를 꺼내 나가는 간선 제거 새롭게 진입차수가 0이 된 노드에 큐 넣기 & 결과 넣기(최소 이수 학기, 현재 노드 결과 + 1) 4. 문제 풀이 4-1. 내풀이 import sys from collections ..
-
[Python] 백준 14888 연산자 끼워넣기알고리즘/삼성 역량 문제 2021. 12. 15. 17:18
1. 문제 링크 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 문제 요약 N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것 구하기 3. 아이디어 정리 백트래킹으로 진행 Base condition(종료 조건): 모든 연산자를 넣은 경우 재귀: 사칙연산을 4개를 돌려 계산을 하고 백트래킹 진행 4. 문제 풀이 4-1. 내 풀이 """ 1. ..
-
위상정렬(Topological Sorting)알고리즘/알고리즘 공부 정리 2021. 12. 14. 23:46
이번 시간에는 위상 정렬에 대한 개념과 동작 과정을 알아본다. 이후 위상 정렬을 Python으로 구현해 본다. 1. 위상 정렬(Topological Sorting) 💡 정렬 알고리즘의 일종으로, 순서가 정해진 일련의 작업을 차례대로 수행해야 할 때 사용하는 알고리즘이다. ⇒ 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다. 1-1. 예시 - 선수과목을 고려한 학습 순서 설정 그림과 같이 총 3개의 과목이 있다고 가정하자. 세 과목을 모두 듣기 위해서는 자료구조 -> 알고리즘 -> 고급 알고리즘 (O) 순서로 과목을 들어야 한다. 만약 알고리즘 -> 자료구조 -> 고급 알고리즘 (X) 순서로 과목을 듣는다고 가정하자. 해당 순서는 올바른 학습 순서가 아니다..
-
[Python] programmers 여행 경로알고리즘/문제풀이 2021. 12. 12. 12:49
1. 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 2. 문제 요약 방문하는 공항 경로를 배열에 담아 return 3. 아이디어 정리 백트래킹으로 진행합니다. 처음 ICN를 배열에 담아 넘겨줍니다. 티켓들 중 마지막으로 탐색한 값과 시작값이 같은 티켓 & 방문 안한 경우 재귀를 진행합니다. 4. 문제 풀이 4-1. 내 풀이 """ 항상 ICN 공항에서 출발 [a,..