본문 바로가기

⭐ Problem_Solving44

[백준] 17142 연구소 3 (Python/파이썬) https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 1. 연구소 2랑 매우 유사하나 비활성 바이러스의 처리가 생각보다 까다롭다 2. 활성바이러스와 만나면 활성 상태로 변하니 '1'의 성질을 가지면서, 동시에 확산 시간에는 영향을 미치지 않으므로 '0'의 성질을 가지게 된다. 3. 여러가지 방법이 있겠지만 나 같은 경우는 비활성 -> 활성 바이러스의 좌표를 저장하면서 탐색하다가 마지막에 0으로 초기화해줌으로써 확산 시간 계산에 영향을 안 미치도록 했다. fr.. 2022. 10. 7.

[백준] 1766 문제집 (Python/파이썬) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. 우선순위큐로 위상정렬을 수행하면 되는 문제이다. 2. 문제의 조건을 읽어보면 비교적 명확하다. - 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. -> 위상정렬 - 가능하면 쉬운 문제부터 풀어야 한다. -> 우선순위 큐 3. 위상정렬 공부하면서 푼 문제였는데 위상정렬임을 알고 풀어서 그런지 몰라도 난이도에 비해서.. 2022. 10. 6.

[백준] 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.

이전 1 ··· 3 4 5 6 7 8 다음

티스토리툴바