Stitchhhh

https://www.acmicpc.net/problem/1504 문제에서는 시작점이 무조건 1, 도착점이 무조건 N으로 되어있으며 경유해야할 정점이 2개 주어집니다. 그래서 케이스로만 확인해보면 다음과 같습니다.1 -> V1 -> V2 -> N1 -> V2 -> V2 -> N그리고 다익스트라 알고리즘을 통해 해당 정점에서 다음 정점까지의 최소거리를 구하면 됩니다.정점 까지의 최대거리는 2억이기 때문에 모든 값을 2억으로 초기화를 해준 후 1번의 경우와 2번의 경우 모두를 계산을 합니다. 1번 계산이나 2번 계산의 결과값이 기존에 설정한 2억이상이면 갈 수 없는 길이 존재하는 것 이기 때문에 조건을 처리해주면 됩니다. import java.io.BufferedReader;import java.io.IOE..

https://www.acmicpc.net/problem/2457  이번 문제는 그리디 알고리즘입니다. 문제에서 3월1일부터 11월 30일까지는 꽃이 하나 이상 피어있어야 된다고 했으므로 초기값은3월1일을 포함하여 이 전까지 핀 꽃 중에 제일 오래사는 꽃이 필요합니다. 그리고 제일 오래사는 꽃을 찾게 된다면 그 꽃이 죽는 날을 기준으로 위 행동을 반복하면 됩니다. 여기서 해당 꽃이 11월 31일까지 살게 된다면 기록했던 꽃의 수를 반환을 하고 최종적으로 11월 31일까지 못갔다면 0을 반환하면 됩니다. 그리고 만약 꽃이 없는 기간이 생기게 되면 이 또한 바로 0을 반환하면 됩니다. import java.io.BufferedReader;import java.io.IOException;import java...

https://www.acmicpc.net/problem/1541  이번 문제는 그리드 알고리즘입니다. 주어진 식을 괄호를 적절히 쳐서 최소값으로 바꾸어 주어야 합니다. 최소값으로 만드는 명제는 -뒤에 값을 크게 하는 것입니다. 즉 '-' 뒤에 '+' 하는 값을 괄호로 묶어주는 것을 의미합니다. 만약 '-' 뒤에 '+' 하는 값을 괄호로 묶지 않은 것이 더 크다며 위 명제는 틀린 것이 됩니다. 하지만 '-' 뒤에 '+' 하는 값을 묶지 않으면 그 값은 +로 남기 때문에 명제가 참이라고 할 수 있습니다. 실제 풀이는 '-'를 기준으로 문자열을 끊어줍니다. 그리고 끊은 문자열을 전부 다시 '+' 기준으로 분리하고 계산한 값을 리스트에 저장합니다. 그렇다면 리스트에 있는 값을 전부 빼주면 되는데 주의할 점은 ..

https://www.acmicpc.net/problem/1744 이번 문제는 그리디 알고리즘입니다. 그리디 알고리즘은 귀류법을 통해 증명을 해놓는 습관이 중요합니다. 가설은 다음과 같습니다.양수 영역은 내림차순으로 2개씩 곱한 합과 양수의 개수가 홀수 일 경우 남은 값을 더합니다.음수 영역은 오름차 순으로 2개씩 곱한 합과 만일 음수 영역의 값이 홀수 일 경우 0의 존재 유무를 확인해 존재한다면 그 음수를 음수∗0 으로 제거하고 없다면 음수를 더합니다.양수 영역부터 명제를 확인해보겠습니다. 만약 양수 부분에서 내림차 순으로 2개씩 곱하지 않았을 때 최대값이 나온다면 명제는 틀린 것이 됩니다.양수가 9, 8, 7, 6이 있을 때 2개씩 곱한 값으로 대체 할 수 있다면 9∗8+7∗6이 제일 큽니다.그런데 ..

https://www.acmicpc.net/problem/2346 이번 문제는 단순 자료구조 문제입니다. 풍선에서 나온 값에 따라 마지막 데이터를 제거하고 처음에 추가하거나 처음 데이터를 제거하고 마지막 데이터에 추가하면 됩니다. 만약 풍선에 적힌 값이 양수라면 처음 데이터를 제거하고 마지막에 추가하고 음수라면 마지막 데이터를 제거하고 처음에 추가하면 됩니다. 여기서 주의할 점은 양수인 경우 풍선이 터지면서 자연스럽게 위 과정을 거치므로 값에서 1을 빼서 진행을 하면 됩니다.예시를 들어 2 3 1 2 4일 경우 2가 터지면 다음에 숫자는 2를 기준으로 오른쪽 두 칸을 이동한 1이 되어야 하는데 2가 터짐과 동시에 3 1 2 4에 기준이 3으로 바뀌므로 1을 뺀 값을 옮기면 됩니다. 여기까지 풀이했을 때 ..

https://www.acmicpc.net/problem/1707 이번 문제는 그래프 문제입니다. 그래프 문제는 여러가지 유형이 있지만 이번 문제는 '이분 그래프' 입니다. 이분 그래프에 대해 간단히 설명을 하면 모든 정점을 2개의 집합으로 나눌수있으며 하나의 집합 내부 정점들은 서로 이웃이 아닌 집합을 말합니다. 예를 들어 그래프가 1 -> 2 -> 3 -> 4 라고 했을 시 A라는 집합에는 1,3 B라는 집합에는 2,4가 들어간다. 여기서 1,3은 서로 이웃이 아니며 2,4 또한 이웃이 아니다. 이렇게 나타낼 수 있는 그래프를 이분 그래프라 합니다. 구현방법은 처음에는 HashSet을 통해 각각 어느 집단에 넣어주고 확인을 하는 과정을 거쳤지만 이는 시간초과라 해결하지 못하였습니다. 그래서 다른 방식..

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개의 코드 실행 흐름이 생긴다는 의미입니다. 멀티 프로세스는 운영체제에서 할당받은 자신의 메모..