Java78 [JAVA] 백준 - 스위치 1395 (세그먼트트리 + lazy propagation) www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net 세그먼트트리를 풀기위한 기본 템플릿은 onejunu.tistory.com/119 [JAVA] 세그먼트 트리구현법과 lazy propagation (feat. 백준) www.acmicpc.net/blog/view/26 세그먼트 트리 나중에 업데이트 해야지! 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 .. 2021. 3. 14. [JAVA] 세그먼트 트리구현법과 lazy propagation (feat. 백준) www.acmicpc.net/blog/view/26 세그먼트 트리 나중에 업데이트 해야지! 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제가 있습니다. 10999번 문제: 구간 합 구하기 2 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 www.acmicpc.net 여기서 공부한 내용을 바탕으로 간단하게 정리해보고자 한다. 세그먼트 트리를 공부하면서 분할정복에 대한 감을 좀더 잘 잡을 수 있는거 같다. 세그먼트 트리 구현을 잊어버려도 되지만 감은 계속 붙잡고 있었으면 하는 마음에 본인이 이해한 내용을 그림과 코드로 설명한다. 설명은 위에 백준님이 설명해준 그림을 바탕으로 설명하겠다. 먼저 백준님글을 .. 2021. 3. 12. [JAVA] 세그먼트 트리 ( SegmentTree ) www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i www.acmicpc.net 백준 사이트의 설명을 보며 나름 자바 코드로 정리해봤다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main{ static long[] segTree; static long[] a; /** * nod.. 2021. 3. 7. [JAVA] 백준 - 캐슬 디펜스 17135 (테케 다 맞는데 틀린다면?) www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 자꾸 틀린다면 꼭 점검해야할 상황을 소개한다. (본인 경험) 1. 궁수 3명을 배치하는 모든 경우를 구했는가? - 문제에서 N+1 번째 칸에 궁수 3명을 배치한다고 하였다. 한 칸에 한명만 올 수 있다. 따라서 M개의 자리에서 3개를 선택하는 모든 경우의수를 구해야한다. Combination 로직을 DFS로 구현해주면 된다. 여기에서 M = 5 일때 3개의 자리를 선택하는 경우의 수는 5C3 이므로 10가지가 나와야한다... 2021. 3. 4. [JAVA] Enum 내부 동작원리를 중심으로 알아보기 처음 Enum 에 대해 배울 때 단순히 여러 상수를 정의할 때 사용하였다. 상수를 그냥 쓰다보면 예상치 못한 오류가 생길 수 있으므로 따로 열거형으로 정의해서 사용한다. JAVA 에서는 Enum 안에 함수도 들어가는 거 같고 생각보다 복잡한 느낌이 있어서 이번 기회에 재대로 정리해본다. 아래의 예시를 보자. class Korea { static final int SEOUL = 0; static final int DAEGU = 1; static final int BUSAN = 2; } class America { static final int LA = 0; static final int NEWYORK = 1; } public class Main{ private static void main(String[].. 2021. 2. 26. [JAVA] 위상정렬 (TopologySort) - 위상정렬이란? 순서가 정해져 있는 작업들의 목록들을 가지고 전체 작업 순서를 결정하도록 하는 알고리즘. 이를 위해서는 사이클이 없는 방향그래프에서만 해야한다. 아래 그래프로 예를 들겠다. 1번 작업은 2번보다 먼저 해야한다. 이것을 방향그래프로 나타내었다. 2번은 5번 보다 먼저 해야 한다. 5번은 4번 보다 먼저 해야한다. 만약 위와 같은 작업 스케줄이 있다면 어떻게 진행하면 좋을 것인가? 1 - 2 - 3 - 5 - 4 1 - 3 - 2 - 5 - 4 위 2가지 경우중에서 한가지 선택하여 진행하면 된다. 먼저 차수에 대해 정의하겠다. 한 정점의 차수 = 해당 정점보다 먼저 선행되어야 하는 작업의 수 예를들어, 3번의 차수는 1이다. 1번 작업이 선행되어야 하기 때문이다. 5번의 차수는 2이다. 2.. 2021. 2. 24. [JAVA] ArrayList remove for loop ( ConcurrentModificationException) JAVA 에서 ArrayList 메소드중 remove를 루프문을 돌면서 사용하고 싶은 데 자칫하면 삭제된 인덱스가 꼬여서 java.util.ConcurrentModificationException 이 발생한다. ArrrayList를 루프문 돌면서 삭제는 Iterator 를 사용하면 깔끔하다. // ArrayList 초기화 ArrayList list = new ArrayList(); // list에 원소들 추가 list.add(1); list.add(2); ... // iterator 사용 Iterator it = list.iterator(); // 10 보다 작다면 삭제해버린다. while(it.hasNext()){ int next = it.next(); if( next < 10 ){ it.remove(.. 2021. 2. 24. [JAVA] Comparator 란? (feat. Generics ) - Comparator : 기본 정렬기준이 아닌 다른 기준으로 사용하고 싶을 때 사용. Comparator는 인터페이스임. - Comparator 구조 Comparator 는 함수형 인터페이스이기 때문에 람다식으로도 표현할 수 있다. 함수형 인터페이스에 관한 내용은 나중에 자세히 다룰 것이다. 여기서 중요한 것은 Comparator 안에 있는 compare 함수다. 사실 Comparator 인터페이스 내부에는 많은 함수들이 존재하지만 compare에 관해서만 정리하겠다. compare 를 구현함으로써 임의의 클래스에 대해서 정렬 기준을 만들 수 있다. 예시를 들면서 살펴본다. - Comparator 예시 먼저 아래처럼 클래스들을 선언한다. Phone은 iphone 과 galaxy의 부모이다. 또한 모든 .. 2021. 2. 24. [JAVA] 백준 1707 - 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net - 7등에 랭크 되어있는 거 보면 느린코드는 아닌 듯 하다. - 이분 그래프란? 그래프에서 임의의 점을 선택하여 그 점과 이웃하는 다른 점은 선택된 점과 색이 달라야 한다. 그리고 그래프에 칠해진 색은 2종류가 가능할 때 이분 그래프라고 한다. 예를 들어, 아래는 이분 그래프인가? 정답은 이분그래프가 맞다. 왜냐하면 아래처럼 2가지의 색상만을 이용하여 임의의 점을 선택할 시 모든 이웃이 자신과 다른.. 2021. 2. 23. 이전 1 2 3 4 5 ··· 9 다음
