본문 바로가기

전체207

[백준 1238번] 파티 난이도: 골드 3 문제 링크: www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 최단 경로 문제를 공부한 후 연습 삼아 풀어본 문제입니다 (블로그 글 링크). 1 ≤ N ≤ 1,000, 1 ≤ M ≤ 10,000으로, 입력되는 데이터의 양이 아주 많은 편은 아닙니다. 하지만 문제를 자세히 보면, 최단 경로를 총 N번 찾아야 합니다. c번 도시를 제외한 다른 도시들로부터 c번 도시로 갈 때 총 N-1번, c번 도시에서 다른 도시로 .. 2021. 2. 11.
최단 경로 최단 경로 알고리즘은 말 그대로, 출발지와 도착지 사이의 가장 짧은 경로를 찾는 알고리즘입니다. 다른 말로는 '길 찾기' 문제라고도 합니다. 보통 이런 문제들은 그래프 자료구조를 이용해 표현되는데, 출발지와 도착지, 그리고 그 외 중간 지점은 노드, 각 지점 사이의 경로와 거리는 엣지로 표현됩니다. 문제의 유형도 다양한데, '특정 지점 A에서 특정 지점 B까지의 최단 경로를 구하기', '모든 지점에서 다른 모든 지점까지의 최단 경로를 구하기' 등이 있으며, 이에 맞는 알고리즘을 알고 있다면 문제를 조금 더 수월하게 풀 수 있습니다. 실제 코딩 테스트에서는 최단 경로를 모두 출력하기보다는, 최단 거리만을 출력하는 문제가 많이 출제된다고 합니다. 대표적인 알고리즘은 다음과 같습니다: 다익스트라 (Dijkst.. 2021. 2. 9.
[백준 12865번] 평범한 배낭 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 오늘 공부한 다이나믹 프로그래밍을 응용해 보기 위해 풀어 본 문제입니다. 얼핏 보면 간단해 보이지만, 두 개의 변수 W와 V를 고려해야 해서 쉽지 않습니다. 제가 예전에 풀었던 최소 편집 거리 문제와 비슷하다는 느낌을 받았습니다. 나름 유명한 문제인데, Google 등에 knapsack 문제라고 검색해 보시면 이 문.. 2021. 2. 6.
다이나믹 프로그래밍 프로그래밍은 대개 현실 세계의 문제를 전산적으로 접근하여 풀기 위하여 사용됩니다. 그 중 어떤 문제들은, 컴퓨터를 사용해도 매우 오래 걸리거나 해결하기 어렵기도 합니다. 컴퓨터 역시 현실 세계의 물건인 만큼, 저장 공간이나 연산 속도에 한계가 존재하며, 이러한 한계가 걸림돌이 되는 경우가 분명히 존재합니다. 만약 어떤 알고리즘이 O(2^N)의 시간 복잡도를 가진다면, N의 크기가 커질수록 처리 속도가 비약적으로 증가할 것입니다. 하지만, 메모리를 조금 더 사용하여 같은 문제를 O(N)의 시간 복잡도로 해결할 수 있다면, 이는 매우 효율적인 방법이 될 수 있습니다. 다이나믹 프로그래밍 (dynamic programming) 은 이렇게 연산 속도를 대폭 줄일 수 있는 대표적인 방법입니다. 다이나믹 프로그래밍.. 2021. 2. 5.
이진 탐색 탐색이라 함은, 데이터의 집합 중에서 원하는 값을 찾는 것을 의미합니다. 오늘 다루어 볼 내용은 이진 탐색 (binary serach)인데, 이에 앞서 가장 기본적인 탐색 방법인 순차 탐색을 다루고자 합니다. 순차 탐색 순차 탐색 (sequential search)는 배열 내의 특정 데이터를 찾기 위해 앞에서부터 순차적으로 확인하는 방법입니다. 정렬되지 않은 배열에서 데이터를 찾을 때, 시간만 충분하다면 순차 탐색이 좋은 방법이 될 수 있습니다. 'Carrot' 이라는 문자열을 찾는 과정입니다. 파란색은 현재 'Carrot'와 비교하는 문자열, 빨간색은 이미 비교하였으며 일치하지 않은 문자열, 초록색은 목표로 하는 문자열입니다. 첫 번째 문자열 'Apple', 두 번째 문자열 'Banana'는 일치하지 .. 2021. 2. 4.
정렬 정렬은 컴퓨터과학 분야에서 광범위하게 사용되는 개념입니다. 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 의미하는데, 오름차순, 내림차순, 등등 상황에 따른 여러 특정한 기준이 존재합니다. 다양한 정렬 알고리즘이 존재하며, 각각 장점과 단점을 가지고 있습니다. 이 중 상황에 맞는 효율적인 알고리즘을 고르는 것이 중요합니다. 다음과 같은 숫자가 있다고 생각합시다: 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 우리는 위 숫자들을 오름차순으로 정렬하고 싶습니다. 어떻게 진행할까요? 전체 숫자를 슥 보고, 숫자들이 0~9 사이의 숫자들임을 파악한 후, 0부터 차례대로 나열할 것입니다. 하지만 컴퓨터가 정렬을 할 때도 이런 방법이 효율적일까요? 또, 데이터가 수백, 수천만 개가 있다면 이런 방법이 .. 2021. 2. 4.

티스토리툴바