알고리즘

저번 시간에 배운 동적 프로그래밍 관련 문제를 하나 풀어보겠습니다! 문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 사용한 알고리즘 - 동적 프로그래밍(dp) 아이디어 - 보석을 하나하나 추가했을 때의 배낭 무게별 최대가치를 계산 ex) 가방 최대 무게 : 7 보석 보석 번호 무게 가치 0 6 13 1 4 8 2 3 6 3 5 12 이 때, 보석을 0번~3번 까지 하나하나 넣으면서 계산해 봅시다! 표의 값은 배낭 무게별 최대 가치입니다! 0..

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net - 퍼즐 / 골드2 / 82분 생각해보아야 할 것 1. 어떤 수를 옮겨야 하는가? - 0을 기준으로 상하좌우에 있는 수를 옮김 - 이 때, 바꾼 수와 기존의 수를 스와핑 nx ,ny = x+dx,y+dy if 0

정렬이란? 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬을 통하여 이진 탐색(Binary Search) 가능 정렬 알고리즘 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 선택 정렬(Selection Sort) 선택 정렬 가장 작은 데이터를 선택해 맨 앞의 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 시간 복잡도 - O(n^2) 코드 arr = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_idx = i if arr[min_idx] > arr[i]: min_idx= i arr[i], arr[min_idx] = arr[min_idx], arr[i] print(arr) 삽입 정렬(Insertion So..

탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룸 대표적인 알고리즘 - DFS(깊이우선 탐색),BFS(너비우선 탐색) 자료구조란? 데이터를 표현하고 관리하고 처리하기 위한 구조 대표적인 자료구조인 스택과 큐는 다음 두 핵심 함수로 구성됨 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 스택(Stack) FILO, LIFO 구조 append() : 리스트의 가장 뒤쪽에 데이터 삽입 pop() : 리스트의 가장 뒤쪽에서 데이터 꺼냄 큐(Queue) FIFO 구조 collections 모듈에서 제공하는 deque 자료구조 활용 append() : 데큐의 가장 뒤쪽에 데이터 삽입 popleft() : 데큐의 가..

# 그리디 개념 그리디(greedy) : 탐욕 ## 현재 상황에서 가장 좋은것만 고르는 것 - 매 순간 가장 좋아 보이는 것 선택 ex) 거스름돈 - 가장 큰 화폐단위부터 거스르기 ## 해당 해법이 정당한지 검토 ex) 거스름돈 - 큰 단위의 동전은 작은 단위의 배수이므로 다른 해가 나올 수 없음 ### 체크리스트 - [X] 현재 상황에서 가장 좋은 것만 고르는가? - [X] 해당 해법이 정당한가? 출처 HTML 삽입 미리보기할 수 없는 소스