본문 바로가기
반응형

알고리즘 풀이164

[백준 12931] 두 배 더하기 (python) https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 두 배 더하기 문제 0으로 이루어진 크기 N의 배열 A를 주어진 조건에 맞는 연산을 진행했을 때, B와 같게 만들려면 최소 몇 번 연산을 구하는 문제. 그리디로 접근해서 해결할 수 있었다. 📌문제 접근 포인트 1. 주어진 연산은 배열의 값 1개를 1 증가 & 전체를 2배 하기의 연산의 과정으로 이루어져 있다. 0으로 이루어진 A배열을 B배열로 만드는 것보단 B배열을 0으로 이루어진.. 2023. 5. 9.
[백준 2667] 단지번호붙이기 (python) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 단지번호 붙이기 문제 N * N 크기의 정사각형의 칸에 이어진 숫자 단지들의 총 개수와 각 단지의 크기를 구하는 문제 BFS개념을 활용하여 해결할 수 있었다. 📌 문제 접근 포인트 1. 마을의 수를 탐색하고, 이어진 칸을 확인하는 것이므로 너비 탐색(BFS)을 이용하여 탐색을 진행해 주자. 2. 방문처리와 탐색을 동시에 진행하고, 리스트를 하나 만들어줘서 탐색하면서 세어준 개수를 넣어주자. 또 진행.. 2023. 5. 7.
[백준 1541] 잃어버린 괄호(python) https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 잃어버린 괄호 문제 +와 -로 이루어진 숫자 계산식에 괄호를 쳐서 값을 최소로 만드는 문제 단순 계산 아이디어를 떠올려서 split을 이용해 풀 수 있었다. 📌문제 접근 포인트 1. +와 -로 이루어진 숫자 계산식에 괄호를 쳐서 최솟값을 만들려 한다는 건 즉 - 사이의 숫자들을 모두 더해서 빼주면 된다는 뜻이다. 예를 들어 25-20+15-5+10+15 이런 숫자가 있다면 최소로 만들어주려면.. 2023. 5. 7.
[백준 7677] Fibonacci (python) https://www.acmicpc.net/problem/7677 7677번: Fibonacci For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000). www.acmicpc.net Fibonacci 문제 -1을 받을 때까지 반복하고, 숫자의 마지막 4자리를 출력하는 문제 분할정복을 이용하여 해결할 수 있었다. 📌문제 접근 포인트 1. 먼저 피보나치수열을 구해보자. N의 크기가 매우 큰 숫자이기에 재귀 or DP로는 절대로 시간 안에 들어오기 어려운 구조다... 2023. 5. 4.
[백준 10026] 적록색약 (python) https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 적록색약 문제 RGB로 나누어진 영역의 개수와, 적록 색약이어서 RRB 혹은 GGB로만 볼 수 있을 때 나누어진 영역의 개수를 구하는 문제 BFS 개념을 이용해서 해결할 수 있었다. 📌 문제 접근 포인트 1. 나누어진 영역의 수를 구하기 위해서 BFS를 이용한 탐색을 진행해 주자, 진행 과정에서 방문 여부를 체크하기 위한 리스트를 하나 지정해 주자. 2. 처음 주어진 리스트를 이용해서 볼 .. 2023. 5. 2.
[백준 1461] 도서관(python) https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 도서관 문제 0의 위치에서 놓여있는 책들을 m개 들어서 꽂으러 이동할 때 걸리는 최소 시간을 구하는 문제 그리디 개념과 정렬 개념을 활용하여 해결할 수 있었다. 📌 문제 접근 포인트 1. 책을 들고 0의 지점에서 M개를 들고 꽂으러 이동하러 다녀야 한다. 즉, 책을 꽂고 다시 0으로 돌아와야 하니 2배의 거리만큼 이동해야 한다 단, 마지막 이동을 할 때는 제자리를 돌아올 필요가 없으니 1번만 이동해도 .. 2023. 5. 2.
반응형

티스토리툴바