본문 바로가기

백준46

[백준 12100번] 2048 (easy) 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/12100 출처: 삼성 SW역량 테스트 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 설명이 긴 편이므로, 위 링크에서 직접 읽어 보시는 것을 추천드립니다. 잘 알려진 2048이라는 게임을 부분적으로 구현한 후, 최대 5번 움직을 때 얻을 수 있는 가장 큰 값을 출력하는 문제입니다. '움직임' 이라고 함은 상하좌우 네 방향으로 숫자들을 이동시키는 것을 말하며, 이 때 이동하는 방향 중 값이 같고 아직 합.. 2021. 3. 24.
[백준 15401번] 퇴사 난이도: 실버 4 문제 링크: www.acmicpc.net/problem/14501 출처: 삼성전자 SW 역량 테스트 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 다이나믹 프로그래밍을 이용하는 문제입니다. 지금까지 누적 얻은 이익을 매번 다시 계산하지 않고, 이전에 계산해서 저장해 놨던 값을 꺼내어 이용하면 됩니다. 이런 문제는 뒤에서부터 접근하면 보다 쉽게 풀 수 있습니다. 위 사진에 있는 예시를 기준으로 설명하겠습니다. N+1일 후에 퇴사를 합니다. 따라서 N일까지 일할 수 있는지 여부를 우선 체크해야 합니다. 주의할 점은 7일차에 하루가 걸리는 상담을 할 경우 7 + 1 = 8이지만, 상담을 할 수 있다는 점입니다. 따라서 x일차 + y일.. 2021. 3. 11.
[백준 2110번] 공유기 설치 난이도: 실버 1 문제 링크: www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이분 탐색을 이용하는 문제 중 꽤 애를 먹은 문제입니다. 어느 부분에서 이분 탐색을 이용해야 하는지 고민을 많이 했는데, 다른 블로그 (링크)의 글을 참고하여 알고리즘을 이해했습니다. 문제의 접근 순서는 다음과 같습니다. 주어진 집들의 좌표를 오름차순으로 정렬한다 (이분 탐색의 기본 조건). 집들 사이의 거리를 초기화한다. 최솟값.. 2021. 3. 8.
[백준 1647번] 도시 분할 계획 난이도: 골드 4 문제 링크: www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 기본적인 크루스칼 알고리즘을 사용하고, 약간의 아이디어를 내서 최소 신장 트리를 두 개로 분할하는 문제입니다. 크루스칼 알고리즘에 대한 자세한 내용은 그래프 이론 글의 크루스칼 알고리즘 파트를 참고해 주세요. 최소 신장 트리에 대해 다시 복습해 봅시다. 모든 노드가 연결되어 있으며, 그 연결된 값의 총합이 최소가 될 때 최소 신장 트리라고 부릅.. 2021. 2. 13.
[백준 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.
[백준 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.

티스토리툴바