Algorithm 썸네일형 리스트형 5. Stack과 Queue Stack과 Queue는 앞에서 다루었던 Array나 List와는 다른 확실한 개성을 갖고 있는 자료구조입니다. Array와 List가 자료를 공간에 하나씩 배정하고 특정 공간을 지목하여 자료를 꺼내 사용하는 단순한 방식을 지향한다면 Stack과 Queue는 자료가 들어온 순서와 그 순서에 따라 자료를 꺼내는 방식을 취하고 있습니다. Array와 List처럼 특정 주소를 지목하여 값을 꺼낼 수 없고, 중간에 입력된 자료를 꺼내기 위해서는 그 자료 앞이나 뒤에 있는 모든 자료를 비워내었을 때 그 자료를 꺼낼 수 있는 것입니다. 사용하기에 불편할 것 같은 이 자료구조는 왜 그리고 어떻게 사용하는 것인지 알아보겠습니다. 먼저 Stack부터 설명하겠습니다. Stack은 쌓다라는 뜻을 갖고 있습니다. Stack은.. 4. Comparator를 이용한 Array와 List의 정렬 Java프로그램에서 Array나 List에 저장된 value를 정렬할 때 가장 많이 쓰는 방식은 Arrays class나 Collections class를 import하여 정렬하는 방식입니다. 빠른 정렬을 개발자가 직접 구현하여 사용하는 것도 가능하지만, Arrays나 Collections에서 구현된 sort 함수는 정렬방식 중 가장 시간 복잡도가 작은 방식으로 최적화되어 있기 때문에 시간을 더 줄일 수 있지 않을까 하는 생각으로 직접 구현할 필요는 없습니다. 하지만 일반적인 Arrays.sort()나 Collections.sort()를 이용하다보면 발생하는 문제가 있습니다. Array든 List든 값을 오름차순으로만 정렬한다는 것과 이차원 배열 등 다차원 배열의 정렬이 되지 않는다는 것입니다. Java.. 강한 연결 요소 (SCC: Strongly Connected Component) 강한 연결 요소는 그래프 내의 노드간 연결구조 중 한가지이다. 간단히 설명하자면 그래프 내에서 노드간 상호이동이 가능한 상황이면 그 노드들은 강한 연결 요소 관계에 놓여있다고 말할 수 있고, 만일 일방으로만 이동이 가능한 경우나 이동이 불가능한 경우는 강한 연결 요소가 아니라고 할 수 있다. 예를 들어 방향성 있는 간선과 노드가 주어졌을 때, 이들이 연결되어 하나의 그래프를 이루고 있고, A라는 노드에서 B라는 노드로 이동이 가능하고 B라는 노드에서 A 노드로 이동이 가능하다면, 두 노드는 SCC를 이룬다고 할 수 있다. 좀 더 확장하여 세 개나 그 이상의 노드들의 연결관계로도 설명할 수 있다. 만일 A, B, C 세 개의 노드가 있을 때, A 노드는 B 노드로, B 노드는 C 노드로, C 노드는 A 노.. 1854번: K번째 최단경로 찾기 - Baekjoon Online Judge K번째 최단경로 찾기는 최단경로 알고리즘 중에서 가장 기본적이고, 가장 널리 알려진 다익스트라(Dijkstra) 알고리즘의 응용 문제이다. 다익스트라 알고리즘에 대해 간단히 알아보자면 다익스트라 알고리즘은 노드와 간선으로 이루어진 그래프가 있을 때, 하나의 노드를 출발점으로 하여 목표 노드까지 도달하는데 드는 비용을 최소화시키는 알고리즘이다. 알고리즘이 갖는 의미가 비교적 단순명료하여 이해하기는 쉬운데 처음 소스로 구현하자면 어떻게 해야할지 방향 잡기가 힘들다. 간단히 다익스트라 알고리즘 푸는 법을 설명하자면, 처음 시작점에서부터 갈 수 있는 노드들을 탐색하여, 해당 노드까지 가는데 드는 비용이 최소가 되도록 업데이트 해준다. 그리고 비용을 줄여서 이동 가능한 노드들이 우리가 도착 목표로 하고 있는 노드.. 3. Array와 List 비교 및 사용 Array와 List는 가장 기본적인 자료구조입니다. Array는 일반적으로 배열이라고 부르는 자료구조입니다. 선언 및 사용에 있어 대괄호를 사용하며 제일 처음 저장되는 값은 0번째 자리에 저장되게 됩니다. 또한 처음 크기와 타입을 선언하게 되면 새로운 객체를 생성하기 전까지는 형태가 고정된다는 특징을 갖고 있습니다. 만일 배열크기를 넘어서게 되면 Exception이 나게 되며 처음 선언된 타입이 아닌 다른 타입의 자료형을 배열에 넣으려고 한다면 Type mismatch로 컴파일 자체가 안되게 됩니다. 1234567891011121314151617import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTok.. 2. BufferedWriter와 System.out.println() 의 비교와 사용법 잘 구현된 알고리즘은 속도면에서 그리고 메모리면에서 최적화되어 있어야 합니다. 만일 문제는 잘 풀어놓고도 많은 입력과 출력을 감당하지 못해서 실행 속도가 느려진다면 복장이 터질겁니다. 그렇다면 어떤 문제들을 풀 때 입출력에 유의해야 할까요. 가장 손쉽게 파악할 수 있는 방법은 문제에서 주어진 입력, 출력 예시를 보는 것입니다. 문제에서 가능한 케이스가 무엇인지 모두 출력하게 한다던가, 여러 케이스의 답을 한번에 출력하기를 바란다면 말은 하지 않았지만 빠른 입출력을 사용하는 것을 은연중에 의도한 것이라고 할 수 있습니다. 어쩌면 의도하는게 아니라 빠른 입출력의 사용을 지극히 당연하게 생각하고 있을 수도 있겠습니다. 프로그래밍을 처음 시작할 때 일반적으로 우리는 출력을 먼저 하게 됩니다. Java 개발을 처.. 11400번: 단절선 - Baekjoon Online Judge 단절선 알고리즘은 완전 그래프에서 어떤 간선을 제거하였을 때, 그래프가 두 개 이상의 영역으로 나누어지는지 알아내기 위한 알고리즘이다. 문제를 단절선 알고리즘으로 규정짓기 위해서는 몇 가지 조건이 주어져야 한다. 첫째 완전 그래프여야 한다. 완전 그래프는 모든 노드가 간선으로 연결되어 어느 한 노드도 빼놓지 않고 연결이 되어 있는 경우를 의미한다. 완전 그래프의 정의 https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84_%EA%B7%B8%EB%9E%98%ED%94%84 둘째 한번에 하나의 간선만 끊을 수 있다. 동시에 여러 간선을 끊는다던가 한번 끊어진 간선은 계속 끊어진 상태로 있다던가 하는게 아니라 연결되어 있는 상태에서 한번에 하나씩 끊어져야 한다. 단절선 알고리즘.. 1. Scanner와 BufferedReader로 입력받기 보통 처음 Java를 배울 때 입력방식은 Scanner를 사용하게 됩니다. Scanner는 사용하기에 아주 편리한 클래스 입니다. Scanner는 공란과 줄바꿈 모두 입력값의 경계로 인식하기 때문에 데이터를 입력받기에 용이하고, 입력받은 즉시 자료형이 확정되기 때문에 문제를 풀어나가기에도 용이합니다. 그에 반하여 BufferedReader 클래스는 일반적으로 라인단위로 입력을 받게 되며, 라인 바이 라인으로 입력값의 경계를 인식하기 때문에 한줄에 공란을 경계로 여러 값이 입력된 경우라면 파싱이 필수적입니다. 또한 입력받은 값은 모두 String 타입이기 때문에 하나하나 타입변환을 해줘야 한다는 불편함이 존재합니다. 더군다나 BufferedReader는 Scanner처럼 자체적으로 Exception에 대한.. 이전 1 2 3 4 5 다음
