Python
-
[Python] 백준 14890 경사로알고리즘/삼성 역량 문제 2022. 1. 16. 12:26
1. 문제 링크 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 2. 문제 요약 총 2n개의 길이 존재할 때, 지나갈 수 있는 길의 개수를 출력한다. 낮은 칸과 높은 칸의 차이는 1이고, 낮은 칸에 경사로를 L길이만큼 설치해야 한다. 3. 아이디어 정리 한 줄 씩 확인해야하기 때문에 한줄 기준으로 지나갈 수 있는 길인지 확인하는 함수를 작성한다. 지나갈 수 있는지 확인하는 함수는 아래 로직을 따른다. 이전 칸과 현재 칸이 1칸 높이 이상이면 False 현재 높이 < ..
-
[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 ..
-
위상정렬(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,..