분류 전체보기 (644) 썸네일형 리스트형 백준 : 10775 https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 www.acmicpc.net 문제해결 방법 : Union-Find 이문제에서 생각할것은 도킹을 할수 없는 상태가 잇다면 그다음 쿼리는 처리안해주고 끝난다는 것이다. 두.. 백준 : 1637 https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어볼 수 있는 날카로운 눈을 가진 기이한 원숭이였다. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다. 어느 날 멍멍이는 원숭이의 날카로운 눈이 너무 샘나서 원숭이를 직접 패고 싶었지만 날카로운 눈으로 찌를까봐 무서워서 때리지는 못하고 대신, 원숭이에게 문제 하나를 던져주었다. 그 문제 www.acmicpc.net 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.. KMP 알고리즘 알고리즘 소개 KMP 알고리즘은 특정 문자열에서 특정 문자열의 패턴이 존재하는가를 판단할때 유용하다. ex) "AAABCCDEFSDFSWESSSAAWWSSW" 문자열에서 ABC 문자열이 존재하는지를 찾기 위해서는 일반적으로 찾기위해서 N*M 번 모든경우를 뒤저야한다. 하지만 KMP 알고리즘을 사용한다면 훨씬 빠르게 pattern을 찾을 수 있다. 여기서는 접미사와 접두사의 개념을 이해해야한다. 접두사 : 문자열의 앞쪽 접미사 : 문자열의 끝쪽 즉 찾을 문자열의 접두사와 접미사의 비교를 통해 반복적으로 일어나는 문자열의 길이와 위치를 알수 있으면 실제 문자열에서 찾을때 처음부터 다시 찾는것이아니라 반복적으로 일어난 패턴에대해서는 이미 같을 것이니깐 거기서부터찾는 것이다. ex) ABDABC 라는 무자열 이.. 투 포인터 알고리즘 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 백준에 예제에서 한번 배워보자 투포인터 알고리즘이란 두개의 포인터지점을두어 특정 조건일때 rear값을 상승시키면서 중첩해가면서 계산하다가 답이아닌경우 front 증가시키면서 정답을 찾아가는 방법이다. 수들의합 2의 예제 2번으로 예시를 들겠다. 현재 구하는 M = 5라고 한다면 front =0 , rear = 0 을 가리키는 상태이다. 이때 sum = 1 이된다. 구할려.. 2020 상반기 라인코딩테스트 후기 대체적으로 배열에 들어있는 문자열을 처리하는 문제가 많이나왓다. 한문제는 그리디문제 였는데 시간이 부족해서 풀지는 못하였다. 카카오 보다 문제가 깔끔한편인거 같다. 알고리즘 공부할것들 1) 기초 - 완전 탐색(Brute-force Search) - 탐욕적 기법(Greedy) - 분할 정복(Divide and Conquer) - 이분 탐색(Binary Search) - BFS, DFS - 정렬 - 구현 2) 자료구조 - 리스트(List), 배열(Array) - 스택(Stack) - 큐(Queue), 데크(Dequeue) - 트리(Tree) 3) 초급 - 백트래킹(Backtracking) - 비트마스크(Bit Masking) - 구간 합 배열(Prefix Sum) - 우선순위 큐(Priority Queue) - 유니온 파인드(Union-Find) - 투 포인터 - 슬라이딩 윈도우(Sliding Window) - 그래프 최단 경로: 다익스트라 알고리즘(Dijkstra’s Algorithm).. LCA(Lowest Common Ancestor) Tree는 deep를 가지는 자료구조이다. LCA는 직역하면 최소 공통 조상이라고 한다. 7과 5의 최소 공통 조상은 2 가될것이다. 문제를 푸는 방법은 7과 5의 deep중 깊은 deep를 위로 올리면서 같은 deep일때 써로를 비교해주는 O(N) 시간으로 문제를 해결 할수 있다. 하지만 만약 쿼리가 많은 문제에 대해서는 어떻게해야할까?? 같은 깊이를 빠르게 찾을 특별한 자료구조가 필요해보인다. 7번을 보도록 하겠다. 7번의 1번째 조상은 4 2 번째 조상은 2 이다. 이러한값을 배열에 미리 저장해둔다면 공통 조상을 찾는데 걸리는 시간은 O(longN)이 된다. 처음 배열을 만드는 비용 O(N*K) 가드는데 K는 log2 ( 최대N) 을 해서 나올수 있는 값이다. N가 100000이라면 2^20 > N.. LinkedList : 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 public class Linkedlist { static class Node{ Object data; Node link; public Node(Object data) { this.data = data; } public Node(Object data, Node link) { super(); this.data = data; this.link = link; } @Override publ.. 이전 1 ··· 62 63 64 65 66 67 68 ··· 81 다음
