백준문제풀이 (13) 썸네일형 리스트형 Q. 1644 소수의 연속 합(feat. 투포인터) 이 글을 쓰는 이유지난 주에 싸피 13기 코테를 봤다. 물론 코테 공부는 하지 않았지만 예상했던 것보다 쉽다 느껴졌다.대외비라 자세한 문제는 올릴 수 없지만 투포인터로 풀수 있는 문제가 나왔는데 당시에 도저히 기억이 안나서 DP로 풀었는데 이참에 투포인터를 좀 더 파보자 생각이 들어 이 글을 쓴다. 정보난이도: 골드 3문제 링크https://www.acmicpc.net/problem/1644 문제 요약N을 입력 받고 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수의 갯수를 찾는 문제이다. ex)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 간단한 문제이지만 여러 문제가 합쳐져 있다.1. 소수 목록 구하기2. 연속된 소수 합 구하기 1. 소수 목록 구하기먼저 소수 .. 위상정렬 알고리즘(Topology Sort) 위상정렬 알고리즘은 순서가 정해진 작업을 차례로 수행해야 할 때 사용한다. 순서의 일부만 나타낸 list를 가지고(graph의 edge와 같이) 전체 순서를 찾는 방식이다.위상정렬 알고리즘의 가장 중요한점은 제일 처음에 있는 head는 자신을 가르키고 있는 노드가 없다는 점이다 이게 무슨 말이냐 다음과 같은 그래프가 있을 때 자신을 가르키는 노드(진입차수)가 없는 노드는 1번 뿐이다. 따라서 다음 그래프의 시작점은 1인 것이다. 따라서 각 노드의 진입차수를 표로 관리한다. 따라서 시작점은 1번인 것이다. 1번이 시작이면 이제 1번 노드를 삭제하고 진입차수를 다시 계산한다.정확히 말하면 다시 계산이 아닌 1번 노드와 연결된 노드들을 1씩 빼는 것이다. 이 때 진입차수가 0인 노드가 다음 순서이다.이런식으로.. 백준 7453 Java (int[] 와 List의 차이) https://www.acmicpc.net/problem/7453 문제를 풀면서 그 전문제에 투포인터로 시간 복잡도를 낮출 수 있는 방법을 배워 그것을 활용해 풀었다. 하지만 시간 복잡도가 아직도 컸다. 최초 코드를 보면서 분석해보자public class Main { static long count; static int[] A, B, C, D; static int N; static List AB, CD; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTok.. 백준 2133 오답풀이 https://www.acmicpc.net/problem/2133난이도: 골드4 해당 문제는 DP 문제로 생각보다 생각해야할 문제들이 많은 문제였다. 최초에 생각한 방식은 dp[6]이면 dp[4]와 dp[2]를 곱하고 둘의 순서가 바뀔 수 있으므로 2를 곱하면 될줄 알았다.하지만 dp[4] 안에는 dp[2] dp[2]의 배열이 있기 때문에 중복되는 값이 존재한다는 점이었다. 따라서 dp[4]에만 있는 모양을 따로 빼기로 마음 먹었다. 모든 dp에는 나누어 떨어지지 않는 모양이 2개 존재한다. 따라서 dp[i-2] * dp[2]를 한 뒤 dp[i]에 나눠 떨어지지 않는 2가지 경우만 * 2를 해줬다 + dp[i]에만 존재하는 2개 결과적으로 아래와 같은 점화식을 세웠다dp[i] = (dp[i - 2] + .. 2022.06.30 백준 Q2178 학습 내용 : DFS, BFS의 차이점(어떤 것으로 구현해야 할지), 미로문제 구현방법 https://www.acmicpc.net/problem/2178 이 문제는 미로 문제를 구현하는 방법에 대해 묻는 문제이다. 미로 문제를 통해 (N,M)로 가는 가장 짧은 경로를 출력해야한다. 필자는 노드를 Class로 구현해 n,m,1인지0인지 유무(isOpened), 방문했던 노드인지(isVisited) 그 곳까지 가는 가장 짧은 경로(length)를 담았다. 그리고 가장 가에 있는 노드들을 다른 노드들과 똑같이 움직일수 있게 통일성을 맞추기 위해 겉을 0으로 감쌌다 ex) 10 01 -> 0000 0100 0010 0000 또한 이 문제는 최단 경로를 찾아야하기 때문에 DFS가 아닌 BFS로 구현해야한다. BF.. 2022.06.29 백준 Q1927 학습 내용 : 최소 힙 구현, PriorityQueue API를 이용한 최소힙 구현 이 문제는 최소 힙을 구현하는 문제이다. 필자는 API 사용 없이 구현을 한 후에 API를 사용해 구현하였다. static void addData(int data){ int currentIndex = ++size; while (currentIndex != 1 && list[currentIndex / 2] > data) { list[currentIndex] = list[currentIndex / 2]; currentIndex = currentIndex / 2; } list[currentIndex] = data; } 위 코드는 addData를 구현한 코드이다. currentIndex = ++size를 해 size를 하나 늘려.. 2022.06.28 백준 Q1874 학습 내용 : 스택 사용. 어떨 때 구현 가능하고 어떨 때 불가능한지 구분하는 방법 이 문제는 스택을 사용하여 입력받은 숫자 배열을 구현하는 방법을 묻는 문제이다. 원하는 배열을 wantedArray에 저장하고 inputStackNum은 다음 스택에 넣어야 할 숫자를 저장하게 했다(1~num까지). 만약wantedIndex가 num까지 도달했으면 이미 모든 wantedArray 배열이 끝났으므로 break; 시켜준다. 만약 스택이 비여있다면 inputStackNum의 값을 스택에 넣어주고 스택이 비여있지 않으면 가장 위에 있는 stack 값이 wantedArray[wantedIndex]값과 같은지 비교한다. 값이 같으면 wantedIndex++하고 stack.pop()해준다.(-) 출력. 만약 같지 않다.. 2022.06.27 백준 Q11651 학습 내용 : Comparable 인터페이스를 이용한 정렬 방식 수정과 정렬 이 문제는 바로 전 게시물인 Q11650과 비슷한 문제이지만 이번에는 Comparable 인터페이스를 이용해 한 클래스 안에서 comparTo와 객체에 대한 data를 동시에 넣었다. 클래스 안에 x,y좌표도 있기 때문에 compare로 인자 2개를 받는것이 아닌 compareTo로 객체와 인자 1개를 비교하면 된다. public int compareTo(Pointer o) { if(y>o.y) return 1; else if(y==o.y){ if(x>o.x) return 1; } return -1; } -코드 본문- package BaekJoon11651; import java.io.BufferedReader; import j.. 이전 1 2 다음
