분류 전체보기

    [Java] 백준 2143 (두 배열의 합) Gold 3
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2143 (두 배열의 합) Gold 3

    Problem : https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net Approach 이분탐색 문제이다. 먼저 A 배열 과 B 배열의 요소들로 부 배열의 합들을 구하여 각각 aSum, bSum 에 저장한다. 그런 후, aSum에 있는 각 요소들에 대하여 더해서 T가 되는 요소를 bSum에서 구할 것이다. 그러기 위해 일단 bSum을 정렬한다. aSum의 각 요소들에 대해 ..

    [Java] 백준 2096 (내려가기) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2096 (내려가기) Gold 4

    Problem : https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net Approach 간단한 DP 문제로 생각하고 풀었다. DP의 점화식은 문제에서 알려주고 있기 때문에 따로 언급은 하지 않겠다. 최솟값 배열과 최댓값 배열을 따로 두어, 한 번 순회하며 두 값을 각각 갱신하였다. 마지막 줄을 검사하여 최종최댓값과 최종최솟값을 구하면 된다. Code import java.io.*; import java.util.StringTokenizer; /** * No.209..

    [Java] 백준 2056 (작업) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 2056 (작업) Gold 4

    Problem : https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Approach 기본적인 위상정렬 (Topological Sort) 문제였다. 위상 정렬에서는 선행되어야 하는 것들의 개수를 저장하는 inDegree 배열이 필요하다. 먼저 inDegree[a] 를 a작업이 수행되기까지 선행되어야 하는 작업의 수라고 정의한다. 그렇게 inDegree를 구성하고, inDegree가 0인 것..

    [Java] 백준 1987 (알파벳) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1987 (알파벳) Gold 4

    Problem : https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net Approach 이미 지나온 알파벳은 지날 수 없는 DFS 문제이다. 이미 지나온 알파벳은 지날 수 없다는 것을 확인하기 위해 visited 배열과 더불어 alpha 배열을 따로 두었다. 풀이 방법은 다음과 같다. 좌측 상단(0, 0)에서 시작하여 DFS를 수행한다. DFS 를 수행하며 지나온 알파벳을 기록한다. 이미 지나온 알파벳이라면 그 칸으로는 더이상 탐색하지 않는다..

    Head First: Design Patterns - 이터레이터 패턴(Iterator Pattern)
    Algorithm/Baekjoon Online Judge

    Head First: Design Patterns - 이터레이터 패턴(Iterator Pattern)

    디자인 패턴: 이터레이터 패턴(Iterator Pattern) 이 포스팅은 Head First: Design Patterns 책을 보고, 개인적으로 정리한 포스팅입니다. Iterator Pattern 이란? 이터레이터 패턴(Iterator Pattern: 반복자 패턴)은 컬렉션 구현 방법을 노출시키지 않으면서도 그 집합체 안에 들어있는 모든 항목에 접근할 수 있게 해주는 방법을 제공해준다. 이 패턴을 이용하면 집합체 내에서 어떤 식으로 일이 처리되는지에 대해서 전혀 모르는 상태에서 그 안에 들어있는 모든 항목들에 대해 반복작업을 수행할 수 있다. 또한, 이터레이터 패턴을 사용하면 모든 항목에 일일이 접근하는 작업을 컬렉션 객체가 아닌 반복자 객체에서 맡게된다는 것이 중요한 점인데, 이는 집합체의 인터페이..

    [Java] 백준 1967 (여행 가자) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1967 (여행 가자) Gold 4

    Problem : https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net Approach 유니온 파인드(Union-Find) 를 활용한 문제였다. 플로이드 와샬 알고리즘으로도 풀이가 가능하다고 한다. (여기서는 다루지 않는다.) 주어진 여행 경로가 어떤 형식으로든 서로 연결되어 길이 존재한다면 가능한 여행경로라고 볼 수 있다. 따라서 입력데이터를 받아 도시 사이에 길이 있다면 같은 집합으로 묶는 작업을 진행한다. 그런 뒤에 여행경로에 있는 모든 도시들..

    [Java] 백준 1967 (트리의 지름) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1967 (트리의 지름) Gold 4

    Problem : https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net Approach 트리를 가장한 DFS/BFS문제이다. 트리의 지름은 가장 먼 두 노드 사이의 길이를 구하면 된다. 가장 먼 두 노드 사이의 길이는 다음과 같이 구할 수 있다. 임의의 점에서 가장 먼 노드 A를 구한다. A에서 가장 먼 노드 B를 구한다. A - B 사이의 길이가 가장 먼 두 노드 사이의 길이가 된다. 머릿속에서나 잠깐 생각해보면 쉽게 이해가 갈..

    Head First: Design Patterns - 템플릿 메소드 패턴(Template Method Pattern)
    Book/Design Patterns

    Head First: Design Patterns - 템플릿 메소드 패턴(Template Method Pattern)

    디자인 패턴: 템플릿 메소드 패턴(Template Method Pattern) 이 포스팅은 Head First: Design Patterns 책을 보고, 개인적으로 정리한 포스팅입니다. Template Method Pattern 이란? 템플릿 메소드 패턴(Template Method Pattern)에서는 메소드에서 알고리즘의 골격을 정의한다. 알고리즘의 여러 단계 중 일부는 서브클래스에서 구현할 수 있다. 템플릿 메소드를 이용하면 알고리즘의 구조는 그대로 유지하면서 서브클래스에서 특정 단계를 재정의할 수 있다. 템플릿(Template)이란 일련의 단계들로 알고리즘을 정의한 메소드이다. 여러 단계 가운데 하나 이상이 추상 메소드로 정의되며, 그 추상 메소드는 서브클래스에서 구현된다. 이렇게 함으로써 서브클..

    [IntelliJ] VisualVM 연동 + 사용방법
    IDE

    [IntelliJ] VisualVM 연동 + 사용방법

    내 환경은 다음과 같다. 다른 버전에서는 차이가 있을 수 있다. IntelliJ IDEA 2020.2.2 Java 11 Windows 10 나는 코딩테스트를 준비하며, 내가 사용한 로직이 얼만큼의 메모리를 쓰는지 확인하기 위해 설치했다. 그 외에도 많은 정보를 제공해 주는데, 그에 관해서는 마지막 단락의 내가 참고했던 블로그를 방문하면 좋을 것이다. VisualVM 설치하기 https://visualvm.github.io/download.html VisualVM: Download First Steps Unzip the downloaded archive. The archive already contains the top-level visualvm directory. Start VisualVM by invo..

    [Java] 백준 1918 (후위 표기식) Gold 4
    Algorithm/Baekjoon Online Judge

    [Java] 백준 1918 (후위 표기식) Gold 4

    Problem : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net Approach Stack을 이용하여 풀이하는 문제이다. 입력으로 주어진 문자열을 하나씩 읽으면서 각 문자에 대해 우선순위를 매겨서 하나씩 뽑는 형태이다. 다음과 같이 4개의 경우가 발생한다. 참고로 스택엔 여는괄호와 연산자만 들어가게끔 구현한다. 스택의 문자들은 각각 우선순위가 매겨져 있으며, (가 0, +-가 1, */가 2로 숫자가 높을수록 우선이 된다. stack..

티스토리툴바