CS/알고리즘 & 문제풀이53 [Python] 백준 2866 문자열 잘라내기 문제 링크 : https://www.acmicpc.net/problem/2866 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 1. 접근 방법 전체 탐색을 하기에는 많은 것 같고, 탐색을 줄이며 해결하기 위해 이분 탐색을 선택했다. 각 문자열이 중복인지 확인하기 위해 집합을 사용했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2800/2866.py GitHub - mintropy/bae.. 2022. 3. 13. [Python] 백준 20928 걷는 건 귀찮아 문제 링크 : https://www.acmicpc.net/problem/20928 20928번: 걷는 건 귀찮아 일직선 위에 놓인 $N$개의 지점 $p_i$에는 최대 $x_i$만큼 이동시켜주는 인력거꾼들이 있다. 즉, $p_i$에 있는 인력거꾼은 $p_i$, $p_i+1$, $p_i+2$, $...$, $p_i+x_i$ 중 한 지점까지 승객을 데려다준다. 세상 www.acmicpc.net 1. 접근 방법 DP나 큐를 활용한 탐색을 고민했는데, 계속해서 시간 초과되었다. 최대 1,000,000까지 탐색을 해야 돼서 N 또는 2N정도로 해결하는 방법을 찾아야 했다 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000.. 2022. 3. 6. [Python] 백준 11000 강의실 배정 문제 링크 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 1. 접근 방법 시작 끝 시간을 기반으로 간단한 그리디라 생각했는데, 문제를 다시 읽고 보니 전체 강의 실수를 확인하는 조금 번거로울 수 있는 문제였다. 이를 해결하기 위해 heap을 활용하여 가장 빨리 끝나는 시간 기준으로 고민했다. 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/11000/11000.py 📕코드 해설 시작 시간 기준으로 오.. 2022. 2. 27. [Python] 백준 13164 행복 유치원 문제 링크 : https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net 1. 접근 방법 정렬을 우선적으로 했고, 그 이후 어떻게 짝을 지어갈지 결정해야 하는데 그 방법에서 조금 고민을 했다 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/13000/13164.py GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장.. 2022. 2. 27. [Python] 백준 21924 도시 건설 문제 링크 : https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 1. 접근 방법 오랜만에 MSP 문제를 접근하여 방법이 잘 떠오르지 않아 여러 가지 방법을 시도하다가, 결국 union-find로 해결했다 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob.. 2022. 2. 21. [Python] 백준 16562 친구비 문제 링크 : https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 1. 접근 방법 union-find로 친구들을 묶으면 된다고 생각했고, 나름 쉽게 잘 풀렸던 것 같다 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/16000/16562.py GitHub - mintropy/baekjoon_py: BOJ를 Pytho.. 2022. 2. 20. [Python] 백준 18809 Gaaaaaaaaaarden 문제 링크 : https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 1. 접근 방법 좀 귀찮은 구현 문제라고 생각했는데, 구현보다는 브르투포스+BFS의 느낌이 컸다. 조합은 itertools로 간단하게 구현했는데, 세부 구현에서 고민을 했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/18000/1.. 2022. 2. 2. [Python] 백준 2173 양파깡 만들기 문제 링크 : https://www.acmicpc.net/problem/2173 2173번: 양파깡 만들기 (주) 넝심에서는 양파링의 아성에 도전할 만한 아이디어 과자인 양파깡을 만들어냈다. 양파깡은 기존의 양파링과는 달리 직사각형의 모양을 갖는 과자이다. 그런데 (주) 넝심의 과자 기술은 그 www.acmicpc.net 1. 접근 방법 브루트 포스 하게 접근해야 했다. 모든 가능한 경우를 각 순간마다 따져봐야 하기에, 가능한 모든 모양일 미리 저장해 두고, 불가능한 경우는 쳐내는 방식으로 진행했다. 2. 풀이 코드 🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2100/2173.py GitHub - mintropy/ba.. 2022. 1. 13. [Python] 백준 2671 잠수함식별 문제 링크 : https://www.acmicpc.net/problem/2671 2671번: 잠수함식별 입력에 들어있는 스트링을 읽고, 이것이 잠수함의 엔진소리를 나타내는 스트링인지 아니면 그냥 물속의 잡음인지를 판정한 후, 잠수함의 엔진 소리에 해당하는 스트링이면 "SUBMARINE"을 출력하고 www.acmicpc.net 1. 접근 방법 우선 정규 표현식도 잘 알지 못했고, 일반적인 문자열 패턴 찾는 방식으로 우선 접근했다. 이후 re 라이브러리를 활용한 정규식 패턴 매칭방식과 문자열 패턴을 확인하여 정답을 구하는 방법 모두 사용해보았다. 2. 풀이 코드 🖥python 코드 링크: https://github.com/mintropy/baekjoon_py/blob/master/2000/2600/2671... 2021. 12. 17. 이전 1 2 3 4 5 6 다음
