Stitchhhh

https://www.acmicpc.net/problem/11003 이번 문제는 자료구조 문제입니다. 이 문제를 해결하기 위해서 우선순위 큐도 사용해보았는데 우선순위 큐는 값을 추가 삭제 할 때마다 O(Log N) 시간복잡도가 발생해 시간초과가 발생할 수 있습니다. 그래서 데이터를 추가 삭제하는데 상수시간인 덱을 활용하였습니다. 실제 데이터를 관리하는 배열과 들어온 인덱스를 관리하는 Deque를 사용하였습니다. Deque에 값을 추가할 때마다 최근에 들어온 값과 비교해 최근에 들어온 값이 더 크다면 그 값을 삭제하고, 추가 후에는 처음에 들어온 값부터 인덱스를 검사해 유효 범위인지 확인을 하는 방식으로 풀이하였습니다. import java.io.*;import java.util.*;import java...

https://www.acmicpc.net/problem/2042 이번 문제는 누적합 문제입니다. 누적합 문제의 풀이로는 2가지가 있습니다. 첫 번째는 누적합배열을 사용하는 것이고 두 번째는 세그먼트 트리를 사용하는 방법입니다. 이번에는 두 가지 알고리즘을 큰 차이점만 설명해보겠습니다. 누적합배열은 값이 변경되지 않을 때 효율적입니다. 하지만 값이 변경이 된다면 누적합배열을 다시 갱신해야 하고 변경이 여러번 된다면 시간복잡도가 O(배열길이 * 변경횟수) 이므로 시간초과를 가져올 수 있습니다. 이렇게 값이 변경이 자주 일어난다면 세그먼트 트리를 사용하면 됩니다.세그먼트 트리에서는 자신과 부모 노드만 갱신하여 루트까지 가는 방식으로 O(변경횟수 * log 배열길이)이면 가능합니다. 단점으로는 메모리를 더 사..

Thread이 전에 Thread에 대한 개념과 간단한 사용법을 포스팅을 했었습니다. 이 번에는 좀 더 디테일하게 자바에서 제공하는 비동기에 대해서 학습한 내용과 예시 코드를 정리해보겠습니다. 간단하게 스레드를 생성하고 실행하는 클래스입니다. Runnable, Task를 상속받은 클래스를 사용해도 되고, 익명 객체 + 람다 형식으로도 사용할 수 있습니다. 해당 스레드를 종료하기 위해서는 interrupt() 함수를 사용하면 됩니다. interrupt() 메소드는 스레드가 일시 정지 상태에 있을 때 InterruptedException 예외를 발생시키는 역할을 합니다. 이것을 이용하면 Thread의 run() 메소드를 정상 종료시킬 수 있습니다.public static void main(String[] ar..

Process프로세스란 애플리케이션을 실행하면 운영체제로부터 실행에 필요한 메모리를 할당받아 애플리케이션이 실행되는데, 이를 프로세스라고 합니다. 하나의 애플리케이션은 멀티 프로세스를 만들기도 합니다. 예를 들어 메모장 애플리케이션을 2개 실행했다면 2개의 메모장 프로세스가 생성된 것입니다. Thread운영체제는 두 가징 이상의 작업을 동시에 처리하는 멀티 태스킹을 할 수 있도록 CPU 및 메모리 자원을 프로세스마다 적절히 할당해주고, 병렬로 실행시킵니다. 하나의 프로세스가 두 가지 이상의 작업을 처리하는 방법은 멀티 스레드입니다. 스레드는 하나의 코드 실행 흐름이기 때문에 한 프로세스 내에 스레드가 2개라면 2개의 코드 실행 흐름이 생긴다는 의미입니다. 멀티 프로세스는 운영체제에서 할당받은 자신의 메모..

https://www.acmicpc.net/problem/1012 import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Baekjoon_1012_유기농배추_BFS { static int M, N, K; static int[][] map; static boolean[][] check; static int[] dx = { 0, 0, 1, -1 }; static int[] dy = { 1, -1, 0, 0 }; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int TC = sc.nextInt(); for (i..

https://www.acmicpc.net/problem/4963 import java.io.IOException;import java.util.LinkedList;import java.util.Queue;import java.util.Scanner;public class Baekjoon_4963_섬의개수_BFS { static int w, h; static int[][] map; static boolean[][] visit; static int[] dx = { 1, -1, 0, 0, -1, -1, 1, 1 }; static int[] dy = { 0, 0, -1, 1, 1, -1, 1, -1 }; public static void main(String[] args) throws IOException {..

https://www.acmicpc.net/problem/2667 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.LinkedList;import java.util.Queue;public class Baekjoon_2667_단지번호붙이기_BFS { static int[][] map; static boolean[][] visit; static ArrayList list; static int N, cnt; static int[] dx = { 0, 0, 1, -1 }; ..

https://www.acmicpc.net/problem/9012 문자열을 끊어 받으면서 단순하게 '(' 가 들어오면 stack에 push해주고 ')' 가 들어오면 stack에 pop을 해주는데 stack이 비워져 있으면 'NO' 출력 후 반복문을 종료하면 된다. 반복문이 끝까지 돌았을 경우에는 stack의 사이즈를 가져와 0이면 'YES' 0이 아니면 '('가 ')' 보다 많은 경우 이기 때문에 'NO' 출력을 하면 된다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;public class Baekjoon_9012_괄호 { public static..

https://www.acmicpc.net/problem/10828 입력값 중에서 4개는 하나의 단어로 이루어져있으므로 해당되면 다음 i로 넘어가도록 continue를 해놓고, 남은 한 가지의 경우에는 두 단어 이루어져있으므로 StringTokenizer로 받아서 문제를 풀이하였다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;import java.util.StringTokenizer;public class Baekjoon_10828_스택 { public static void main(String[] args) throws NumberFormatEx..

이 번에는 안전한 멀티 스레드 환경을 만들기 위해 Java에서 제공하는 ConcurrentHashMap에 대해 학습한 내용을 정리해보겠습니다.ConcurrentHashMapConcurrentHashMap은 Java에서 동시성 기능을 제공하는 Map 자료구조입니다. 먼저 간단하게 테스트를 진행한 후에 구현부에 대해서 정리해보겠습니다. 테스트 코드는 다음과 같습니다.import java.util.HashMap;import java.util.concurrent.ConcurrentHashMap;import java.util.concurrent.ExecutorService;import java.util.concurrent.Executors;public class concurrent { public stati..