분류 전체보기
백준 1504(특정한 최단 경로) - Python(파이썬) - 최단 경로
백준 1504(특정한 최단 경로) - Python(파이썬) - 최단 경로
2022.06.12참고자료 : 다익스트라 알고리즘 참고 자료 [이코테] CHAPTER 09 최단 경로 알고리즘 - 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘(Shortest Path) : 가장 짧은 경로를 찾는 알고리즘 1) 최단 경로 문제- 지점( 노드 ), 지점 간 연결된 도로( 간선 ) - 한 지점에서 다른 한 지점까지의 최단 경로를 구해야 하는 경우 coooco.tistory.com 예제 설명 1번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 0 3 5 4 2번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 3 0 3 4 3번 노드에서 시작할 경우 도착 노드 1번 2번 3번 4번 최소 비용 5 3 0 1 1번 노드 -> 2번 노드 -> 3번 노드 -> 4번노드 인경우 최..
[이코테]CHAPTER 09 최단 경로 알고리즘 - 플로이드워셜 알고리즘 - Python(파이썬),Java(자바)
[이코테]CHAPTER 09 최단 경로 알고리즘 - 플로이드워셜 알고리즘 - Python(파이썬),Java(자바)
2022.06.11참고자료 : https://www.youtube.com/watch?v=acqm9mM1P6o 📎 다익스트라(Dijkstra) 알고리즘과 플로이드 워셜(Floy-Warshall) 알고리즘의 차이 1) 다익스트라(Dijkstra) 알고리즘 - 자세한 설명은 : https://coooco.tistory.com/36?category=1071114 - 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우에 사용하는 알고리즘 - 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택 -> 해당 노드를 거쳐가는 경로 확인 -> 최단 거리 테이블 갱신 - 그리디 알고리즘 2) 플로이드 워셜(Floy-Warshall) 알고리즘 - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용하..
백준 10819(차이를 최대로)- Python(파이썬),Java(자바) - 구현,브루트포스(Permutations,Combinations,백트래킹,Java- 스택 사용 )
백준 10819(차이를 최대로)- Python(파이썬),Java(자바) - 구현,브루트포스(Permutations,Combinations,백트래킹,Java- 스택 사용 )
2022.06.0910819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 예제 설명 일단 배열 A를 오름차순으로 정렬한다. 인덱스 0 1 2 3 4 5 배열 1 4 8 10 15 20 인덱스의 차이가 최대이기 위해서는 고른 인덱스와 선택하지 않은 배열 중 제일 먼 인덱스를 골라야한다. ex ] 0고르기 -> 5고르기 -> 1고르기 -> 4고르기 -> 2고르기 -> 3고르기 하지만 마지막에 2를 고르고 3을 고르는 것보다 인덱스 3을 제일 앞에 두는 것이 더 차이의 합이 커진다 ex ] 3고르기 -> 0고르기 -> 5고르기 -> 1고르기 -> 4고르기..
백준 2252(줄 세우기) - Python(파이썬) - 위상정렬
백준 2252(줄 세우기) - Python(파이썬) - 위상정렬
2022.06.082252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상 정렬 설명 CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬) 참고 자료 : https://m.blog.naver.com/ndb796/221236874984 위상 정렬 : 순서가 정해져 있는 작업을 수행해야 할 때 그 순서를 정해주기 위해서 사용하는 알고리즘 ex ] 0번 -> 1번 ->3번 -> 5번 순으로 이어진.. coooco.tistory.com 💻 Python(..
CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬)
CHAPTER 6 -번외 정렬 - 위상 정렬(Topology Sort) - Python(파이썬)
2022.06.08참고 자료 : https://m.blog.naver.com/ndb796/221236874984 위상 정렬 : 순서가 정해져 있는 작업을 수행해야 할 때 그 순서를 정해주기 위해서 사용하는 알고리즘 ex ] 0번 -> 1번 ->3번 -> 5번 순으로 이어진 후에 4번이 나오기 전에 2번 만족 이런식으로 그래프의 흐름이 있고 다양한 조건들이 얽혀있을 때 일렬로 그래프의 순서를 나열할 수 있어야함 ex] 0 -> 1 -> 3 -> 5 -> 2 -> 4 -> 6 1. 위상 정렬의 특징 - 여러개의 답이 존재 할 수 있다 - DAG(Directed Acyclic Graph)에만 존재(방향그래프이지만 사이클이 존재하지 않는 그래프) -> 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. Why? 위상 정렬은 시..
백준 11000(강의실 배정) - Python(파이썬) - 그리디,정렬(heap, lambda,Comparator)
백준 11000(강의실 배정) - Python(파이썬) - 그리디,정렬(heap, lambda,Comparator)
2022.06.0811000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 1번 ->3번 -> 5번 순으로 이어진.. coooco.tistory.com 1 2 3 4 5 1-3 2-4 3-5 일단 1-3 ,2-4 ,3-5 을 처음 시작하는 시간으로 오..
백준 5430(AC) -Python(파이썬) - 자료구조
백준 5430(AC) -Python(파이썬) - 자료구조
2022.06.085430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 풀이 1. 일단 수행할 함수, 배열에 들었는 수의 개수, 배열에 들어있는 정수를 받아들인다. 2. 배열에 들어있는 정수는 항상 "["+배열에 들어 있는 정수+"]" 구조로 이루어졌다. "[]"을 제외한 값을 리스트로 받아들이기 위해서 인덱스 1부터 -1까지의 인덱스르 리스트로 받아들인다.[1:-1] 배열 "R" "D" "D" 4 1 3 2 1 2 3 2 1 1 4 3 2 이런 느낌으로 RDD 함수가 진행되면 [ 2,1 ]이 남는다. 📌 문제 풀면서 주의할점 1. 파이썬에서는 deque 라이브러리를 사용 2. re..
백준 10828(스택) - Python(파이썬),Java(자바) -자료구조,스택
백준 10828(스택) - Python(파이썬),Java(자바) -자료구조,스택
2022.06.0710828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 예제 설명 push 1 stack = [ 1 ] push 2 stack = [ 1,2 ] top stack = [ 1,2 ] 이므로 stack top = 2 출력 size stack = [ 1,2 ]이므로 size = 2 출력 empty stack = [ 1,2 ]이므로 empty가 아니므로 0 출력 pop stack = [ 1,2 ]이므로 pop이므로 2 출력 pop stack = [ 1 ]이므로 pop이므로 1 출력 pop stack = [ ..
백준 1158(요세푸스 문제) - Python(파이썬),Java(자바) - 자료구조(큐)
백준 1158(요세푸스 문제) - Python(파이썬),Java(자바) - 자료구조(큐)
2022.06.071158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 예제 설명 이걸 좀 해석하면 ① 제일 앞에 있는 값을 pop하고 뒤에다가 append한다 ② 그 과정을 두번 하고나서 ③ 세번째에는 pop하면서 나오는 값을 따로 큐에 저장한다. 이렇게 세 개의 과정을 한번 할때마다 하고서 큐에 사람 수만큼 채워지면 그만둔다. 풀이과정 ① 사람 수만큼 1번부터 사람수까지 번호를 부여한다. ② 제일 앞에 있는 값을 pop하고 다시 append에서 뒤로 붙이는 과정을 두번을 하므로 range(2)만큼 for문을 실행한다. ③ 세번째 pop하는 것은 visted 리스트에 붙인다. ④ ②,③번의 과정을 모두 큐에 저장할 때까지..
백준 1913(달팽이) - Python(파이썬) - 구현
백준 1913(달팽이) - Python(파이썬) - 구현
2022.06.061913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 예제 풀이 49 26 27 28 29 30 31 48 32 47 33 46 34 45 35 44 36 43 42 41 40 39 38 37 입력 받은 길이 7은 문자 n이라고 가정하고 이렇게 네부분으로 나눌 수 있다. ( i : x축( → ), j ( : y축( ↓ ) ) 1. 노란색 부분 : i 값은 일정 | j 값은 1씩 늘어남 | 49부터 시작해서 49 - 7(n) +1 = 43까지 줄어듬 2. 초록색 부분 : i 값은 1씩 늘어남 | j 값은 일정 | 43..
백준 20152(Game Addiction) - Python(파이썬) - 다이나믹
백준 20152(Game Addiction) - Python(파이썬) - 다이나믹
2022.06.0620152번: Game Addiction 첫째 줄에 집과 PC방의 좌표 (H, H), (N, N) 을 나타내는 두 정수 H, N (0 ≤ H, N ≤ 30) 이 차례로 주어진다. www.acmicpc.net 예제 설명 (8,8) -> (4,4) 를 가는 방법의 수는 (4,4) -> (8,8) 로 가는 방법의 수랑 동일하다. 이 방법의 수는 y>x인 곳은 침수되어서 갈 수 없다고 하였으므로 (4,5),(4,6),,, 이 모든 값은 0이라고 볼 수 있다. (4,4)의 점을 (0,0)이라고 가정하고, (8,8)의 점을 (4,4)라고 가정하고나서 표를 작성하면 다음과 같다 점화식 | if j>=i : dp[j][i] = dp[j-1][i] + dp[j][i-1] j \ i 4=0 5=1 6=2 7=3 8=4 4..
백준 1991(트리 순회) - Python(파이썬) - 트리,재귀
백준 1991(트리 순회) - Python(파이썬) - 트리,재귀
2022.06.031991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 설명 전위 순회의 경우 , 루트 -> 왼쪽 -> 오른쪽 중위 순회의 경우, 왼쪽 -> 루트 -> 오른쪽 후회 순회의 경우, 왼쪽 -> 오른쪽 -> 루트 tree[루트] = [ 왼쪽, 오른쪽 ] tree[A] = [ B,C ] tree[B] = [ D ] tree[C] = [ E,F ] tree[E] = [ . , . ] tree[F] = [ . , G ] tree[D] = [ . , . ] tree[G] = [ . , . ] Python에서는 t..
백준 19941(햄버거 분배 ) - Python(파이썬) - 그리디
백준 19941(햄버거 분배 ) - Python(파이썬) - 그리디
2022.06.0319941번: 햄버거 분배 기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 $K$ 이하인 햄버거를 먹을 수 있다. 햄버거 사람 햄버거 사람 햄버거 사 www.acmicpc.net 예제 설명 20 1 HHPHPPHHPPHPPPHPHPHP 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 H H P H P P H H P P H P P P H P H P H P 1. 2번의 사람 -> 1번 or 3번의 햄버거를 먹을 수 있지만 무조건 앞에 남은 햄버거 먹기 -> visted[1] =T visted ( 먹었는지 안 먹었는지 알려주는 배열 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
백준 2448(별 찍기) - Python(파이썬) - 재귀
백준 2448(별 찍기) - Python(파이썬) - 재귀
2022.06.032448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 문제 설명 내가 처음 생각한 풀이는 이와 같다 위와 같이 삼각혁의 꼭짓점의 좌표를 (startX,startY,높이) 라고 가정해본다. N=12 일 때의 삼각형은 연두색과 같이 세개로 나누어진다. ( 0, 0 6 ) , ( -6, 6, 6 ) ,( 6, 6, 6 )으로 이렇게 세개가 나누어진다. 이걸 처음 시작점 ( 0, 0, 12) 점이랑 연관되어서 생각해보면 ( 0, 0, 6 ), ( 0-6, 0+6, 6 ), ( 0+6, 0+6, 6) 이라고 할 수 있다. 또 N = 6일 때의 값을 각각 세개의 삼각형으로 나눌..
백준 14494(다이나믹이 뭐에요?) - Python(파이썬) - 다이나믹
백준 14494(다이나믹이 뭐에요?) - Python(파이썬) - 다이나믹
2022.06.02문제 설명 이런 원리로 (2,1)의 점 1, (3,1)의 점 1, (2,2)의 점 3이 세점을 더해서 5가 만들어지는 것이다. 즉 , 5 (3,2) = 1(2,1) + 1(3,1) + 3(2,2) 이걸 dp 그래프안에 넣었다고 가정해서 점화식으로 풀면 dp[m][n] = dp[m-1][n-1]+dp[m-1][n] + dp[m][n-1] 풀이 방법 ① m=1, n = 1인 지점은 모두 1이다. 갈 수 있는 방법은 무조건 일이다 1 1 1 1 1 1 1 ② 따라서 m의 값이 증가에 따라 for문 해서 1부터 n까지 루프문 돌린다. ③ 단, 수가 커지기 때문에 array값을 구할 때 마다 1,000,000,007 나눈 나머지 값을 구한다. Python(파이썬) import sys n,m = map(int,sy..
백준 1927(최소 힙) - Python(파이썬) - 자료구조
백준 1927(최소 힙) - Python(파이썬) - 자료구조
2022.06.01예제 설명 왼쪽 그림은 0,12645678,1,2 이 입력 | 오른쪽 그림은 0,0,0,0,32 이 입력되었을 때 힙안 숫자와 출력 되는 구조 Python(파이썬) import sys import heapq #연산의 개수 n = int(sys.stdin.readline()) heap=[] for i in range(n): #자연수 x 입력 받기 x=int(sys.stdin.readline()) #x가 0이 아닌 경우 if x!=0: #힙에 x를 입력 넣기 heapq.heappush(heap,x) #x가 0인 경우 else: #힙에 아무것도 없는 경우 if len(heap)!=0: #힙에서 가장 작은 값 출력 print(heapq.heappop(heap)) #힙에 값이 있는 경우 else: print(0)..