Algorithm
[백준] 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..
[백준] 18115 카드 놓기 - Java / Python
[백준] 18115 카드 놓기 - Java / Python
2022.02.12평범한 덱 문제처럼 보이지만... 조금 다르다. 문제 이해가 매우 중요하다. 알고 있는 것 : 스킬을 사용하는 목록 / 스킬 사용 후 결과 알아야 하는 것 : 초기 상태 초기 상태와 명령어를 주고 결과값을 구하는 문제가 대부분인데, 이 문제에서는 초기 상태를 구해야 한다. 스킬을 적용하는 순서를 알고 있으니, 거꾸로 스킬을 적용하며 덱에 숫자를 추가하는 방식으로 해결할 수 있다. 풀이 방법이 생각나지 않을 때, 거꾸로 적용해 보는 것도 생각해보자! Java import java.io.*; import java.util.*; public class temp { public static void main(String[] args) throws IOException { BufferedReader br = ne..
[백준] 2504 괄호의 값 - Java / Python
[백준] 2504 괄호의 값 - Java / Python
2022.02.12자료구조에서 자주 출제되는 괄호 문제이다. 스택을 사용해 해결할 수 있다. 다른 문제와는 다르게 괄호마다 값이 주어지고 이 값들을 계산해야 한다. 1. 여는 괄호가 나오면 스택에 넣어준다. 2. 닫는 괄호가 나오면 pop을 진행한다. 위 부분은 여러 문제에서 다룬 내용과 같지만, 값을 계산하는 부분에서 따로 처리가 필요하다. () 세트가 2 [] 세트가 3이라고 했으니, 여는 괄호가 나올 때 만들어 둔 연산자 변수에 괄호에 따라 2와 3을 곱해주고, 닫는 괄호가 나올 때 만들어 둔 연산자 변수에 괄호에 따라 2와 3을 나눠줘야 한다. 정답 변수를 갱신하는 경우는 한 칸 전의 괄호가 세트를 이룰 경우이다. 예를 들어, ( ( ( ) ) ) 같은 입력이 주어졌을 때, 4번째 반복을 시행할 때 정답 변수를 갱..
[백준] 2346 풍선 터뜨리기 - Java / Python
[백준] 2346 풍선 터뜨리기 - Java / Python
2022.02.11요세푸스 문제처럼 덱을 사용해서 원을 구현하고 풀이하는 문제다. 인덱스 값과 몇 번 띄어넘는지 알려주는 값을 함께 넣어야 하므로 따로 클래스를 만들고 클래스를 덱에 넣어줬다. (여기서 배열을 사용할 수도 있을 것 같다.) List에 항상 기본형 타입만 넣는다는 생각은 버리자!! 그 다음부터는 한 칸 씩 당겨주면서 해결하면 되는데... cycle이 양수일 때는 poll을 진행하면서 이미 한 칸 당겨졌기때문에 한 번 덜 당겨져야 한다. Java import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffere..
[백준] 1620 나는야 포켓몬 마스터 이다솜 - Java / Python
[백준] 1620 나는야 포켓몬 마스터 이다솜 - Java / Python
2022.02.11해시 맵을 사용해서 풀어야 한다. 일반 배열을 사용하게 되면 이름을 입력으로 받을 때 반복문을 돌게 돼 시간 초과가 발생한다. 포켓몬 클래스를 만들어서 객체를 생성하는 방향으로도 풀 수 있을 것 같긴 한데.. 이렇게 하면 시간이 좀 더 오래 걸릴 것 같아 시도하지는 않았다. 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 sb = new StringBuilder(); StringT..
[백준] 1725 히스토그램 - Java
[백준] 1725 히스토그램 - Java
2021.11.17스택에 인덱스를 넣어주고 따로 배열을 설정해 배열에는 직사각형의 높이에 대한 정보를 넣었다. 넓이를 구하는 과정은 이전에 탐색한 직사각형의 높이가 현재 탐색하고 있는 직사각형의 높이보다 높을 때이다. 이 때를 기준으로 지금까지 쌓아온 스택 인덱스에 해당하는 직사각형의 높이들을 현재 탐색하고 있는 높이보다 작거나 같은 높이들을 대상으로 하나씩 pop해주며 넓이를 계산한다. 차례차례 pop을 진행해주며 넓이를 구해주는데, 이 과정은 코드를 참고하자. 이후 pop 과정 수행 후 스택에 남아있는 원소들에 대해서도 처리해주기 위해 다시 pop을 수행한 후 출력해줬다. import java.util.*; public class Main { public static void main(String[] args) { S..
[백준] 1016 제곱ㄴㄴ수 - Java
[백준] 1016 제곱ㄴㄴ수 - Java
2021.11.17얼핏 보기에는 쉬워 보이는 문제이다. 1부터 자기 자신까지 전부 다 나눠보는 방식으로도 접근할 수 있긴 하지만.. 문제 조건에서 주어지는 수의 범위가 너무 크기 때문에 위의 방법대로 접근하면 시간초과 문제가 발생한다. 어떤 수의 제곱에 관련된 수가 있었는데... 소수를 찾을 때 사용했던 에라토스테네스의 체 알고리즘에서 제곱수를 다룬 적이 있었다. 이 알고리즘으로 접근해보자. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); StringBuilder sb = new StringBuilder(); long min = sc.nextLong(); lon..