Algorithm
[백준] 14890 경사로 -Java
[백준] 14890 경사로 -Java
2022.03.01생각할 부분이 많은 구현 문제다. 전체적인 풀이 로직은 다음과 같다. 1. 반복문을 돌면서 같은 숫자가 몇 번째 연속으로 나오고 있는지 확인한다. - 현재 확인하고 있는 수가 이전 수와 같으면 continue - 현재 확인하고 있는 수가 이전 수보다 크면 - 입력받은 L 이상으로 연속되고 있고, 경사로가 중복되지 않으면 경사로를 놓고, 연속을 초기화하며 continue - 현재 확인하고 있는 수가 이전 수보다 작으면 - 뒷부분을 확인한다. 뒷부분의 연속되는 수가 L이상이고, 경사로가 중복되지 않으면 경사로를 놓고 연속을 초기화 하며 continue 2. L이 1일 경우와 1이 아닐 경우를 따로 생각해 줬다. (더 좋은 풀이가 생각나지 않음) - L이 1일 경우는 간단하게 처리할 수 있다. 경사로를 중복해..
[백준] 15683 감시 -Java
[백준] 15683 감시 -Java
2022.02.21어떻게 모든 경우를 다 고려할지, 좌표계를 어떻게 설정할 지.. 많은 고민이 필요한 문제이다. 주의할 점은 다음과 같다. 1. CCTV클래스를 따로 만들고 Object배열에 넣어서 접근하자. 2. 탐색 함수를 정의할 때 재귀 느낌으로 작성해서 모든 경우를 고려할 수 있도록 하자. 3. 백트래킹을 고려해서 배열 복사 함수를 정의하자. 4. 감시카메라로 감시할 수 있는 구역을 표시하는 부분을 함수로 정의하고 방향에 따라 재활용하자. Java import java.util.*; import java.io.*; public class Main { static int N; static int M; static int[][] map; // 사무실 static int ret = 0; // 정답 static int c..
[백준] 14499 주사위 굴리기 -Java
[백준] 14499 주사위 굴리기 -Java
2022.02.20문제 이해가 매우 중요하다. 차근차근 생각해보자. 1. 문제에서 주어지는 좌표계를 먼저 이해하자. 문제에서 주어지는 첫 번째 예제에 대해 생각해보자. 지도는 이차원 배열로 저장한다. int[][] map = new int[N][M]; 이런 형태로 저장하게 되는데 이 배열에 대한 좌표계는 좌측 그림과 같아진다. x와 y를 설정한다고 하면 (1,0)위치는 3이 되고 (2,1)위치는 6이 된다. 2. 주사위의 회전을 이해하자. 주사위의 각 요소를 인덱스로 생각하고 회전을 진행하자. 주사위의 요소는 6가지이므로 크기가 6인 배열을 주사위로 취급한다. 초기 주사위에서 오른쪽으로 회전을 진행한 후의 모습이다. 처음에는 인덱스 1이 윗부분, 인덱스 6이 아랫부분을 차지하고 있고, 회전을 진행한 후에는 인덱스 4가 윗..
[백준] 14891 톱니바퀴 -Java
[백준] 14891 톱니바퀴 -Java
2022.02.19처음에는 Deque를 사용해서 회전을 구현하면 되겠다고 생각했다. char타입이나 int타입을 담을 수 있는 덱을 4개 만들고, 조건에 따라 회전시켜가면서 답을 구하면 되지 않을까..? 라는 생각으로 풀었는데, 문제에서 사용하는 0과 1에 집중하면 비트 연산자로 회전을 구현하고 문제를 해결할 수 있었다. https://www.youtube.com/watch?v=MzywM54p1y0 풀이에 참고한 동영상 유튜브에서 관련 풀이를 찾아보고 비트 연산자를 사용해서 다시 풀어봤다. Java 전체적인 흐름은 다음과 같다. 1. 회전할 톱니바퀴를 기준으로 좌측과 우측에 붙어있는 극성을 확인한다. (이 때 회전 방향은 배열을 생성해서 처리) 2. 극성이 같으면 회전 방향 배열을 업데이트하지 않고, 극성이 다르면 배열을..
[백준] 1850 최대공약수 -Java
[백준] 1850 최대공약수 -Java
2022.02.18일반적인 접근방법으로 풀면 메모리 초과가 발생하거나 시간 초과가 발생한다. 새로운 방법을 생각해보자. 입력값으로 들어온 숫자들에 대해 111... 로 변환하지 않고 최대공약수를 구해 보면, 출력값은 111... 로 변환했을 때의 출력값과 어떠한 연관관계를 찾을 수 있다. 변환 전 숫자의 최대공약수만큼 1을 추가해서 출력해주면 된다. Java import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder ..
[백준] 10994 별 찍기 - 23 - Java
[백준] 10994 별 찍기 - 23 - Java
2022.02.18이차원 배열을 생성하고 문제의 조건에 따라 별을 찍었는데.. 풀고 난 다음 코드를 다듬지 않아서 좀 지저분하다.. 별찍기 문제에서 "출력 형식이 잘못됐습니다"오류를 자주 볼 수 있는데, 이 경우는 이차원 배열을 출력할 때 불필요한 공백 부분까지 출력하게 되어 발생하는 경우가 많다. 이번에도 출력은 제대로 나오는데, 출력 형식이 잘못됐다고 해서 출력부분을 조작해서 공백 출력을 막아서 해결했다. Java 1. 최상단과 최하단 2. 가운데 3. 나머지 위의 세 가지 경우에 따라 별을 찍었다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { Buffe..
[백준] 10994 별 찍기 - 19 -Java
[백준] 10994 별 찍기 - 19 -Java
2022.02.17간단한 별찍기 문제를 풀 때는 반복문을 사용해서 바로바로 풀 수 있지만, 복잡한 별찍기 문제를 풀 때는 이차원 배열을 설정해서 규칙에 맞게 찍는 것이 편하고, 더 복잡한 별찍기 문제에서는 별을 찍는 함수를 만들고 규칙에 따라 재귀적으로 호출해야 한다. 이번 문제도 별찍기 중에서는 꽤 복잡한 편이고, 별찍기 함수와 재귀를 이용해서 풀었다. Java 수평과 수직 방향으로 별을 찍은 다음, N을 감소시켜 N이 1이 될 때 까지 재귀적으로 함수를 호출했다. import java.util.*; import java.io.*; public class Main { static char[][] arr; public static void main(String[] args) throws IOException { Buffe..
[백준] 22252 정보 상인 호석 -Java
[백준] 22252 정보 상인 호석 -Java
2022.02.16정보를 ArrayList에 저장하고 sort를 통해 정렬한 후 결과값을 찾을 수도 있겠지만, Q의 범위가 100,000이니 sort를 진행할 시 시간 초과가 나올 것이다. 기본으로 sort가 되어 있는 heap자료구조를 통해 구현된 PriorityQueue를 사용해서 문제를 해결하자. 1을 입력받았을 때 고릴라의 이름과 이름에 따른 우선순위 큐를 만들어야 한다. HashMap을 사용해서 두 가지 정보를 한 번에 저장하자. 2를 입력받았을 때 입력받은 고릴라에게서 정보를 구매해야 한다. 1에서 만든 HashMap이 있을 경우에 정보를 가져오자. Java import java.util.*; import java.io.*; class Main { public static void main(String[] ar..
[백준] 2075 N번째 큰 수 -Java / Python
[백준] 2075 N번째 큰 수 -Java / Python
2022.02.16그냥 배열을 생성해서 sort로 정렬해준 뒤 인덱스에 맞춰서 출력해줘도 시간 초과가 나오지 않는다. 그래도 우선순위 큐와 슬라이싱 윈도우 알고리즘을 활용해서 좀 더 효율적으로 풀어보자. Java 일단 우선순위 큐만 사용했을 때 풀이이다. import java.util.*; import java.io.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N = Integer.parseInt(br.readLine()); PriorityQueue pq = ne..
[백준] 7662 이중 우선순위 큐 -Java
[백준] 7662 이중 우선순위 큐 -Java
2022.02.16하나는 최소 큐, 하나는 최대 큐로 정렬되어있는 우선순위 큐 두 가지를 선언해 풀었었는데, 시간 초과가 나왔다. 두 가지 큐를 사용하므로 최소 큐에서 값을 제거할 때 최대 큐에서도 같이 값을 제거해줘야 하는데 여기서 poll함수와 remove함수를 함께 쓰게 되서 시간복잡도가 O(N)이 나와 시간초과가 발생하게 된다. poll함수에서는 문제가 없지만, remove함수를 사용할 때는 순차적으로 접근해서 발생하는 문제다. 문제를 해결하기 위해 TreeMap자료구조를 사용했다. 객체를 선언하면 자동으로 정렬이 되는 자료구조인데, TreeMap을 사용해 키 값을 기준으로 트리를 정렬시켜 저장하고 트리 형태로 빠르게 탐색을 진행할 수 있다. Java 맞게 풀었는데 계속 틀렸다고 하길래.. 다시 보니 StringT..
[백준] 4358 생태학 -Java / Python
[백준] 4358 생태학 -Java / Python
2022.02.15입력의 마지막에 대한 조건이 없는 문제다. BufferedReader를 사용할 경우 입력값이 null이거나 공백일 경우 입력을 종료하도록 작성했다. 해시 맵 느낌이 강하게 드는 문제이다. key값으로는 나무 이름을, value값으로는 이름이 나오는 횟수를 저장하고 입력이 끝난 후에 key값을 기준으로 정렬을 진행한 뒤 key값에 대한 비율을 출력해 주면 된다. Java key값에 대해 정렬을 수행할 때 keySet() 함수를 사용해서 Object타입의 배열을 만들어주고 sort함수로 정렬을 수행했다. import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException..
[백준] 17298 오큰수 -Java / Python
[백준] 17298 오큰수 -Java / Python
2022.02.14그냥 읽고 손 가는대로 풀면 시간초과로 오답이 된다. 빠르게 처리할 수 있는 방법을 생각해 보자. 스택을 잘 활용하면 빠르게 처리할 수 있다. 일단 수를 담는 스택과 인덱스를 저장하는 스택을 만들자. 입력값을 배열에 넣어준 후에 차례대로 값을 검사한다. 값을 검사하면서 현재 검사하고 있는 값이 이전의 값보다 작으면 스택에 인덱스와 값을 넣어 준다. 만약 현재 검사하고 있는 값이 스택의 가장 윗부분의 값보다 크면 스택에서 값을 뺀다. 이 작업을 스택의 가장 윗부분의 값이 더 커질 때 까지 반복한다. 위의 작업이 끝나면, 마지막 처리로 스택에 남아있는 인덱스를 -1로 채워준다. 스택을 이렇게 활용하는 방법도 있다.. 기억해두자. Java import java.io.*; import java.util.*; p..