위 문제는 Java의 Queue관련 메서드를 공부한 사람이라면 간단히 풀 수 있는 문제다. 내가 먼저 정리해둔 Queue인터페이스의 메서드를 알아보자. LinkedList와 ArrayDeque는 Deque 인터페이스의 상속을 받아 양쪽에서 접근이 가능하다. 주로 LinkedList를 사용하여 큐를 구현하며 ArrayDeque가 더 효율이 좋은 경우도 있다. LinkedList는 LinkedArray처럼 모든 인덱스가 노드(위치)와 밸류(값)을 갖고 있어 중간에 값을 추가하거나 삭제할 때 더 효율적이다. ArrayDeque는 순차적인 검색을 할 때 더 효율적이다. 이를 알고 사용하면 더 효율적인 코드를 만들어 낼 수 있을 것이다. 그럼 문제를 살펴보자. 이번 문제는 매우 단순하다. https://www.a..

문제를 풀기 전에 우선 구간합을 구하는 방법을 알아야한다. 하지만 또! 구간합을 구하기 전에 합 배열을 만들줄 알아야 한다. ㅎㅎ 알아야하는 이유는 다음과 같다. 반복문으로 해당 문제를 풀었을때에는 시간 초과가 발생했다. 주어진 질의의 개수가 최대 10만개이다. 수의 개수도 최대 10만개이다. 최악의 경우에는 10만개의 수를 가진 배열안에서 10만번의 질의를 반복문을 돌려야한다. 이때 반복문을 통한 시간복잡도 O(n^2)로는 해결할 수 없다. 이 때 구간합으로 문제를 해결한다면 누적배열합을 생성하는데 O(N)이 들고 M번 반복하므로 O(N+M)의 시간복잡도를 갖는다. 해당 문제는 1초안에 풀어야하는데 구간합 알고리즘을 모른다면 반복문으로 통해 최악의경우 1억회이상의 연산을 하기때문에 시간내에 풀기 힘들것..

BFS에 대한 개념을 먼저 공부해야 한다면 아래 포스팅을 먼저 보고 문제를 푸시는 걸 권장합니다. https://sunro1994.tistory.com/181 [백준 -24480 ] java , 알고리즘 수업 - 깊이 우선 탐색 2 문제를 풀기 전 그래프 및 DFS 개념이 부족하다면 아래 포스팅을 먼저 읽어주세요! https://sunro1994.tistory.com/179 [자료구조 - Graph 와 DFS] Graph와 DFS란? [Algorithm] 깊이 우선 탐색 목차 1. DFS란? 2. 그래프 sunro1994.tistory.com 이번 문제입니다! https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)..

문제를 풀기 전 그래프 및 DFS 개념이 부족하다면 아래 포스팅을 먼저 읽어주세요! https://sunro1994.tistory.com/179 [자료구조 - Graph 와 DFS] Graph와 DFS란? [Algorithm] 깊이 우선 탐색 목차 1. DFS란? 2. 그래프란? 그래프의 특징 그래프의 종류 그래프 용어 1. DFS란? 깊이 우선 탐색(Depth-First-search)은 그래프 완전 탐색 기법중 하나 그래프의 시작 노드에서 sunro1994.tistory.com 문제해결중 놓친 중요한 부분 - 내림차순! Do it 알고리즘 자바편을 통해 DFS를 공부하고 해당 코드를 변경해서 이 문제를 풀려고 했다. 책에서 제공했던 백준 문제는 아래의 문제였다. https://www.acmicpc.ne..

위 문제는 DFS풀이의 가장 기본적인 문제이다. 문제를 풀기에 앞서 풀이 순서를 짚어보자. 1. 최대 정점의 개수와 문제풀이 시간을 대조해본다. - 문제 풀이 시간은 3초이다. 최대 노드의 개수는 1000개로 n^2의 복잡도로 문제를 풀어도 충분히 시간이 남는다. 2. 해당 그래프를 직접 그려본다. - 첫 예시의 그래프를 만들어보자면 다음과 같다. (혼을 담아 정성스럽게 그려보았다) 3. 이처럼 두개의 그래프가 그려지는것을 확인할 수 있다. 이를 코드로 작성하기 위한 슈도코드를 작성해본다. n(노드 개수) , m(엣지 개수) A(그래프 데이터 저장 인접 리스트) visited(방문 기록 저장 배열) for(n만큼 반복 {A 인접 리스트의 각 ArrayList초기화} for(m의 개수만큼 반복하기) { A..

에라토스테네스 체 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른 방법이다. 일단 1부터 100까지 숫자를 쭉 쓴다. 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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 일단 소수도, 합성수도 아닌 유일한 자연수 1..