전체 글
-
[PS] 17081) RPG Extreme백준 PS 2022. 11. 1. 16:30
https://www.acmicpc.net/problem/17081 17081번: RPG Extreme 요즘 택희는 RPG 게임을 하고 있다. 던전을 헤쳐나가며 몬스터를 물리치고, 아이템을 모으고, 레벨 업을 하여 보스 몬스터를 물리치는 전형적인 RPG 게임이다. 이 게임은 N×M 2차원 그리드 위에서 www.acmicpc.net Platinum2) 17081.RPG Extreme 구현, 시뮬레이션 Platinum 구현 문제라 조건이 많고 세세한 부분 컨트롤에 유의하자. 구현 자체 코딩에는 많은 시간이 걸리지 않았지만 AC를 받는 것까지가 어려웠다. 개인적으로 빼먹었던 조건과 질문 검색의 유의사항을 정리해보자 아이템 박스는 방문시 교체가 일어나지 않아도 없어진다. 움직일 수 없는 상황에 가시를 밟고 있다..
-
[탐색] 이분/이진 탐색알고리즘 2022. 10. 25. 19:06
이분/이진 탐색 Heap에서 binary tree구조의 이점을 활용하여 대소 비교 연산을 줄여 O(logN)의 시간복잡도로 리스트의 반정렬 상태를 유지하면서 값을 삽입하거나 삭제할 수 있었다. 이분/이진 탐색도 위와 비슷하게 탐색 과정에서 절반을 신경쓰지 않으면서 대소 비교 연산을 진행할 수 있어 시간복잡도를 O(logN)으로 줄일 수 있다. 이분/이진 탐색 아이디어 위의 아이디어를 조금 더 구체화해서 보면 다음과 같다. 우선 주어진 리스트를 정렬한다. ( 정렬하는 이유는 절반을 신경쓰지 않고 대소 비교를 진행하기 위해서이다. ) 정렬된 리스트의 중간 Index의 값에 접근하여 탐색하고 싶은 값과 비교한다. 이때, 비교하여 작거나 큰 경우 중간 Index에서 우측 또는 좌측 부분의 값들은 비교할 필요가 ..
-
[PS] 1647) 도시분할계획카테고리 없음 2022. 10. 24. 19:16
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net Gold4) 1647.도시분할계획 그래프, 최소 스패닝 트리 이전에 풀었던 Gold4의 최소 스패닝 트리와 매우 흡사한 문제이다. 가장 기초적인 스패닝 트리 구성 문제로 풀이가 어렵지 않다. 크루스칼과 프림 알고리즘이 최소 스패닝 트리 만드는 방법으로 가장 잘 알려져 있다. 이번 문제에 대해서 크루스칼 알고리즘으로 풀이를 작성했다. 크루스칼 알고리즘의 수행 과..
-
[PS] 1806) 부분합백준 PS 2022. 10. 24. 19:00
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net Gold4) 1806.부분합 누적합, 두 포인터 누적합으로 처음에 코딩을 구성했지만 각 구간을 탐색하는 과정에서 for문을 두번 돌아 O(n^2)의 시간이 걸려 시간 초과가 났다. 시간을 줄이기 위해 두 포인터를 이용하여 코드를 다시 구성했다. 입력으로 받은 배열을 유지하며, 특정 값과 구간 합을 비교하므로 구간을 줄이고 늘리는 것으로 결과에 도달할 수 있어 두 포인터를 사용하여 깔..
-
[PS] 14939) 불끄기백준 PS 2022. 10. 21. 15:57
https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net Platinum5) 14939.불끄기 그리디 알고리즘, 브루트포스 알고리즘, 비트마스킹, 구현 S사 코딩테스트 이후 간만에 푼 구현 문제. 이번 문제도 길이가 짧고 요구사항도 간단하다. 주어진 10*10 필드에 0과 1로 전구가 켜져있거나 꺼져있는데 switch를 작동해서 이를 다 끄도록 해야한다. swtich는 해당 좌표를 누를 시 상하좌우와 함께 상태가 변한다. 이때 최소의 스위치로..
-
[PS] 1509) 펠린드롬분할백준 PS 2022. 10. 21. 13:50
https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net Gold1) 1509.펠린드롬분할 다이나믹 프로그래밍 다이나믹 프로그래밍으로 작성해서 AC를 받았다. 시간복잡도를 대충 계산해봤는데 펠린드롬 분할 확인에서 O(N^2), 문자열의 분할 수 최소값을 구할 때도 O(N^2)의 시간이 소요된다. 문제에서 주어진 요구사항은 문자열의 길이가 최대 2500으로 약 6만번의 루프가 수행된다. ..
-
[PS] 1202) 보석도둑백준 PS 2022. 10. 20. 19:27
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net Gold2) 1202.보석도둑 자료구조, 그리디 알고리즘, 정렬, 우선순위 큐 Heap 자료구조 사용 없이 코드를 구성했다가 시간 초과가 났다. 일반적인 Knapsack 문제와 비슷한 구조이고 특징은 가방이 여러 개인 것과 각 가방에 한 개의 보석을 넣을 수 있다는 점. 문제의 핵심은 각 가방의 무게 한계보다 작은 무게의 보석 중 가장 ..
-
[Python] Heapq 모듈로 힙(Heap) 구현하기Python 2022. 10. 20. 18:22
Heapq 모듈 사용법 Heapq 모듈을 사용하여 Heap 구조를 만족하는 배열을 생성할 수 있다. 기본적으로 Min Heap으로 구현됨. 1. Import import heapq 2. Heap 노드와 값을 저장할 배열 초기화 Min_Heap = list() 3. 노드 추가 ( Heappush() ) # 삽입은 heappush 사용 # 기본 구조 : heappush(배열, 값) for i in range(3,0,-1) : heapq.heappush(Min_Heap, i) print(Min_Heap) # 결과 : [3] -> [2, 3] -> [1, 3, 2] # root와 새로 추가된 노드의 swap 고려 4. 노드 삭제 ( Heappop() ) # 삭제는 heappop 사용 # 기본 구조 : heapp..