랜선 자르기(BOJ : 1654) 백준 1654번 : 랜선 자르기 본문 제한 시간 제한 메모리 제한 2초 128MB 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선..

나무 자르기(BOJ : 2805) 백준 2805번 : 나무 자르기 본문 제한 시간 제한 메모리 제한 1초 256MB 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높..

이진 탐색 이진 탐색(Binary Search)은 이분 탐색이라고도 하며, 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 이진 탐색 조건 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다. 이진 탐색 특징 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다. 이진 탐색 동작 과정 이진 탐색의 동작 과정은 다음과 같다. 데이터 리스트(arr)..

정렬 알고리즘 정렬이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘은 다양한 알고리즘이 존재하는데, 그 중 대표적인 정렬 알고리즘인 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬에 대해서 정리하고자 한다. 선택 정렬 선택 정렬 알고리즘은 리스트에서 매번 가장 작은 데이터를 선택하여 차근차근 정렬하는 방식의 알고리즘이다. 가장 작은 데이터를 선택하여 앞으로 보내는 과정을 반복하면 전체 데이터의 정렬이 이루어진다. 선택 정렬의 과정은 다음과 같다. 리스트의 길이(N)-1 만큼 다음 내용을 반복한다. 반복 횟수를 K라고 한다(0 = 0 && arr[a] > tmp) { // a 포인터의 값을 한 칸 다음으로 민다. arr[a + 1] = arr[a]; a--; } // b 포인..

DFS/BFS DFS와 BFS는 대표적인 그래프 탐색 알고리즘이다. DFS는 스택 자료구조 또는 재귀 함수를 통해 구현할 수 있고, BFS는 큐 자료구조를 통해 알고리즘을 구현할 수 있다. 그래프는 노드와 간선으로 표현되며 이때 노드를 정점이라고도 한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 ‘두 노드는 인접하다’라고 표현한다. 프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다. 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 메모리 측면에서 인접 행렬 방식은 모든 관계를 저장하므로 노드의 개수가 많을 수록 메모리가 불필요하게 낭비된다. ..

최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘 특징 최단 경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다는 특징이 있다. 또한 최단 경로 문제는 보통 그래프를 이용해서 표현하는데 각 지점은 그래프에서 노드로 표현되고, 지점 간 연결된 도로는 그래프에서 간선으로 표현된다. 최단 경로 알고리즘에는 다익스트라 알고리즘, 플로이드 워셜 알고리즘, 벨만 포드 알고리즘 등과 여러 알고리즘이 있다. 여기서는 다익스트라 알고리즘과 플로이드 워셜에 대해 알아본다. 다익스트라 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다..