본문 바로가기

⭐ Problem_Solving/백준30

[백준] 1662 압축 (Python/파이썬) https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 1. 스택을 활용한 문자열 문제이다. 2. 문제를 보면 가장 먼저 떠올리기 쉬운 풀이는 실제로 문자열을 압축해제해서 결과 문자열의 길이를 구하는 건데, 그렇게 할 경우 문자열의 최대 길이가 2,147,473,647인지라 당연히 메모리 초과가 발생한다. 3. 핵심은 문자열 전체를 구하는 게 아니라 '길이'를 구하는 것이므로 괄호 앞에 위치한 반복 횟수를 나타내는 문자만 숫자 그대로 저장하고, .. 2022. 10. 5.

[백준] 20057 마법사 상어와 토네이도 (Python/파이썬) https://www.acmicpc.net/problem/20057 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 특별한 알고리즘을 필요로 하지 않는 구현 문제이다. 구현해야할 요소는 크게 모래바람의 확산과 토네이도의 이동이다. 모래바람의 확산 모래바람이 확산되는 좌표랑 비율을 딕셔너리 형태로 담아준다. 더 똑똑한 방법도 있을 거 같은데 나는 그냥 모든 좌표랑 비율을 일일이 입력했다 이럴 경우 오타가 있으면 디버깅 시 발견하기 매우 힘드니 주의하자 딕셔너리에 저장해둔 좌.. 2022. 10. 4.

[백준] 2437 저울 (Python/파이썬) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 그리디 문제로 정답코드를 보면 매우 단순한데 아이디어를 떠올리기까지가 매우 힘들다. 핵심 아이디어는 다음과 같다. 현재까지 측정 가능한 무게의 최댓값을 ans라고 하면 (1 - ans)의 값들을 측정할 수 있다. 오름차순으로 정렬된 무게추들 중에서 하나의 무게추(weight)을 선택한다. weight ans + 1라면 ans + 1의 값은 측정 불가능하므로 해당 값이 정답이 된다. 단 1, 1, 1, 1 혹.. 2022. 10. 3.

[백준] 20056 마법사 상어와 파이어볼 (Python/파이썬) https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 특별한 알고리즘을 필요로 하지 않는 구현 문제이다. 어떤 자료구조형을 어떻게 사용해서 파이어볼의 정보와 위치 등을 나타낼 것인가가 생각하기 좀 까다롭다 구현해야할 요소는 크게 파이어볼의 이동 / 파이어볼의 병합과 분산이다. 먼저 파이어볼의 이동이다. 파이어어볼의 이동은 리스트에 담은 파이어볼의 정보를 하나씩 꺼내서 빈 리스트를 원소로 가진 N x N 배열(리.. 2022. 10. 3.

[백준] 14621 나만 안되는 연애 (Python/파이썬) https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 1. 기본적인 MST 문제이다. 2. 대학교 남초/여초 여부를 딕셔너리 형태로 저장해서 크루스칼 알고리즘에서 다음 간선 선택 시 다른 종류의 대학교일 경우만 선택하도록 했다. 3. 그 외에는 조건을 만족하는 mst가 없을 경우 -1을 출력하도록 해야된다. import sys, os, io, atexit input = lambda: sys.stdin.read.. 2022. 10. 2.

[백준] 16724 피리 부는 사나이 (Python/파이썬) https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 0. DFS / BFS (+ 유니온파인드) 문제이다. 유니온 파인드에 괄호를 친 이유는 아래 설명하겠지만 유니온 파인드를 안 쓰고 bfs만으로 풀이 하는 방법도 있기 때문이다. (아래 설명) 1. 유니온 파인드 풀이 주어진 그래프에서 dfs를 통해서 사이클을 확인하고 해당 사이클을 하나의 safezone 그룹으로 묶는 과정을 반복해야하는데 이 과정에서 유니온 파.. 2022. 10. 2.

이전 1 2 3 4 5 다음

티스토리툴바