[백준 / C++] 15903번: 카드 합체 놀이 (그리디, 우선순위 큐)

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 난이도: solved.ac 실버 1 알고리즘 분류 그리디 알고리즘, 우선순위 큐 접근 방법 점수를 최소로 하기 위해서는 매 선택마다 가장 작은 수를 가진 카드 두 장을 선택해야 한다. 따라서 가장 작은 수가 top에 오도록 하는 우선순위 큐를 이용한다. 우선순위 큐에서 가장 작은 수 2개를 뽑아서 합친 후 그 결과를 다시 우선순위 큐에 두 번 넣으면 된다. 그..

• format_list_bulleted PS/백준
• · 2023. 7. 29.
• textsms

[백준 / C++] 1051번: 숫자 정사각형 (브루트포스 알고리즘)

https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 난이도: solved.ac 실버 3 알고리즘 분류 구현, 브루트포스 알고리즘 접근 방법 모든 경우를 다 해보면 된다. N과 M 중 더 작은 값을 Max_len이라고 하면, 한 변의 길이가 1인 정사각형부터 한 변의 길이가 Max_len인 정사각형까지 변의 길이를 1씩 증가시켜 가며 정사각형을 찾아주면 된다. 정사각형의 네 꼭지점의 합이 가장 큰 정사각형을 찾아야 하는데 나는 왼쪽 위 꼭짓점을 기준..

• format_list_bulleted PS/백준
• · 2023. 7. 29.
• textsms

[백준 / C++] 11054번: 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 11053번을 풀었다면 아주 쉽게 풀 수 있는 문제다. https://jangkunstory.tistory.com/37 [백준] 11053번: 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를..

• format_list_bulleted PS/백준
• · 2023. 7. 28.
• textsms

[백준 / C++] 14002번: 가장 긴 증가하는 부분 수열 4 (dp)

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 난이도: solved.ac 골드 4 접근 방법 일반적인 dp를 이용한 N^2짜리 LIS 풀이로 가장 긴 부분 수열의 길이를 구하고 추가적인 코드를 통해 O(N)에 경로를 추적할 수 있다. 일단 LIS의 길이를 구하는 for문을 마치고 나면 len[i]에는 A[i]를 부분 수열의 마지막 원소로 썼을 때의 LIS 길이가..

• format_list_bulleted PS/백준
• · 2023. 7. 27.
• textsms

[백준 / C++] 2638번: 치즈 (BFS, 구현)

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 난이도: solved.ac 골드 3 알고리즘 분류 구현, 그래프 탐색 (BFS) 접근 방법 및 구현 DFS로도 풀리겠지만 나는 BFS로 풀었다. 이 문제에서 핵심은 외부 공기와 내부 공기다. 내부 공기(구멍)는 공기로 취급 안 해서 닿아있는 공기의 개수에 포함하지 않는다. 외부 공기와 내부 공기를 파악하기 위해 우선 0인 곳을 찾아주었다. 하나의 visited 배열을 공기를 탐색하는데..

• format_list_bulleted PS/백준
• · 2023. 7. 27.
• textsms

[백준 / C++] 15686번: 치킨 배달 (삼성 SW 역량테스트 기출)

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 구현, 브루트포스 알고리즘, 백트래킹 접근 방법 입력으로 받은 치킨집에서 M개를 고르는 모든 경우의 수를 다 따져보며 치킨 거리를 구한다. 구현 c++의 STL에 있는 next_permutation을 이용해 치킨집 중 M개를 고르는 조합을 만든다. 입력으로 들어오는 치킨집의 개수가 x개라고 하면, x개의 원소 중 M개가 1, ..

• format_list_bulleted PS/백준
• · 2023. 7. 26.
• textsms