분류 전체보기
[백준] 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..
[백준] 1991 트리 구조 -Java / Python
[백준] 1991 트리 구조 -Java / Python
2022.02.14비선형 자료구조인 트리 구조를 알아야 풀 수 있는 문제다. 트리 구조는 노드를 사용해서 데이터를 저장하고, 노드는 저장된 값, 하위에 있는 여러 가지 노드들로 구성된다. 여기서 하위에 있는 노드의 개수가 2개 뿐인 노드를 이진트리라고 한다. 트리의 순회 방법에는 세 가지가 있다. 1. 전위 순회 루트 노드를 순회한 다음 왼쪽 하위를 거쳐 오른쪽 하위로 순회하는 방법. 2. 중위 순회 왼쪽 하위 노드부터 시작해 루트 노드까지 순회하고 오른쪽 하위 노드부터 다시 순회하는 방법. 3. 후위 순회 왼쪽부터 시작해 가장 하위 계층에 있는 노드를 순회한 다음 오른쪽을 거쳐 루트 노드로 순회하는 방법 트리에 대한 개념은 어렵지 않지만, 이 개념만을 가지고 코드로 구현하려면 막막하다.. Java 트리 구조를 구현할 때..
[백준] 1655 가운데를 말해요 - Java / Python
[백준] 1655 가운데를 말해요 - Java / Python
2022.02.13시간 제한을 보고 당연히 배열로 푸는건 시간 초과가 걸릴것 같아 ArrayList로 접근했다. 그런데 ArrayList도 시간 초과가 나온다.. 다른 분들의 풀이를 보고 겨우 이해했다. 문제에서 의미하는 중앙값을 뽑아내기 위해 하나는 최대 힙, 하나는 최소 힙으로 두 가지의 우선순위 큐를 선언한다. 최대 힙부터 시작해서 하나씩 숫자를 넣어 주는데, 최대 힙의 루트 노드값이 최소 힙의 루트 노드값보다 크면 두 노드값을 바꿔줘야 하고, 입력에 대해서는 최대 힙의 루트 노드값을 출력해 주면 된다. 이런 생각은 어떻게 하는지.. 수능 수학을 공부할 때 참신한 발상이 필요한 30번 문제를 보는 것 같다.. "중앙값을 빠르게 구할 때 두 가지 우선순위 큐를 만들어서 구하는 방법이 있다" 정도만 기억해 두고, 주기적..
[백준] 11286 절댓값 힙 - Java / Python
[백준] 11286 절댓값 힙 - Java / Python
2022.02.13https://13months.tistory.com/151 [백준] 11279 최대 힙 - Java / Python 힙 자료구조를 사용해서 푸는 문제다. 힙을 사용해서 우선순위 큐를 구현해 풀자. 구현은 어렵지 않기 때문에 힙을 알고 있으면 쉽게 풀 수 있고, 모르면 힘들게 풀거나 틀리는.. 문제이다. Java 13months.tistory.com 전반적인 구성은 최대 힙 문제와 같지만, 절댓값이 같을 때에 대해서 처리 해 줘야 한다. Java 우선순위 큐를 구현할 때 인자에 람다식으로 익명 함수를 넣어줬다. 절댓값이 같은 경우 그 중에서 값이 더 작은 음수를 기준으로 우선순위 큐에 대해 오름차순 정렬을 진행하고, 아닌 경우에는 절댓값을 기준으로 오름차순 정렬을 진행한다. import java.io.*;..
[백준] 1927 최소 힙 - Java / Python
[백준] 1927 최소 힙 - Java / Python
2022.02.13https://13months.tistory.com/151 [백준] 11279 최대 힙 - Java / Python 힙 자료구조를 사용해서 푸는 문제다. 힙을 사용해서 우선순위 큐를 구현해 풀자. 구현은 어렵지 않기 때문에 힙을 알고 있으면 쉽게 풀 수 있고, 모르면 힘들게 풀거나 틀리는.. 문제이다. Java 13months.tistory.com 위 문제와 똑같다. Java 최대 힙 코드에서 reverseOrder()를 지워주면 된다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..
[백준] 11279 최대 힙 - Java / Python
[백준] 11279 최대 힙 - Java / Python
2022.02.13힙 자료구조를 사용해서 푸는 문제다. 힙을 사용해서 우선순위 큐를 구현해 풀자. 구현은 어렵지 않기 때문에 힙을 알고 있으면 쉽게 풀 수 있고, 모르면 힘들게 풀거나 틀리는.. 문제이다. Java 우선순위 큐의 기본 값은 최소 힙이기 때문에 Collections.reverseOrder()를 인자에 넣어 최대 힙으로 바꿔주자. 힙 자료구조를 몰라도 유틸을 사용하면 풀 수 있지만.. 이번 기회에 이론도 제대로 잡고 가자. https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값..
[백준] 17413 단어 뒤집기 2 - Java / Python
[백준] 17413 단어 뒤집기 2 - Java / Python
2022.02.13스택을 사용해서 어떻게 풀어볼 수 있지 않을까?라는 생각이 드는 문제였다. 그런데 스택으로 어떻게 접근해야 할지 감이 안 와서.. 문제에서 하라는 대로 구현했다. 1. 태그는 뒤집으면 안된다. 2. 띄어쓰기를 기준으로 단어를 구분하고 단어를 뒤집는데, 마지막 단어에는 띄어쓰기가 없다. 3. 단어 다음 여는 괄호가 등장해도 단어로 구분하고 뒤집는다. 위 세 가지에 집중해서 구현하면 어렵지 않게 풀 수 있는 문제였다. Java 조건에 맞춰 구현하다 보니.. 코드가 좀 더러워졌다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedRea..