Algorithm
[Baekjoon] 16985: Maaaaaaaaaze
[Baekjoon] 16985: Maaaaaaaaaze
2023.06.14문제 아... 너무 길다 다음 링크를 통해 자세한 내용을 확인해보자. [Baekjoon] 16985: 매애애애애애애애애즈 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 3차원 미로 찾기 문제이다. 여기서 조건은 다음과 같다. 판은 회전할 수 있다. 판은 순서가 바뀔 수 있다. 꼭짓점이면서 1인 곳으로만 들어갈 수 있다. 정반대 꼭짓점으로만 나올 수 있다. 위를 고려하면서 풀면 그냥 풀린다. 스터디원 모두 막판 원큐 세레모니를 보여주고 있다. 풀이 내 풀이 import java.io.Bu..
[Baekjoon] 15732: 도토리 숨기기
[Baekjoon] 15732: 도토리 숨기기
2023.06.14문제 욕심 그득한 다람쥐가 도토리를 나름 머리써서 숨기는 걸 찾는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class Q15732 { static class Dotori { private int start; private int end; private int gap; public Dotori(String start, String end, String gap) { this.start = Integer.parseInt(start); this.end = Int..
[Baekjoon] 16947: 서울 지하철 2호선
[Baekjoon] 16947: 서울 지하철 2호선
2023.06.14문제 순환선의 특정 역과 순환선이 아닌 역 사이의 거리를 구하는 문제이다. 예를 들면 까치산은 순환선과 거리가 4, 도림천은 거리가 1이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q16947 { private static int n; private static List graph; private static boolean[] visited; private static int[] cycle; private static boolean[] check; private static int[] distances; p..
[Baekjoon] 22856: 트리 순회
[Baekjoon] 22856: 트리 순회
2023.06.14문제 유사 중위 순회를 구현하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q22856 { private static int n; private static int[][] tree; private static int visitCount; private static int lastNode; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); n = In..
[Baekjoon] 15898: 피아의 아틀리에 ~신비한 대회의 연금술사~
[Baekjoon] 15898: 피아의 아틀리에 ~신비한 대회의 연금술사~
2023.05.10문제 최고의 폭탄을 제조하는 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q15898 { private static final String WHITE = "W"; private static final String YELLOW = "Y"; private static final String GREEN = "G"; private static final String RED = "R"; private static final String BLUE = "B"; private static Map qualities; ..
[Baekjoon] 21611: 마법사 상어와 블리자드
[Baekjoon] 21611: 마법사 상어와 블리자드
2023.05.10문제 상하좌우로 블리자드를 쏴대는 상어 문제이다. 예시가 궁금하다면 여기서 확인하자. [Baekjoon] 21611: 마법사 상어와 블리자드 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q21611 { private static BufferedReader..
[Baekjoon] 2176: 합리적인 이동경로
[Baekjoon] 2176: 합리적인 이동경로
2023.05.10문제 문제를 읽자마자 머리를 붙잡았다. 설명이 참,,, 심오하다,, ,,,? 풀이나 알아보자. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Q2176 { private static final List graph = new ArrayList(); private static long[] weights; private static int[] counts; public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..
[Baekjoon] 1943: 동전 분배
[Baekjoon] 1943: 동전 분배
2023.05.10문제 돈이 주어지면 반으로 정확히 나눌 수 있는지 묻는 배낭 문제이다. 풀이 내 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public static void main(String[] args) throws IOException { for (int i = 0; i < 3; i++) { System.out.println(distribute() ? 1 : 0); } } privat..
[Algorithm] 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)
[Algorithm] 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)
2023.04.07펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)? 펜윅 트리는 세그먼트 트리의 변형으로 세그먼트 트리보다 메모리를 더 절약할 수 있다. 또, 갱신을 O(log n)의 시간에 수행할 수 있으며, 세그먼트 트리보다 구현이 쉽다는 장점이 있다. 구성 펜윅트리는 일반적인 세그먼트 트리와 다르게 기존 배열과 같은 크기로 구성할 수 있다. 펜윅 트리는 다음과 같이 구성한다. 여기서 노란 블럭은 기존 배열, 초록 블럭은 트리 배열이다. 0이 아닌 최하위 비트 펜윅 트리를 초기화하고 업데이트하기 위해선 값을 어떻게 인덱싱하는지 알아야한다. 이때, 0이 아닌 최하위 비트 값을 더해주는 방식을 취한다. 먼저 각 비트의 0이 아닌 최하위 비트를 구하는 방법을 알아보자. 예를 들어 3, 6,..
[Algorithm] 외판원 순회 문제(Traveling Salesman Problem)
[Algorithm] 외판원 순회 문제(Traveling Salesman Problem)
2023.04.06외판원 순회 문제(TSP) 외판원 순회 문제(TSP)는 조합 최적화 문제 일종으로, NP-난해 집합에 속하기 때문에 계산 이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다. 즉, 아직까지 다항 시간에 해결할 수 있는 해결책을 못찾았으며 해결하지 못한다는 것도 증명하지 못했다. 외판원 문제의 내용은 다음과 같다. 예를 들어, 어떤 외판원이 n개의 도시를 방문할 계획을 갖고 있다고 하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위해 외판원이 출발하는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 경로를 찾고자 할 때, 어떻게 찾을 수 있을까? 만약 20개의 도시가 있을 때 정답을 찾기 위해 다녀야 하는 총 경로 수는..
[Algorithm] 보이어-무어 알고리즘(Boyer-Moore Algorithm)
[Algorithm] 보이어-무어 알고리즘(Boyer-Moore Algorithm)
2023.04.04보이어-무어 알고리즘(Boyer-Moore Algorithm) 보이어-무어 알고리즘은 문자열 검색에 사용되는 알고리즘이다. 보이어-무어 알고리즘은 일반적인 상황에서 문자열은 앞부분보다 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 때문에 오른쪽 끝부터 비교하게 된다. 보이어 무어 알고리즘은 다음과 같이 이동할 칸의 개수를 저장해 놓은 테이블을 미리 만들어 저장해 놓는다. 오른쪽 끝과 일치하지 않는 경우 오른쪽 끝 문자가 일치하지 않는다면, 패턴에 해당 문자가 존재하는지 검사한다. 만약 패턴에 존재하지 않는다면, 패턴의 길이만큼 패턴을 이동시킨다. 만약 패턴에 존재한다면, 패턴의 오른쪽 끝에서부터 그 문자까지의 칸 수를 세서, 해당 칸수만큼 이동시킨다. 오른쪽 끝과 일치하는 경우 오른쪽 끝 문..
[Baekjoon] 11401: 이항 계수 3
[Baekjoon] 11401: 이항 계수 3
2023.03.30문제 간단히 이항계수 (n k)를 구하는 문제이다. 풀이 대표 풀이 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Q11401 { public static final int MOD = 1000000007; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] nk = br.readLine().split(" "); int n = Integer.parseInt(nk[0..