밤이 블로그

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 으로 인접행렬..

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

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 개미 * 문제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..

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..

import Foundation let input : String = readLine()!; var idx : Int = 0 while idx + 10 < input.characters.count { var startIdx = input.index(input.startIndex, offsetBy: idx) var endIdx = input.index(input.startIndex, offsetBy: idx + 10) let range = startIdx ..< endIdx print(input.substring(with: range)) idx += 10} var startIdx = input.index(input.startIndex, offsetBy: idx)var endIdx = input.endInd..

import Foundation let n : Int = Int(readLine()!)!var sum : Int = 0 for index in 1...n { sum += index} print(sum)

import Foundation let input : String = readLine()!;let inputArr = input.characters.split(separator: " ").map({Int(String($0))!}) var sum = 0 for number in inputArr { sum += number} print(sum)

BOJ#2887 행성 터널 * 문제https://www.acmicpc.net/problem/2887 * 풀이 MST, 최소 스패닝 트리 문제입니다.최소 스패닝 트리의 특성상 (문제에도 명시되어 있듯이) 행성이 N개 이므로, 간선은 N-1개가 됩니다. 이 문제를 풀 때 어려웠던 점은 간선 정보가 직접적으로 주어지지 않고직접 간선 정보를 만들어야 한다는 점입니다. 주의할 점으로는N이 최대 100,000 이므로 모든 간선을 입력하려면 100,000 * 100,000이 됩니다. (시간 초과) 따라서 모든 간선을 추가할 수 없으므로, 아래 방법대로 최소 간선만 추가해줍니다. 간선 비용은 문제에 주어진대로 min(x좌표 차이, y좌표 차이, z좌표 차이) 이므로1. x좌표를 기준으로 정렬 -> i-1 노드와 i 노..