[백준 / C++] 4179번: 불!

https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 그래프 탐색 (BFS) 접근 방법 J가 F와 동시에 같은 지점으로 이동하면 불에 타 죽는다. 따라서 먼저 F를 이동시킨 후 J를 이동시키는 방법으로 진행했다. 다른 분들은 BFS를 두 번 돌리던데, 하나의 BFS 큐에 J와 F를 넣어서 BFS를 한 번만 돌려도 이 문제를 풀 수 있다. (이렇게 하면 메모리나 시간을 훨씬 단축시킬 수..

• format_list_bulleted PS/백준
• · 2023. 8. 3.
• textsms

[백준 / C++] 14500번: 테트로미노 (삼성 SW 역량테스트 기출)

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 난이도: solved.ac 골드 4 알고리즘 분류 구현, 브루트포스 알고리즘 접근 방법 및 구현 ㅗ 모양을 제외한 나머지 모양은 한 지점에서 depth = 4짜리 DFS를 돌리면 구현 가능하다. 신경 써야 할 것은 ㅗ 모양인데, 나는 ㅗ에서 가운데 부분을 기준으로 잡고 상하좌우에서 3개를 골라 그 부분들의 합을 함께 더해주는 식으로 구현했다. 상하좌우에서 3개를 고르는 건 DFS에서 사용한 dy[..

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

[백준 / C++] 2565번: 전깃줄 (LIS 응용)

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 난이도: solved.ac 골드 5 알고리즘 분류 다이나믹 프로그래밍, LIS 접근 방법 전깃줄이 겹치지 않으려면 A 전봇대에서 이어지는 B 전봇대의 번호가 오름차순이어야 한다. 따라서 자르는 전깃줄의 개수를 최소화하려면 LIS를 찾아야 한다. 가장 긴 증가하는 부분 수열만을 남기고 나머지는 다 잘라버려야 한다. 구현 LIS 알고리즘 사용해서 (11053번 포스팅 코드 참고) 가장 긴 수열의 길이를 구하..

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

[백준 / 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