Algorithm 195

BOJ#14438 수열과 쿼리 17

BOJ#14438 수열과 쿼리 17 * 문제https://www.acmicpc.net/problem/14438 * 풀이Segment Tree - RMQ설명 : http://stack07142.tistory.com/216 * 나의 코드 (Java, Kotlin)https://github.com/stack07142/BOJ/blob/cd23ff130cc6e28b7f30aea5c4bc8932dad8688b/BOJ%2314438_SequenceQuery17/src/Main.java (Java)import java.io.*; import java.util.StringTokenizer; /** * 선데이코딩 베타라운드1 - E. 수열의 최소값 * BOJ#14439 수열과 쿼리 17 * https://www.acmic..

BOJ#3665 최종 순위

BOJ#3665 최종 순위 * 문제https://www.acmicpc.net/problem/3665 * 풀이위상 정렬 문제입니다. - 위상 정렬 설명 : http://terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093 첫 예제를 통해 어떻게 문제를 풀지 생각해보겠습니다. 5 4 3 2 1 1. 간선과 indegree를 아래와 같이 추가합니다. 간선의 경우 인접리스트보다는 인접행렬로 구현하는게 더 효율적일 것 같습니다. 5->4, 5->3, 5->2, 5->14->3, 4->2, 4->13->2, 3->12->1 [0, 4, 3, 2, 1, 0] int[][] graph = new int[n + 1][n + 1];// n^2 으로 인접행렬..

Algorithm/정렬 2017.05.30

BOJ#2042 구간 합 구하기

BOJ#2042 구간 합 구하기 * 문제https://www.acmicpc.net/problem/2042 * 풀이 http://stack07142.tistory.com/216 * 나의 코드 https://github.com/stack07142/BOJ/blob/48ba119dd11b7779be8b2d1e05a64b723e334d54/BOJ%232042_RangeSumQuery/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BOJ#2042 구간의 합 구하기 * https://www.acmicpc.net/problem/2042 */ public class Main { static final int QUERY_CHANGE = 1;..

세그먼트 트리(Segment Tree, 구간 트리)

세그먼트 트리(Segment Tree, 구간 트리) ■ 구간에 대한 질문에 효율적으로 대답하는 것■ Segment Tree는 저장된 자료들을 적절히 전처리하여 그들에 대한 질의에 빠르게 대답할 수 있도록 한다.■ 구간 트리의 핵심 아이디어는 주어진 배열의 구간들을 표현하는 이진트리를 만드는 것 전처리하는게 핵심인 것 같습니다. 만약 구간의 최소값을 여러번 구하는 것이 목적이라면, 그 목적에 맞게 전처리하여 구간 트리를 구현하는 것입니다.그리고 그 구간 트리는 해당 구간의 최소치를 각 노드에 저장할 것입니다. 예) 길이 5인 배열을 표현하는 구간 트리가 저장하는 구간들 [0, 4][0, 2] [3, 4] [0, 1][2] [3][4] [0][1] ■ Heap 자료구조와 마찬가지로 일차원 배열로 표현하는 것..

Algorithm/기타 2017.05.25

BOJ#2805 나무 자르기

BOJ#2805 나무 자르기 * 문제https://www.acmicpc.net/problem/2805 * 풀이이분 탐색 * 나의 코드 https://github.com/stack07142/BOJ/blob/694dfa1bdca47f2449d56ad95c47ba5fc7a371f6/BOJ%232805_EKO/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#2805 EKO 나무 자르기 * https://www.acmicpc.net/problem/2805 */ public class Main {..

BOJ#4307 개미

BOJ#4307 개미 * 문제https://www.acmicpc.net/problem/4307 * 풀이 쉬운 문제입니다.(개미의 속도가 모두 같기 때문에) 저는 막대의 중간에서 가장 가까운점, 가장 멀리 있는 점을 구해서 최대/최소 시간을 구했습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/a4b77ff3f9b58feceb146cac9d85601a166cb545/BOJ%234307_Ant/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BOJ#4307 개미 * https://www.acmicpc.net/problem/4307 */ public class Main { public st..

Algorithm/기타 2017.05.23

BOJ#1152 단어의 개수

BOJ#1152 단어의 개수 * 문제https://www.acmicpc.net/problem/1152 * 풀이1. 문자열을 입력받습니다. 앞, 뒤 공백이 있을 수 있으므로 trim 함수를 이용하여 공백을 제거합니다.2. 문자열을 정규표현식을 이용하여 분리합니다. (정규표현식 : \\{Blank}+ : 공백이 하나 이상)3. 분리한 문자열의 개수를 출력합니다. * 나의 코드import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * BOJ#1152 단어의 개수 * https://www.acmicpc.net/problem/1152 */ public class Main { public stati..

Algorithm/문자열 2017.05.22