본문 바로가기

CS/알고리즘 & 문제풀이53

[Python] 백준 13258 복권 + 은행 문제 링크 : https://www.acmicpc.net/problem/13258 13258번: 복권 + 은행 두 번째 예제의 경우에 첫 주가 지난 후 1/3의 확률로 (3, 2, 2)가, 1/3의 확률로 (2, 3, 2)가, 1/3의 확률로 (2, 2, 3)이 된다. 둘째 주에 (3, 2, 2)는 기댓값이 3.4286이 되고, (2, 3, 2)와 (2, 2, 3)은 기댓값이 2.2857 www.acmicpc.net 1. 접근 방법 간단한 확률 계산 문제로, 기댓값을 알아내면 된다 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/13000/13200/13258.py GitHub - mintropy/PS:.. 2022. 8. 5.
[Python] 백준 1655 가운데를 말해요 문제 링크 : https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1. 접근 방법 입력을 계속 받으며 중간 값을 출력해야 한다. 이때, 입력이 많기 때문에 계속 정렬을 한다거나 탐색을 하면 시간 초과가 날 것으로 보인다. 그렇기 때문에 중간값을 기준으로 큰 값, 작은 값을 각각 보관하고, 입출력이 많을 수 있기 때문에 heap 구조를 활용했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintr.. 2022. 8. 3.
[Python] 백준 20149 선분교차 3 문제 링크 :https://www.acmicpc.net/problem/20149 1. 접근 방법 문제는 매우 간단하다. 두 선분의 끝점이 주어지고, 교차하는지 판별하면 된다. 하지만 이를 해결하기 위한 과정은 간단하지 않을 수 있다. 우선, 선분 교차와 관련하여 CCW 지식이 있으면 더욱 편하게 해결할 수 있다. 그리고 선분 위치에 따라 분류하여 작업을 진행해야 한다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/20000/20100/20149.py GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다. 다양한 알고리즘 문제 풀이 저장소입니다. Contribute to min.. 2022. 7. 25.
[Python] 백준 5527 일루미네이션 문제 링크 : https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 1. 접근 방법 BFS를 응용하여 해결하는 문제인데, 육각형 구조에 따라 추가적인 고려사항이 생긴 문제이다. 그리고 단순히 육각형의 수를 원하는 것이 아니라 모서리의 길이를 구하여야 하므로, 조금 더 복잡한 과정이 필요할 수 있다. 처음에는 각 선분을 좌표로 하여 탐색하려 했다. 어차피 한붓그리기 형태가 될 것이므로 구현은 조금 복잡할 수 있지만, 쉽게.. 2022. 7. 11.
[알고리즘] 이분 매칭(Bipartite Matching) 1. 이분 매칭 네트워크 플로우(Network Flow) 알고리즘에서 두 정점 사이의 용량이 1이고, 정점이 두 집합으로 구분되는 특수한 경우. 한쪽 그룹을 X, 다른 그룹을 Y라고 할 때, X → Y로의 최대 유량을 구하는 문제. 이때, 각 용량이 1이므로 최대 매칭 수를 찾는 문제로 볼 수 있음. 2. 알고리즘 예시 DFS를 활용하여, 매칭을 하나씩 선택하는 과정을 거친다. 예시는 조금 복잡하지만, 백준 문제의 예시를 가져왔다. 세부적인 예시는 아래와 같다. 다음과 같이 왼쪽 그룹, 오른쪽 그룹에 있는 정점에 대하여 각 선분 중 연결되어 있다. DFS를 응용하여 편하게 최적의 답을 찾을 수 있다. 우선 1번점에서 연결할 수 있는 최적의 점을 찾는다. 그러면, 왼쪽 1번점, 오른쪽 2번점을 연결할 수 .. 2022. 5. 22.
[Python] 백준 3806 S를 T로 문제 링크 :https://www.acmicpc.net/problem/3806 3806번: S를 T로 첫째 줄에 테스트 케이스의 개수 C (C ≤ 200)가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있다. 첫째 줄에는 '0', '1', '?'로 이루어진 S, 둘째 줄에는 '0', '1'로 이루어진 T가 주어진다. 두 문자 www.acmicpc.net 1. 접근 방법 접은 방법을 조금 고민했는데, 가능한 조건이 많지는 않지만, BFS나 DP로는 적합하지 않을 것 같아 그리디한 방식을 탐색했다. 2. 풀이 코드 🖥python 코드 링크 :https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/3000/3806.py GitHub - mintropy/PS.. 2022. 4. 17.
[Python] 2212 센서 문제 링크 : https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 1. 접근 방법 각 값이 아니라, 각 값의 차이 중 최솟값을 뽑아내는 그리디 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2200/2212.py GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다. BO.. 2022. 3. 25.
[Python] 백준 2533 사회망 서비스(SNS) 문제 링크 : https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 1. 접근 방법 DP와 DFS를 고민했는데, 나는 둘 다 사용한 방법으로 가닥을 잡았다. 문제를 해결하고 DP로만 해결하는 등의 풀이도 고민했지만, 잘 되지는 않아 시간은 조금 오래 걸렸지만, 해결했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2500/2533.py Git.. 2022. 3. 22.
[Python] 백준 13335 트럭 문제 링크 : https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 1. 접근 방법 queue를 활용하여 쉽게 해결할 수 있는 문제. 리스트를 활용한다면, 슬라이싱으로 유사하게 구현할 수 있을 것 같다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/13000/13335.py GitHub - mintropy/ba.. 2022. 3. 21.

티스토리툴바