본문 바로가기
반응형

알고리즘 풀이/백준125

[백준 17136] 색종이 붙이기 (python) https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 색종이 붙이기 문제 10x10 종이 위에 색종이들을 붙일 때 필요한 최소 개수를 구하는 문제 #사용 알고리즘 백트래킹(Backtracking) 📌문제 접근 포인트 1. 기본적으로 1x1, 2x2, 3x3, 4x4, 5x5의 색종이 5개씩 주어지므로 리스트에 5개씩 할당해 주자. 이때, 최대 결과값은 색종이를 모두 사용하는 25이므로 결과값의 최대치는 26만 잡아도 충분하다. 2. 반복 탐.. 2024. 3. 27.
[백준 14267] 회사 문화1 (python) https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 회사 문화1 문제 상사로부터 부하로 칭찬을 내리 칭찬할 경우 받는 칭찬의 수를 구하는 문제 #사용 알고리즘 다이나믹 프로그래밍 📌문제 접근 포인트 1. 상사가 받는 칭찬은 본인 보다 부하인 직급에 모두 더해진다. 그러므로 받은 칭찬을 우선적으로 구하고, 해당 상사의 부하들에 대해 칭찬 수를 증가해주면 된다. 2. 칭찬 포인트(good)를 만들어서 각 상사에 매칭되는 최초 칭찬 값을 넣어주자. 3.. 2024. 3. 13.
[백준 2644] 촌수계산(python) https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 촌수계산 문제 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 문제 #사용 알고리즘 너비 우선 탐색(BFS) 📌문제 접근 포인트 1. 촌수 계산을 하는 문제. 즉, 촌수는 한칸 넘어갈 때마다 해당 위치에서 촌수가 +1씩 증가한다. 2. 1씩 증가하는 탐색 방법 중 가장 보편적인 방법인 BFS를 구현하면 된다. 일반 기본 BFS 구현 문제들과 풀이 방식이.. 2023. 11. 21.
[백준 16435] 스네이크버드 (python) https://www.acmicpc.net/problem/16435 16435번: 스네이크버드 첫 번째 줄에 과일의 개수 N (1 ≤ N ≤ 1,000) 과 스네이크버드의 초기 길이 정수 L (1 ≤ L ≤ 10,000) 이 주어집니다. 두 번째 줄에는 정수 h1, h2, ..., hN (1 ≤ hi ≤ 10,000) 이 주어집니다. www.acmicpc.net 스네이크버드 문제 스네이크버드가 자기보다 길거나 같은 높이에 있는 과일을 먹을 때 최대 길이 구하는 문제 #사용 알고리즘 그리디 정렬 📌문제 접근 포인트 1. 스네이크버드는 자신의 길이보다 길거나 같은 과일을 먹을 수 있고, 먹을 때마다 1씩 증가한다. 여기서 과일의 위치와 상관없이 사이즈에 해당하는 크기가 존재한다면 먹을 수 있다. 2. 오름차.. 2023. 10. 2.
[백준 14433] 한조 대기 중(python) https://www.acmicpc.net/problem/14433 14433번: 한조 대기 중 첫째 줄에 한 팀에 속한 플레이어의 수 N(1 ≤ N ≤ 300)과 트롤픽의 수 M(1 ≤ M ≤ 300), 각 팀의 팀원들이 원하는 트롤픽의 수 K1, K2(1 ≤ K1, K2 ≤ 500)가 주어진다. 다음 K1개의 줄에 걸쳐 두 수 i, j(1 ≤ www.acmicpc.net 한조 대기 중 문제 트롤 픽에 따라 욱제가 이길 수 있는지 없는지 확인하는 문제 #사용 알고리즘 이분 매칭 📌문제 접근 포인트 ※ 문제 자체는 이분 매칭 알고리즘 구현 방법만 알면 쉽게 해결 할 수 있는 문제 1. 배정할 수 있는 트롤픽 수를 구하기 위한 방법을 생각해보자. 각각의 고를 수 있는 트롤픽의 경우를 찾기 위해서 이분 매칭.. 2023. 7. 18.
[백준 1467] 수 지우기(python) https://www.acmicpc.net/problem/1467 1467번: 수 지우기 첫째 줄에 세준이가 가지고 있는 N자리의 수가 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에 세준이가 지울 숫자들이 공백 없이 주어진다. 지울 숫자의 개수는 N보다 작으며, 항상 www.acmicpc.net 수 지우기 문제 N자리의 수에서 몇 개의 수를 지웠을 때 만들 수 있는 가장 큰 수를 구하는 문제 #사용 알고리즘 그리디 스택 📌문제 접근 포인트 1. 각 수를 지우기 위해서 일단 주어진 숫자(N)의 종류와 갯수, 지워야하는 숫자(R)의 종류와 갯수를 각각 카운팅 배열을 통해 구성해보자. 2. for문을 통해 N을 탐색하면서, 주어진 수가 존재하고, 지울 수 있는 숫자랑 갯수가 같으면 각각에서.. 2023. 7. 14.
반응형