begong블로그

"에라토스테네스의 체"를안다면 쉽게 풀리는 문제이다. 에라토스테네스의 체란 간단히 말해소수의 배수 = 소수가 아님을 이용한 것이다.반복문을 돌며 가작 작은 소수인 2부터 배수를 지워주고 그다음 3 , 5 순으로 돌면서 배수를 지워준다.이때 배열로 배수를 지우며, 이미 체크가 된 숫자는 소수가 아니므로 검사를 넘어간다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu..

백트래킹 및 재귀함수 문제 공을 뺄 때마다 배열을 새로만드는 방법은 너무 메모리와 시간을 많이 잡아먹는다 굳이 새로운 배열을 만들지 말고 방문처리를 하여, W번째 공을 뺀 효과를 준다. 또한 W+1,W-1번째 공도 방문처리가 되어있다면, W+2,W-2번째를 탐색하는 식으로, 다음 공을 찾으면 된다. 양끝 공은 절대 빠질 수 없기 때문에 배열 overflow가 나지 않는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int max = 0; static int N; static boolea..

백트래킹 문제 입력을 오름차순으로 정렬하고 전 단계에서 방문한 노드가 현재 노드와 같은지 확인을 한다(중복 방지를 위해) 만약 같으면 그 단계는 건너뛰고 아닐 경우 진행하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; class Main { static int N, M; static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReade..

그리디 알고리즘 문제 접근방식 - 전봇대의 왼쪽, 오른쪽 집의 갯수가 같아야 한다 = > 1 3 5 7 이라 가정했을 때 전봇대가 3->2로 이동한다고 치면, 오른쪽에 집이 3개가 있기 때문에 거리의 합이 +3-1이되어 +2가된다. 3~5에서 이동은 좌측, 우측 집이 2개씩이기때문에 총 길이의 합의 변화가 없다. 3~5에서의 이동만 총 길이가 늘어나지 않기 때문에 최소치이다. 집의 갯수가 홀수일 경우, 집들의 중간값에있는 위치만이 좌측 우측의 집의 갯수가 동일하므로 유일한 답 집의 갯수가 짝수일 경우 중간값 2개중 작은것이 답(문제의 조건때문에) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..

유니온 파인드 및 dp를 활용하는 문제 누가 누가 친구관계인지 union find를 통해 찾은 뒤, dp의 배낭문제 알고리즘을 통해 어떤 그룹을 선택할 수 있는지 고르는 문제이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; class Node { int cost; int value; public Node(int cost, int value) { this.cost = cost; this.value = value; } } class Main { static int[] paren..

dfs를 활용한 구현문제 로직상으로는 bfs로 풀어도 상관없을 듯 하나, visit처리를 하기 힘들어 dfs로 구현하였다. 한칸씩 이동하며 모든 도형을 검사해야한다. 바로 인접한 칸으로 이동하면서 4칸을 이동하면 된다. 4칸째 이동하면 그간 지나친 경로의 숫자를 다 더한것과 max를 비교하여 max를 갱신한다. ㅗ모양의 블럭은dfs로 해결이 안되어 해당 지점의 상하좌우에있는 블럭들을 모두 더한 뒤 하나씩 빼면서 최대치를 체크한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int[][] ..

처음 접근 방법 : 가장 긴 감소하는 부분순열 - 서류심사 등수, 면접 등수가 주어지기 대문에 배열의 index를 서류심사 등수로, 면접등수를 배열의 값으로 넣어주어 가장 긴 감소하는 수열을 찾으면 될 것 같았다. => 시간초과 n^logN 다음 접근 방법 : 위의 방식과 같이 서류심사 등수로 정렬을 한다(등수를 배열의 index로 활용하기때문에 입력을 받으며 정렬이 된다) 1등의 면접등수를 min으로 기록하고, 그 값보다 작은 값들만 추린다. min값보다 값이 작다면 answer에 1을 더해주고 min값을 해당 값으로 바꿔준다.(이렇게되면 1등보다 면접등수가 낮고, 서류심사등수가 높은 사람만 선택됨) import java.io.BufferedReader; import java.io.IOException..

bfs문제 다른 문제와 다르게 방향과 이동 칸까지 맞춰줘야해서 조금 까다로울 수 있다. 풀이방법은 방향별로 visit을 만들어, 해당 위치와 방향을 방문하였는지 체크하면 된다. 이동 칸의 경우 한칸 앞에서부터 검사를 하여, 칸이 막혀있기 전가지만 큐에 넣어주면 된다. 최소명령으로 이동하는 것 이기때문에 우선순위 큐 를 사용해서 자동정렬시켜준다. 90도씩만 고개를 돌릴 수 있기때문에 이것또한 신경써야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; class Main ..

구현문제 문제에 로직이 다 나와있어서 구현을 어떻게 하느냐가 중요한 문제이다. 톱니바퀴끼리 바라보는것을 검사하고, 조건이 만족하면 돌리면된다. 나는 큐를 두개로 나누어 돌릴바퀴의정보를 담는 큐, 탐색을 위한 큐를 만들었다. 이렇게 한 이유는 톱늬를 미리 돌려버리면 조건을 검사하기 상당히 까다롭기때문에 검사를 마친 뒤 톱니바퀴를 한번에 돌리기 위해서이다. 톱니를 돌리는 것은 간단하게 배열을 이용했다. 길이가 8이라서 굳이 다른 자료구조를 이용할 필요가 없을것이라 생각했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import jav..

간단한 bfs문제 단 불이 번지는것을 어떻게 처리하냐가 관건이다. 처음에는 불이 도달한 배열 (일반적인 bfs문제의 visit배열과 같다), 지훈이가 방문한 노드를 저장하는 배열을 만들어 처리했지만, 다시 생각해보니 굳이 두개를 분리하지말고, 지훈이가 불이 번진곳에 도달 할 수 없게 visit배열을 하나만 만든뒤 불이도달했을때 visit처리를 하면 된다는 것을 발견했다. 지훈이와 불이 겹칠 수 없으니 불의 이동을 먼저 한 후 지훈이를 이동시킨다. 자료구조에 몇번째 이동인지 기록하는 count를 만들어 count에 따라서 절차가 진행되게 만들었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..