본문 바로가기

알고리즘

 (179)
[BOJ 11438] LCA 2(최소 공통 조상, 희소 행렬, 시간복잡도, JAVA) www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net ## 최소 공통 조상 최소 공통 조상이란, 트리에 각 노드에서 공통된 조상을 갖을 때 가장 가까이 있는 노드를 의미한다. 만약에, 트리의 높이가 H라고 했을 때, 순차적으로 탐색을 한다면 O(H)만큼 걸릴 것이다. 문제의 조건에서 발생할 수 있는 H는 최대 N과 같으므로, 시간복잡도가 O(N * N)이 되므로 제한 시간안에 정답을 찾을 수 없다. ## 희소 행렬 위에서 높이를 O(H)에 순차적으로 접근..
[BOJ 1655] 가운데를 말해요(Java, Time Complexity) www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net ## 시간복잡도 이 문제를, 단순히 정렬을 통해서 가운데를 찾는다고 생각하면, 시간복잡도는 N * N * logN이 된다. N의 범위는 100,000이므로 제한 시간안에 문제를 푸는 것이 불가능하다. 가운데를 알기 위해서는, 주어진 값들을 항상 관리하고 있어야 한다. 새로운 값을 logN만에 삽입할 수 있는 값이 필요하다. 이진 탐색을 통해서, 위치를 찾을 수도 있지만 우선순위큐를 통해서 문제를..
[BOJ 6591] 이항 숏다운 # 중간값이 왜 항상 정수인지 생각 # nCk = n-1Ck-1 + n-1Ck로 모든 문제를 풀려고 하지 말기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import java.util.*; import java.lang.*; import java.io.*; class Main { static Scanner sc = new Scanner(System.in); static int n, k; static int[][] dp; static long answer = 1; public static void main (String[] args) throws ..
[알고리즘] Trie 자료구조 Java 코드 기본코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 import java.util.*; import java.lang.*; import java.io.*; public class Main{ static Scanner sc = new Scanner(System.in); static class Trie{ TrieNode root = new TrieNode(); void insert(String key){ root.in..
[2020 카카오 인턴십] 보석 쇼핑 programmers.co.kr/learn/courses/30/lessons/67258 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr ## 접근 직관적으로 생각해야 답이 있다. 처음에는, 모든 범위에서 양쪽 범위를 줄여가며 탐색하려고 했다. 하지만 이 경우에는, N * N의 시간복잡도를 가졌다. 정확성 테스트는 통과했지만, 효율성 테스트는 통과하지 못했다. 따라서, N * logN이나 N의 시간복잡도를 가지도록 코드를 설계해야 했다. 보석의 개수를 중복을 제거할 수 있는 자료 구조를 통해서 구한다. 순차적으로, 보석들을 읽어가면서, 보석의 개수가 완성이 됐..
[2020 카카오 인턴십] 수식 최대화(Java, 문자열 처리, ArrayList For문 내 원소 삭제) programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 � programmers.co.kr ## 접근 처음에 시행착오를 겪었던 것은, 문자열 내에서 모든 걸 조작하려고 했다. replace를 사용해서 코드를 작성해보니 '-'가 붙어있는 것이 연산용도인지 음수를 나타내는지 확인이 불가능해지고 코드가 더러워진다. 주변 코드를 참고해, 피연산자와 연산자를 구분해 자료구조에 넣기로 했다. 여기서, 배열을 사용하지 말고, ArrayList를 사용해야 한다. ArrayL..
[2019 카카오 개발자 겨울 인턴십] 징검다리 건너기(Java, 간단한 코드, Union-Find) programmers.co.kr/learn/courses/30/lessons/64062# 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr ## 접근 시뮬레이션 형태로 접근하면 절대 안된다. 시간복잡도가 대략적으로 계산해봐도 너무 크다. 따라서, 삭제해야할 돌을 우선순위큐에 넣어놓고, 순차적으로 접근한다. 돌이 가지고 있는 값이 지나갈 수 있는 사람의 수라고 볼 수 있다. 값이 3인 돌을 지우다가, 간격이 k보다 같거나 크면 문제가 발생하고 종료해야 한다. 순차적으로 돌들을 지우면서, 간격을 확인하는 방법을 생각해봐야 한다. 특정한 돌을 지울 때, 앞 뒤로 비어있는 돌들을 확인해서 값을 확인하면 된다. 앞 뒤로 비어있는 돌을..
[BOJ 3780] 네트워크 연결(Java, Union-Find) www.acmicpc.net/problem/3780 3780번: 네트워크 연결 입력은 여러 개의 테스트케이스로 주어진다. 입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스에는 기업의 수를 나타내는 N(4 ≤ N ≤ 20,000)이 주어진다. 다음은 몇 �� www.acmicpc.net ## 접근 이 문제는 대놓고 Union-Find 문제이다. Union-Find의 재귀호출 방식을 이용해서, 코드를 응용할 수 있는지 묻고 있다. 병합 과정의 2.를 이해가 쉽지 않았다. A 클러스트의 새로운 센터가 j가 된다는 것을 의미하는 내용인데, 처음 읽을 때는, B 클러스터의 별도의 센터가 존재할 수도 있다고 생각했다. Union시에 I의 새로운 센터를 J로 만들어 주고, I의 거리를 갱..

티스토리툴바