반응형 백준5 [백준] 18353번: 병사 배치하기 | LIM 📚문제 N명의 병사가 무작위로 나열되어 있다. 각 병사는 특정한 값의 전투력을 보유하고 있으며, 병사를 배치할 때는 전투력이 높은 병사가 앞쪽에 오도록 내림차순으로 배치를 하고자 한다. 다시 말해 앞쪽에 있는 병사의 전투력이 항상 뒤쪽에 있는 병사보다 높아야 한다. 또한 배치 과정에서는 특정한 위치에 있는 병사를 열외시키는 방법을 이용한다. 그러면서도 남아있는 병사의 수가 최대가 되도록 하고 싶다. 예를 들어, N=7일 때 나열된 병사들의 전투력이 다음과 같다고 가정하자. 이 때 3번 병사와 6번 병사를 열외시키면, 다음과 같이 남아있는 병사의 수가 내림차순의 형태가 되며 5명이 된다. 이는 남아있는 병사의 수가 최대가 되도록 하는 방법이다. 병사에 대한 정보가 주어졌을 때, 남아있는 병사의 수가 최대가.. 2023. 2. 5. [백준] 2110번: 공유기 설치 Python (이분탐색) | LIM 문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 늘 이분탐색 문제를 접할 때마다 느끼는 거지만 어떤 걸 기준으로 이분탐색을 이용해야 하는지 어렵다. 처음 생각한 방식 집의 좌표에 대한 인덱스들로 이분탐색을 진행하는 걸까? 였다. 하지만 여기서 문제는 공유기 개수만큼 어떻게 좌표를 정할 것이냐였다. 문제가 잘 안 풀려서 여기저기 블로그 글을 검색해 보면서 깨달았다. 어떤 부분에서 이분탐색을.. 2023. 1. 15. [백준] 14888번: 연산자 끼워넣기 Python (DFS, BFS) | LIM 이 문제의 경우는 순서대로 연산자에 상관없이 계산해야하기 때문에 연산자를 하나씩 뽑아서 즉, popleft를 사용하여 구현해야 한다고 생각했다. 즉 BFS를 사용하여 문제를 해결하였다. 1. 숫자는 순서의 바뀌지 않고 연산자의 순서만 바뀌기 때문에 연산자의 조합이 어떻게 올 지 부터 먼저 구해야 한다. (조합은 permutation을 이용하여 구했다. 다만, permutation의 경우 ['+','+','+','+']의 경우 모두 다르게 인식하여 경우의 수를 많이 만들기 때문에 set을 사용하여 조합을 unique한 상태로 변경해야 한다.) 2. 연산자의 특성 중 나눗셈 부분이 기존 나눗셈의 개념과는 다르기 때문에 나같은 경우 함수로 사칙연산을 구현해주었다. (생각보다 시간이 오래 걸리지 않았다..) 3.. 2021. 9. 12. [백준] 18405번: 경쟁적 전염 Python (DFS, BFS) | LIM 이 문제는 BFS를 이용하여 풀었다. 생각보다 이 문제는 간단하게 풀 수 있었다. 먼저, 바이러스가 존재하는 위치와 그 위치에 바이러스 값을 저장했다. 또한, 바이러스 숫자가 작을수록 우선수위를 갖기 때문에 바이러스 숫자가 작은 순서대로 sorting 해주었다. popleft()를 통해 앞에 있는 것(바이러스 숫자가 작은것)부터 뽑아내며 상하좌우로 퍼지게 하였다. 퍼지게 한 후 바이러스가 전염된 부분의 바이러스 값과 인덱스를 기존 virusIndex에다가 뒤로 저장하였다. 맨 처음에 순서대로 sorting 해주었기 때문에 추후에 저장되는 바이러스 값은 자동으로 정렬이 되어 있다. 기존에 있던 바이러스가 모두 popleft()를 통해 사라지고 그 바이러스를 통해 전염된 바이러스와 인덱스만 남게 되면 시간을.. 2021. 8. 31. [백준] 14502번: 연구소 Python (DFS, BFS) | LIM DFS와 BFS에 관련하여 설명은 너무 많기에 내가 기억하고 싶은 것만 정리하고자 한다. DFS - Depth-First Search(깊이 우선 탐색) 즉, 깊은 부분부터 탐색하겠다는 이야기이다. 깊은 부분부터 탐색한다는 말이 사실 잘 이해가 되지 않기에 그냥 DFS는 스택을 사용한다로 외웠다. DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀함수를 이용했을 때 매우 간결하게 구현할 수 있다. 스택은 박스 쌓기에 비유할 수 있다. 박스를 쌓다가 아래에 있는 박스를 치우기 위해서는 위에 박스부터 먼저 치워야 한다. 이러한 구조를 선입후출, 후입선출 구조라고 한다. 그냥 먼저 들어온게 나중에 나간다고 생각하면 쉽다. 왜냐하면 쌓기 때문이다. DFS가 동작하는 과정은 다음과 같다. 1. 탐색 시작.. 2021. 8. 31. 이전 1 다음 반응형
