BAEKJOON #1916) 최소비용 구하기 | Python 다익스트라 최단 경로 알고리즘을 구현하는 기본적인 문제입니다. 아래 글에서 자세한 설명을 보실 수 있습니다:) 🚗 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 어떤 한 지점에서 다른 한 지점까지의 최단 경로를 찾아야 하는 문제의 경우, 각 지점은 그래프의 노드로, 지점 간 거리 eunbin00.tistory.com # boj_1916.py # https://www.acmicpc.net/problem/1916 import sys import heapq INF = int(1e9) n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) distance =[INF] * (n + 1) graph = [[].. 🚗 다익스트라 최단 경로 알고리즘 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 어떤 한 지점에서 다른 한 지점까지의 최단 경로를 찾아야 하는 문제의 경우, 각 지점은 그래프의 노드로, 지점 간 거리는 간선의 가중치로 표현됩니다. 즉, 아래 그림과 같은 각 간선이 가중치를 갖는 유향 그래프로 표현됩니다. 🚗 최단 경로 두 정점 사이의 최단 경로의 길이는 가중치들의 합 중에서 가장 작은 값을 가지는 경로이다. 만약 어떤 두 정점 사이의 최단 경로가 없다면 이때의 거리는 무한대($\infty$)라고 가정합니다. 그렇다면 최단 경로를 어떻게 찾을 수 있을까요? 단순하게는 모든 경로에 대한 거리를 계산해보고 가장 짧은 경로를 선택하면 됩니다. 하지만 이 방법은$n$개의 정점이 있을 때, $(n-2)!$개의 경로의 거리를.. BAEKJOON #1655) 가운데를 말해요(Python) 숫자를 입력받을 때마다 중앙값(숫자의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수)을 찾아서 출력하는 문제이다. 처음에는 숫자를 입력받을 때마다 배열에 넣고 정렬하여 홀수면 n/2번째 인덱스를, 짝수면 (n-1)/2번째 인덱스를 출력하면 된다고 생각하여 정렬 알고리즘을 구현하여 제출했다. 뚜둥-! 퀵소트로 정렬하면 시간 초과가 나고, 병합정렬(merge sort)을 이용하면 메모리 초과가 난다😇 정렬 알고리즘을 이용하여 풀 수는 없다. 조금 찾아보니 힙을 사용하여 중앙값을 찾는 방법을 이용하면 된다고 한다. Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap .. BAEKJOON #11279) 최대 힙 (Python) 1927번과 마찬가지로 힙을 구현만 하면 해결되는 문제이지만, 파이썬에는 이미 구현되어있는 heapq 라이브러리가 있기 때문에, 함수(heapq.heappush(heap, value), heapq.heappop(value))를 사용만 해준다. import heapq from sys import stdin n = int(stdin.readline()) heap = list() for _ in range(n): input_num = int(stdin.readline()) if input_num == 0: if heap: print(heapq.heappop(heap)[1]) else: print(0) else: heapq.heappush(heap, [-input_num, input_num]) 다만, heapq.. BAEKJOON #1927) 최소 힙 (Python) 문제 이름처럼 힙을 구현만 하는 되는 문제라서, 힙을 구현해야겠다고 생각했는데, 파이썬에는 이미 힙을 만들 수 있는 라이브러리가 있었다. 역시 파이썬..,.👍 heapq라는 라이브러리를 import하여 문제가 요구하는대로 사용해주면 끝이다. 📌 힙(heap)이란? Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Com eunbin00.tistory.com 📌 정답 코드(Python) import heapq from sys import stdin n = int(stdin.readline()) .. BAEKJOON #11718) 그대로 출력하기| C, Python 백준 11718번: 그대로 출력하기 입력받은 대로 그대로 출력하면 되는 문제이다. 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net C #include intmain(void) { char a; while (scanf("%c", &a) != -1) printf("%c", a); return 0; } char형 변수를 선언하고 character 하나하나 입력받는다. scanf 함수에서 에러가 나지 않는 이상 계속 받은 char를 출력한다. Python while True: try: print(in.. BAEKJOON #9663) N-QUEEN (C) 알고리즘 분류: 브루트포스 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 백준 9663) N-Queen 알고리즘 분류: 브루트포스 #include #include int is_valid(int idx, int val, int *puzzle) { int i = 0; while (i < idx) { if (puzzle[i] == val) { return (0); } if (val - puzzle[i] == idx - i || val - puzzle[i] == i - idx) { return (0); } i++; } return.. BAEKJOON #1463) 1로 만들기 | 다이나믹 프로그래밍 | python 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 📌 다이나믹 프로그래밍 [Algorithm] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자 💡 다이나믹 프로그래밍 (Dynamic Programming, DP) 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 그런데 어떤 문제는 메모리 공간을 약간만 더 사용 eunbin00.tistory.com 1이 될 때까지 주어진 연산을 최소로 사용하는 '1로 만들기' 문제는 다이나믹 프로그래밍 알고리즘을 활용하는 대표적인 유형이다. 이 문제가 다이나믹 프로그래밍 알고리즘을 사용하여 풀 수.. [Algorithm 완전 정복] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자 GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소 github.com 💡 다이나믹 프로그래밍 (Dynamic Programming, DP) 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 그런데 어떤 문제는 메모리 공간을 약간만 더 사용하면 연산 속도를 매우 빠르게 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이.. BAEKJOON #12865) 평범한 배낭🎒 | knapsack | dynamic programming 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🎒 백준 12865번 평범한 배낭 문제는 다이나믹 프로그래밍의 대표적인 문제 유형인 knapsack(배낭) 문제이다. [Algorithm] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자 💡 다이나믹 프로그래밍 (Dynamic Programming, DP) 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.. BAEKJOON #1026) 보물 알고리즘 분류: 그리디 알고리즘 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 💡 풀이 n = int(input()) lst_a = list(map(int, input().split())) lst_b = list(map(int, input().split())) lst_a.sort() lst_b.sort(reverse=True) result = 0 for a, b in zip(lst_a, lst_b): result += a*b print(result) 가장 작은 S를 만드는 방법은 큰 B의 원소가 크면.. BAEKJOON #2231) 분해합 (python) 알고리즘 분류: 브루트 포스 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 💡 풀이 n = int(input()) result = 0 for i in range(1, n + 1): a = list(map(int, str(i))) s = i + sum(a) if (s == n): result = i break print(result) 이전 1 2 3 4 5 6 7 8 다음
