백준 PS
-
[PS] 2178) 미로 탐색백준 PS 2022. 11. 14. 19:52
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net Silver1) 2178.미로 탐색 그래프 탐색, BFS, DFS BFS, DFS 문제도 많이 풀어봤지만, 다시 한번 기본적인 문제로 정리하고 싶어 풀어봤다. DFS와 BFS는 한 번 이해하면 쉽게 다가오지만 막상 코드를 직접 짜려하면 잘 떠오르지 않을 수 있다. 또한, 문제마다 주어진 형식에 맞춰 조정할 필요도 있기 때문에 잘 다져놓는 것이 좋다. 해당 문제는 가장 기본적인 미로찾기이다. 보통 BFS가 DFS보다 퍼포먼스가 좋..
-
[PS] 2293) 동전 1백준 PS 2022. 11. 14. 19:43
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net Gold5) 2293.동전 1 다이나믹 프로그래밍 다이나믹 프로그래밍 풀이가 계속 감이 잡히지 않아 아예 다이나믹 프로그래밍 카테고리에 들어가서 문제들을 풀었다. 골드5지만 다이나믹 프로그래밍은 난이도 체감이 천차만별이다. 기본적인 동전 문제 구성에 애초에 카테고리로 들어간 문제라 처음부터 DP로 접근했다. 사실 문제를 낯선 상황에서 만난다면 DP를 떠올리는 것부터가 문제이다. DP를 생각하고 접근..
-
[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를 받는 것까지가 어려웠다. 개인적으로 빼먹었던 조건과 질문 검색의 유의사항을 정리해보자 아이템 박스는 방문시 교체가 일어나지 않아도 없어진다. 움직일 수 없는 상황에 가시를 밟고 있다..
-
[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 문제와 비슷한 구조이고 특징은 가방이 여러 개인 것과 각 가방에 한 개의 보석을 넣을 수 있다는 점. 문제의 핵심은 각 가방의 무게 한계보다 작은 무게의 보석 중 가장 ..
-
[PS] 1007) 벡터매칭백준 PS 2022. 10. 20. 15:53
https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net Gold2) 1007.벡터매칭 수학, 브루트포스 알고리즘 문제를 잘못 읽어서 돌고 돌아 AC를 받은 문제. 요구 사항은 복잡하지 않아 쉽게 해결방법을 떠올릴 수 있었다. 주어진 모든 점을 각각 한 번씩 사용하여 벡터를 구성하고 구성한 벡터들의 벡터합을 구하여 벡터의 크기를 출력하면 된다. 이때, 주어진 점에 대해 구성할 수 있는 벡터들이 정해져 있지 않으므로 브루트포스 알고리즘을 사용하여..