알고리즘

정렬 알고리즘은 값들을 특정 조건에 따라 정렬하기 위해 사용되는 알고리즘이다. ex) 오름차순, 내림차순 대부분의 언어들에서는 원소들을 정렬하는 내장함수들이 존재하기 때문에 자연스럽게 그 함수들을 사용하지만, 당연히 이 과정은 자동으로 이루어지는 것이 아니라 내부적으로는 일련의 과정들을 거친다. 선택 정렬 알고리즘 선택 정렬 알고리즘은 수 많은 정렬 알고리즘 중 하나이다. 선택 정렬 알고리즘의 아이디어는 그림과 같이, 첫 번째 값부터 맨 마지막 값까지 쭉 돌면서 가장 작은 값들을 하나씩 배열의 맨 앞으로 가져오는 것이다. 파이썬을 통해 구현한 선택 정렬은 다음과 같다. arr = [5, 10, 9, 33, 21, 7, 2, 3, 0] # 정렬되지 않은 array for i in range(len(arr)..

문제 (링크) https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 나의 풀이 from collections import deque n, m = map(int, input().split()) graph = [] # 상 하 좌 우 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] for _ in range(n): graph.append(list(map(int, input()))) def bfs(x, y): queue = deque() queue.append((x, ..

문제 (링크) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 나의 풀이 from collections import deque n, m, v = map(int, input().split()) matrix = [[0] * (n+1) for _ in range(n+1)] visited = [False] * (n+1) for _ in range(m): a, b = map(int, input().split()) m..

문제 (링크) https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 나의 풀이 from itertools import combinations n, m = map(int, input().split()) items = list(map(int, input().split())) comb = list(combinations(items, 3)) # combinations를 이용해 나열 가능한 조합 만들기 sum_value = [..

문제 (링크) https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 나의 풀이 n = int(input()) s = [] # 스택 for _ in range(n): x = int(input()) if x != 0: s.append(x) else: s.pop() print(sum(s)) 문제에 나오는대로 append와 pop만 사용하면 되는 문제

문제 (링크) https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 나의 풀이 n = int(input()) data = list(map(int, input().split())) data.sort() # 걸리는 시간을 오름차순으로 정렬했을 때 최솟값이 나온다 waiting_time = [] for i in range(n): waiting_time.append(sum(data[:i+1])) # 걸리는 시간을 인덱싱한 후 sum한 값을 waiting_time에 추가 print(sum..

문제 (링크) https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 나의 풀이 n = int(input()) def change(n): count = 0 while n % 5 != 0: n -= 2 count += 1 if n < 0: return -1 count += (n // 5) return count print(change(n)) 바로 직전의 설탕 배달 문제와 동일한 문제로, n이 5로 나누어떨어질 때까지 2를 빼주면서 count를 1씩 추가해주고, n이 0보다 작아지면 -1을 리턴하며 함수를 끝내준다. 혹은 n에서 2씩 빼주는 과정에서 5로 나누어떨어지는 값이..

문제 (링크) https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 나의 풀이 n = int(input()) result = 0 while n % 5 != 0: # n -= 3 if n < 0: result = -1 break result += 1 result += (n // 5) # n < 0일 때도 이 코드를 거쳐가서 오류 발생. print(result) n이 5의 배수가 될때까지 (while n%5 != 0) n에서 3을 빼주고 봉지 개수를 +1 해준다...