본문 바로가기
반응형

알고리즘 문제 풀이66

[백준 9465] 스티커 문제 출처 : https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 간단한 DP 문제 입니다. DP에 대해 잘 모른다면 어렵게 느껴질 수 있습니다. 스티커의 품질이 좋지 않기 때문에 어떤 스티커를 떼면 그 스티커의 상, 하, 좌, 우에 있는 스티커는 사용할 수 없습니다. 따라서 왼쪽부터 첫 번째 줄의 스티커를 떼었을 때, 두 번째 줄의 스티커를 떼었을 때, 아무것도 떼지 않았을 때, 이렇게 세가지의 경우를 생각해서 문제를 해결해야 합니다... 2023. 10. 5.
[백준 1976] 여행 가자 문제 출처 : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 여행을 갈 수 있는지, 없는지 확인하는 문제 입니다. 문제를 보면 쉽게 도시들을 DFS를 통해 방문이 가능한지 불가능한지 따지면 해결될 것으로 보입니다. 하지만 이렇게 문제를 풀게 되면 시간초과가 발생할 수 있습니다. 왜냐하면 의도적으로 끝에서 끝으로 이동하는 경로만 입력이 들어온다면 방문하는데 시간이 오래걸릴 수 있습니다. 따라서 이 문제는 DFS가 아니라 유니온 파인드, 즉 분리.. 2023. 10. 4.
[백준 15686] 치킨 배달 문제 출처 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 치킨을 배달할 수 있는 치킨 거리가 가장 짧아지는 경우를 구하는 문제 입니다. 여기서 거리를 구하는 방식은 맨하탄 거리(Manhattan Distance)를 구하는 공식 입니다. 좌표간의 거리를 구하는 방식 중 하나로 간단한 계산으로 거리를 구할 수 있습니다. 알고리즘 지도의 크기 N의 최대는 50이고 치킨 집의 개수의 최대는 13입니다. 이정도의 크기라면 브루.. 2023. 9. 27.
[백준 12015] 가장 긴 증가하는 부분 수열 2 문제 출처 : https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net LIS(Longest Inceasing Sequence)란? LIS는 Longest Increasing Subsequence의 약자로 최장 증가 수열 또는 최장 증가 부분수열이라고 합니다. LIS를 이해하기 위해서는 먼저 Increasing Subsequence 한글로 증가 부분수열을 알아야 합니다. 증가 부분수열을 말 그대로 증가하고 있는 부분 수열을 나타냅니다. 가령 [5, 1,.. 2023. 9. 20.
[백준 1725] 히스토그램(세그먼트 트리) 문제 출처 : https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 히스토그램은 다양한 풀이 방법으로 유명한 문제 입니다. 스택, 분할정복, 세그먼트 트리로 풀 수 있습니다. 여기서는 세그먼트 트리의 다양한 응용에 대해 배우기 위해 세그먼트 트리로 푸는 방법을 알아보겠습니다. 문제 이해하기 문제 풀이를 위한 개념은 이렇습니다. 아래와 같은 히스토그램이 있습니다. 처음부터 끝까지를 모두 포함하는 직사각형은 가장 낮은 높.. 2023. 9. 18.
[백준 28325] 2023 정올 "호숫가의 개미굴" 문제 출처 : https://www.acmicpc.net/problem/28325 28325번: 호숫가의 개미굴 KOI 호숫가에 여러 개미가 모여 사는 개미굴이 있다. 개미굴은 둥근 호수의 둘레를 따라 $1$부터 $N$까지의 번호가 붙은 $N$개의 방이 차례대로 원형으로 배치되어 있으며, 모든 $i$ ($1 \le i \le N-1$)에 www.acmicpc.net 이 문제는 2023년 정보올림피아드 2차 대회 초등부 3번, 중등부 2번 문제입니다. 이 문제를 풀기 위해서 생각해야 하는 부분을 알아보겠습니다. 쪽방 사용 개미굴에 쪽방이 있다면 쪽방을 이용하는 것이 최선 입니다. 그림과 같이 여러 개미굴이 있는 곳의 일부를 보도록 하겠습니다. 2번 개미굴에 쪽방이 하나 연결되어 있습니다. 쪽방인 4번을 선.. 2023. 9. 15.
[백준 1517] 버블 소트(merge sort로 풀기) 문제 출처 : https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 이 문제의 이름은 버블 소트이지만 버블 소트로 문제를 풀려고 한다면 시간초과로 문제를 해결할 수 없습니다. 이 문제는 앞에서 배운 Inversion Counting 으로 해결할 수 있습니다. 앞에서 세그먼트 트리로 푸는 방법을 배웠다면 이번에는 merge sort를 사용하여 문제를 풀어보도록 하겠습니다. 세그먼트 트리의 문제점 세그먼트 트리로 풀 수 있지만 머.. 2023. 9. 13.
[백준 2579] 06 정올 초등부 "계단 오르기" 문제 출처 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 이 문제는 2006년 정보올림피아드 시. 도 지역 본선 초등부 4번 문제 입니다. 지금으로 따지면 1차 대회에서 초등부 가장 어려운 문제 였습니다. 지금이라면 2~3번 수준의 문제이지 않나 생각합니다. 시간이 흐르면 흐를수록 문제가 어려워지고 있는것 같습니다. 계단을 오르는 규칙을 지키면서 얻을 수 있는 점수의 최댓값을 구하는 문제 입니다. 이런 유형의 문제는 다이나믹 프로그래밍(DP)로 해결할.. 2023. 9. 6.
[백준 14428] 수열과 쿼리 16 문제 출처 : https://www.acmicpc.net/problem/14428 14428번: 수열과 쿼리 16 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값의 인 www.acmicpc.net 세그먼트 트리를 조금 응용한 문제 입니다. 기존에는 리스트의 값을 출력 하였다면 이 문제에서는 해당 인덱스를 출력하는 문제 입니다. 이처럼 세그먼트 트리를 어떤 값을 찾는 것이 아니라 보조적인 수단으로 사용하는 문제가 많이 출제되니 이런 케이스의 문제를 많이 풀어봐야 합니다. 이 문제를 푸는 방법은 .. 2023. 9. 5.
반응형

티스토리툴바