이번 포스팅은 오랜만에 알고리즘 관련임 음하하 교재의 예제들과 함께 백준의 #1463 문제를 풀면서 오랜만에 문제 풀이 포스팅을 적으려다가 어쩌다보니 방향이 바뀌어버려서 글 흐름이 조금 이상할 수도 있는데 결과적으로는 다이나믹 프로그래밍이라는 알고리즘에 대해 내가 이해한 것을 정리한 개념 설명 글 입니다 . . . 나름 열심히 적어보았어요 당연한 내용들일 수도 있는데 DP 유형을 처음 접하는 사람이라면 도움이 될지도? https://www.acmicpc.net/problem/1463 1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net 우선 DP 문제에 대한 경험이 없는 사람이 이 문제를 처음 보게 된다면 이게 왜 다이나믹 프로그래..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 다이나믹 프로그래밍 문제를 풀다보니 문제를 보자마자 Bottom-up 방식으로 접근했는데, 다른 풀이들을 찾아보니 꼭 다이나믹 프로그래밍을 사용하지 않아도 된다는 걸 깨달았다. 알고리즘 분류를 확인해보니 이렇기에 너무 문제 푸는거에 집중하다보니 실제 코테에서는 문제를 보고 어떤 방식으로 접근해야 하는지부터 나 스스로 생각해내야 하는데, 내가 지금 공부하는 부분이니까 당연히 그 방식으로 접근하고 있는(+예제 ..

그래프 탐색 알고리즘 이해하기그래프: 여러 개체들이 연결되어 있는 자료구조탐색: 특정 개체를 찾기 위한 알고리즘 DFS, BFS를 드라마를 볼 때로 비유하자면드라마 한 개를 끝나길 기다렸다가 몰아본다 = DFS (깊이 우선 탐색)드라마 여러 개를 하나씩 다 챙겨본다 = BFS (너비 우선 탐색) 대표적 문제 유형 1. 경로 탐색 유형 A 지점부터 B 지점까지의 최소 거리 구하기, 최단 시간 구하기 2. 네트워크 유형 여러 개체들이 주어진 상태에서 연결되어 있는 그룹의 개수 구하기, 두 개체가 같은 네트워크 안에서 연결되어 있는지 확인하기 3. 조합 유형 여러 가지의 조합을 전부 만들고 비교해보기 프로그래머스의 타겟 넘버, 네트워크, 단어 변환, 여행경로 등의 문제를 보고 DFS/BFS 를 떠올렸다면? =..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net DFS/BFS 유형 문제 중에 가장 기초적인 문제이다. 이론을 이해하고 났다면 금방 풀 수 있는 문제지만 혹시나 알고리즘 공부가 아예 처음이거나, 문제에 적용하려고 하니 낯선 분들을 위해 베이스로 알면 좋은(?) 개념을 조금 정리해보았다. 덱(deque) 사용법 - 초기화 deque(iterable, [, maxlen])를 사용해 초기화 from collect..