heemang.dev

1. 문제https://www.acmicpc.net/problem/21939 2. 코드Problem의 정렬 조건 1. 난이도가 낮은 순으로 정렬한다.2. 난이도가 같다면 문제 번호가 낮은 순으로 정렬한다.TreeSet을 사용하여 Problem 저장 시에 정렬이 될 수 있도록 한다.TreeSet은 first(), last()를 사용하여 첫 번째 요소와 마지막 요소에 접근할 수 있다. (양방향 접근)public class Main { static int N, M; static TreeSet set = new TreeSet(); static Map map = new HashMap(); // {문제 번호, 문제} public static void main(String[] args) thro..

1. 문제https://www.acmicpc.net/problem/2493 2. 풀이N = 500,000이므로 시간 복잡도 O(N^2)가 걸리는 코드를 작성한다면 시간 초과가 발생한다.이 문제는 시간 복잡도 O(N)으로 풀 수 있어야 한다.현재 건물(i)에서 왼쪽으로 레이저를 쏜다는 것은 (j 그렇다면 (j 그러나 for문을 사용하여 (0, i - 1) 건물을 모두 탐색한다면 시간 복잡도 O(N^2)이 된다. 이 문제는 스택을 사용하여 최근에 접근한 건물부터 탐색하여 해결할 수 있다.스택의 조건은 다음과 같다.현재 건물보다 높은 건물이 나올 때까지 스택에서 건물을 제거한다.스택 최상단에 있는 건물이 현재 건물보다 높은 건물이다.스택이 비어있다면 현재 건물보다 높은 건물이 없다는 것이다.예를 들어, 높이가..

1. 후위 표기식이란?연산자를 피연산자 뒤에 배치하는 표기 방식이다.일반적인 중위 표기식(Infix)에서는 피연산자 사이에 연산자가 위치하지만, 후위 표기식은 피연산자 뒤에 연산자가 위치한다. 중위 표기식1 + 2A + B * C 후위 표기식12+A B C * +  후위 표기식의 특징으로는 괄호가 필요하지 않다는 것이다. 중위 표기식(A + B) * C후위 표기식A B + C * 2. 후위 표기식 계산 방법후위 표기식은 스택(Stack) 자료구조를 사용하여 계산할 수 있다.피연산자는 스택에 저장한다. 스택은 LIFO(Last In, First Out) 구조이다.연산자를 만나면 스택에서 피연산자 두 개를 꺼내고, 연산자와 계산한다. 계산된 값은 다시 스택에 저장한다.연산을 모두 마쳤을 때 스택에 저장된 값..

1. 문제https://www.acmicpc.net/problem/21318 2. 코드누적 합(prefixSum)을 활용하여 해결하였다.피아노의 단계를 arr 배열에 저장한다.0 prefixSum 배열을 사용하여, 1번 피아노부터 현재 피아노까지의 실수 횟수를 기록한다.x 만약 prefixSum을 사용하지 않는다면 M번동안 (x, y) 받고 x prefixSum을 사용하여 x prefixSum[y - 1] : 범위 조건으로 y는 포함하지 않는다고 명시되어 있다.prefixSum[x - 1] : (1번 피아노부터 x번 피아노까지의 실수 합) - (1번 피아노부터 ~ x - 1번 피아노까지의 실수 합)public class Main { static int N, M; static int[] arr..

1. 문제https://www.acmicpc.net/problem/17132. 코드문제 푸는 것에 지쳐서 설명은 주석으로 대체한다..import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashMap;import java.util.Map;public class Main { static int N; static int M; static int[] persons; // 입력으로 받은 사람 번호 static Map pickPersons; // 사진이 등록된 사람, static int[] pickPers..