Algorithm/Baekjoon For.Java28 백준 11003 : 최솟값 찾기 https://www.acmicpc.net/problem/11003이번엔 백준 11003 : 최솟값 찾기다.탐색을 위한 Big-O를 제외하고 사실상 O(n)에 가깝게 풀어야하는 만큼 쉬운 문제는 아니었다.(플래티넘 5더라고요??) 기본적으로는 PriorityQueue의 원리로 풀어야하는 것이 맞다.그러나 PriorityQueue의 단점 중 하나는 우선순위 큐의 peek원소가 아닌 다른 원소를 뽑아내는 과정은 O(n)이라는 것이다.따라서 PriorityQueue만으로는 문제를 풀기 어렵다. PriorityQueue가 안된다면 Queue의 형태로는 구할 수 있을 것인가? 불가능하다. 역시 Queue 역시 출구가 하나뿐이다. 선입선출의 자료구조이므로 .remove Method를 사용한다고 하더라도 O(n)이 .. 2025. 7. 10. 백준 1644 : 소수의 연속합 https://www.acmicpc.net/submit/1644/95941199오늘 푼 따끈따끈한 문제다.특히 한 번에 풀게 되어 기분이 매우 좋다. 앞으로도 계속 한번에 풀 수 있도록 조금 더 노력해야지. 이 문제는 소수의 연속합이라면서 소수를 알려주지 않는다.따라서 문제를 풀 때 소수를 필히 구해야 한다. 이때, 4백만이라는 완전 탐색에 다소 괴랄한 수가 있어 조금 걱정을 했으나, 아래와 같이 소수를 구할 경우 2중 for문에도 불구하고 O(nlogn)으로 결과를 뽑아낼 수 있을 거라고 생각했다.먼저 multiple로 증감자를 만든 후, 변화되는 수를 idx로 두게 되면idx의 시작점이 2인 경우, 2를 제외하고 4,6,8,10 등이 사라지게 된다.기본적인 원리는 에라토스테네스의 체다. 그렇게 소수를.. 2025. 7. 4. 백준 1766 : 문제집 https://www.acmicpc.net/problem/1766이번 문제는 문제집이란 것으로 시작점을 파약해야한다는 점문제를 푸는 순서가 존재한다는 점으로 미루어보아 위상 정렬로 문제를 접근했다. 그러나 초기 접근은 DFS로 접근을 했는데, 기초적인 위상정렬의 형태로는 문제가 풀리지 않았기 때문이다.이유는 진입 차수가 0인 것을 모두 Queue에 넣어 순서를 지키며 위상정렬을 하는 것이 기본적인 형태였다면, 여기서는 숫자가 작다면 더 빨리 풀 수 있는 조건이 있었기 때문이다.이 과정 때문에 PriorityQueue를 사용해서 순서를 지키며 문제를 풀었다. 구해야 할 것문제를 푸는 순서문제 풀이 순서1. 입력을 받으면서 a->b로 입력 시 b를 인덱스로 하는 진입 차수 배열 inOrder[b]를 증가한다.. 2025. 7. 2. 백준 2630 : 색종이 만들기 https://www.acmicpc.net/problem/2630 이번 문제는 백준 2630 색종이 만들기 문제이다.카테고리는 분할 정복으로 되어 있지만, 결국 접근해야할 문제 방법은 재귀다.재귀를 이용해서 색종이의 색이 일치하는지 안하는지를 확인해나가며 체크한다면 정답을 얻을 수 있다. 시간 체크를 안하기도 했지만, 단번에 풀어 큰 문제가 없다고 판단했다.^^ 구해야할 것흰 색종이와 푸른 색종이의 갯수방법1. 좌측 상단의 색종이 좌표와 우측 하단의 좌표를 구해 해당 색종이가 같은 색인지 확인한다.2. 만약 색종이의 색이 같다면 좌측 상단의 색을 구하고 해당 색을 더해준다,3. 색종이의 색이 같지 않다면 좌측 상단의 좌표와 우측 하단의 좌표를 이용해 색종이를 4개로 쪼갠다.이때 좌표는 좌측상단 좌표와 우.. 2025. 6. 25. 1748 : 수 이어 쓰기 1 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 자 이번엔 수 이어쓰기다. 어제는 문제 풀기가 싫어서 그냥 간단한 문제를 들고 와봤는데, 생각보다 조건 자체가 굉장히 타이트했다. 0.15초에 128MB라... 다른 문제에서는 2초에 512MB주는 것과는 달리 타이트했지만 어쨌든 자바에서 별도의 조건이 있지 않는 걸 보면 자바로도 풀 수 있는 거겠지 1.1번 접근 우선 문제를 보면 1,2,3,4,5, 등의 숫자를 단순히 이어붙이면 N번쨰 숫자까지 이어붙였을 때 수가 몇 자리가 되는가? 라는 것이다. 단순하게 문제를 접근하면 StringBuffer를 써서 append .. 2024. 1. 21. 2775 : 부녀회장이 될테야 https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 누가 이거 제목 보고 웃으라고 했습니까 대답합니다 자 오늘은 부녀회장이 될 시간이다. 아파트 짱 먹는거지 원리 자체는 Dynamic Programming이다 한칸씩 한칸씩 계산해서 최종적으로 우리가 원하는 호수의 인원을 세는 것으로 Memoization 기법을 이용하면 쉽게 풀 수 있다. 201호이면 101호 202호이면 101호 + 102호 203호이면 101호 + 102호 + 103호 이런 식이다 자, 그렇다면 203호를 구하고자 할.. 2023. 3. 30. 이전 1 2 3 4 5 다음 반응형