Stitchhhh

비트마스킹이번 포스트에서 정리할 주제는 비트마스킹입니다. 비트마스킹은 알고리즘 문제에서 자주 등장하는 기법 중 하나로 이진수(bit)를 활용해 여러 개의 상태를 한 개의 정수로 표현할 수 있도록 도와주며, 공간 절약과 연산 최적화 측면에서 매우 유용합니다. 예시는 다음과 같습니다.n = 5 → 101→ 0, 2번 인덱스가 켜져 있다라는 의미로 해석이 가능합니다.비트마스킹 활용 사례부분 집합을 효율적으로 순회할 때중복 방문을 피하는 DP/DFS에서 방문 여부를 저장할 때상태를 배열 대신 정수 하나로 표현하고 싶을 때메모리/성능 최적화가 필요할 때 기본 연산 정리표 연산 목적 표현식 설명 예제 입력 / 결과 예시 i번째 비트 켜기 (Set)S = S | (1 i번째 자리를 1로 설정S = 0; i = 2..

이번 포스트에서는 Character, String, StringBuilder에 대해서 정리해보겠습니다. 해당 포스트의 카테고리를 Java, 알고리즘에서 고민을 했는데 Character, String, StringBuilder의 주요 메소드와 시간복잡도를 함께 설명할 계획이기 때문에 알고리즘 카테고리로 선정하였습니다.Character, String, StringBuilderJava에서 문자열 및 문자 데이터를 처리할 때 주로 사용하는 클래스는 다음 세 가지입니다:Character: 문자(char) 하나를 다루는 클래스String: 불변(immutable) 문자열StringBuilder: 가변(mutable) 문자열, 성능 중심Characterchar 타입을 감싸는 래퍼 클래스이며, 문자 하나를 판단하거나 ..

https://www.acmicpc.net/problem/11403  문제에서 요구하는 바는 시작점으로 부터 갈 수 있는 목적지를 2차원 배열을 통해 표현하는 것 입니다. 여기서 중요한 점은 자기 자신으로 돌아올 수 있는지 체크하는 것도 중요합니다. 인접리스트를 통해 그래프를 구현하였으며, 모든 정점을 시작점에 놓아 갈 수 있는 지점을 배열에 체크 한 후에 값을 저장하면 쉽게 풀 수 있습니다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.LinkedList;import java.util.Queue;import j..

https://www.acmicpc.net/problem/23326 이 문제에서 원하는 것은 현재 도현이의 위치로부터 가장 가까운 명소를 찾는 것인데, 무조건 시계 방향으로만 돌아야만 합니다. 그래서 명소를 관리하기 위해 TreeSet 자료구조를 사용하였습니다. 그 이유로는 TreeSet에서는 X보다 큰 값 중에 가장 작은 값을 반환해주는 함수를 제공해주기 때문입니다. 1. 1의 경우에는 TreeSet에 저장되어 있으면 삭제하고, 저장되어 있지 않으면 추가를 합니다. 2.  2의 경우에는 도현이의 위치를 옮겨주어야 하는데 아무리 큰 수가 오더라고 결국 한 바퀴를 돌게 되면 제자리이기 때문에 나머지를 계산해 최종적으로 움직여야 하는 칸을 계산하고 크기를 넘을 경우 N으로 나누어 주면 됩니다. 3.  3의 ..

https://www.acmicpc.net/problem/21939  처음에 문제를 접했을 때 난이도 순으로 정렬을 하고 난이도가 같으면 문제 번호로 정렬을 하면 손쉽게 전체를 정렬할 수 있다고 생각하였습니다. 그래서 하나의 클래스를 만들고 이를 TreeSet을 통해 정렬을 했습니다. 그런데 solved 명령어를 해결하기 위해서는 문제 번호에 해당하는 TreeSet에 저장된 값을 알아야만 삭제를 O(Log N)에 할 수 있기 때문에 이를 관리하는 HashMap을 생성하였습니다. HashMap에 키로 문제 번호를 받고 값으로 TreeSet에 저장된 값을 저장하는 방식으로 풀이를 하였습니다. import java.io.BufferedReader;import java.io.IOException;import j..

https://www.acmicpc.net/problem/15681  이번 문제는 하나의 트리에서 서브트리의 루트를 정했을 때 그 트리에 포함된 정점을 출력하는 문제입니다. 기본적인 트리 문제에 조금 더 생각을 하면 될 것 같습니다. 매번 서브 트리 루트가 정해질 때 마다 계산을 하기에는 정점의 수가 최대 500,000 쿼리의 수가 500,000 이고 트리 전체는 변하지 않기 때문에 dp를 통해 미리 계산을 하는 식으로 해결을 하였습니다. import java.io.*;import java.util.*;public class Backjoon_15681_트리와_쿼리 { public static void main(String[] args) throws IOException { Buffere..

https://www.acmicpc.net/problem/2623  이번 알고리즘은 위상정렬입니다. 위상 정렬은 그래프에서 방향을 가지는 간선으로 이루어져 있으며 사이클이 없는 것을 말합니다.간단하게 설명을 하자면 A를 하기 위해서 B를 우선 해야 한다는 가정이 있다면 A, B와의 관계를 B -> A로 나타낼 수 있습니다. 문제에서는 위의 개념만 적용하면 바로 풀이를 할 수 있습니다. 서로의 관계를 M번 만큼 제시하는 것 말고는 크게 신경 써야 하는 부분은 없습니다. 우선 시 하는 것이 없는 것을 먼저 큐로 넣고 큐에서 나오면서 자신을 필요로 하는 정점을 가져오고 이 정점의 우선 시 하는 갯수에 -1을 하면 됩니다. 여기서 0이 되면 우선 시 하는 정점을 모두 진행했기 때문에 큐에 넣어주는 방식으로 해결..

https://www.acmicpc.net/problem/21276 해당 문제에서는 제일 먼저 가문의 개수와 가문의 시조를 구해야 합니다. 가문의 개수를 구하는 방법은 자신을 바라보는 정점이 없는 정점 즉 루트가 몇 개인지 확인하고 그 값을 출력을 하면 됩니다. 그래서 가문의 시조를 관리하는 리스트를 만들어 이를 해결하여습니다. 위 말을 조금 더 쉽게 생각하면 부모가 있어야 자식이 있기 때문에 부모 -> 자식 관계로 생각을 하면 합니다. 즉 최상위 조상은 누구도 자신을 바라보지 않습니다. 그리고 자식들을 출력을 해야하는데 이 또한 리스트를 활용하여 각 정점마다 자식을 추가 해주었습니다.for(int i = 0 ; i q = new LinkedList(); int idx = map2.get(strArr[..

https://www.acmicpc.net/problem/1647 이번 문제로 MST 알고리즘입니다. 다만 MST에서 살짝 변형을 준 문제라고 생각해도 될 것 같습니다. MST인 경우에는 모든 집을 연결하는 최소한의 간선 합을 구하는 것인데 여기서는 집을 두 개의 집단으로 나눠야 하기 때문에 최소한의 간선들 중 제일 큰 값을 빼면 됩니다. 그러면 A구역 B구역으로 자연스럽게 나누어질 것 입니다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.PriorityQueue;import java.util.StringTokeniz..

https://www.acmicpc.net/problem/1197 이 번에 풀어본 문제의 종류는 MST(최소 신장 트리)입니다. 최소 신장은 주어진 그래프의 부분 그래프 중 모든 정점을 포함하는 트리를 말합니다. 여기서 MST란 이를 최소한의 비용(기존 간선)으로 이루어진 그래프입니다. MST 알고리즘을 풀이는 2가지 대표 알고리즘이 있습니다. 크루스칼 알고리즘과 프림 알고리즘이 존재하는데 크루스칼을 활용해 문제를 풀이해보겠습니다. 크루스칼 알고리즘은 유니온 파인드라는 알고리즘을 사용합니다. 유니온 파인드는 서로의 집합을 확인하는 알고리즘입니다. parent[] 배열을 통해 최상위를 확인하여 서로 같은 집단인지 확인하며 문제를 풀이하면 됩니다. import java.io.BufferedReader;imp..