hansjour 개발일지

[문제] 오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자. 깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다. dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점 visited[R]

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 어떤 메모리 구조를 가졌느냐에 따라 효율적인 탐색 방법이 갈리긴 하지만, 일반적으로 탐색에 쓰이는 알고리즘 중 대표적인 DFS에 대해 알아보도록 하겠다. 깊이 우선 탐색(DFS)은 이진 트리 구조를 기반의 효율적인 탐색 방법 중 하나이다. Depth First Search = 깊이 우선 탐색이라고도 부르며, 그래프와 트리의 깊은 부분을 우선적으로 탐색하는 알고리즘이다. ▷ 깊이 우선 탐색(DFS) 의 특징 -다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색하는 방식이다. -스택 메모리 구조에 기초하여 구현이 간단하다. -검색 대상 그래프가 크거나 경로의 특징을 저장해둬야 하는 문제에 유리 리프 노드(시작 정점)부터 시작해 정점과 연결 된 모든..

오늘은 자바의 Iterator의 개념과 장/단점을 알아보려고 한다. 먼저, Iterator가 무엇을 말하는지 살펴보자. 1. 개념 JAVA Iterator란? : 컬렉션 프레임워크(Collection Framework)에 저장된 데이터를 순회하는 인터페이스이다. 컬렉션 프레임워크는 List, Set, Map, Queue, ArrayList, Stack, LinkedList 등을 뜻한다. 2. 의의 -우리가 쓰는 웬만한 자료구조의 상위 개념에 속하는 인터페이스로, Iterator 문법 하나로 자료 구조의 일반적인 순회가 가능하다. 3. 대표 메소드 .hasNext() //다음 요소가 있는지 확인, return값 true/false .next() //다음 요소 호출 .remove() //요소 삭제 선언은 I..

[문제] N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 좋은 수의 개수를 첫 번째 줄에 출력한다. -입력 10 1 2 3 4 5 6 7 8 9 10 -출력 8 [풀이] package Baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..

[문제] 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오. 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,00..

오늘은 C언어의 자료 표현 방식 중 '포인터와 연결 리스트(Linked List)' 에 대해 알아보고자 한다. 연결 리스트는 링크(link)를 이용해 표현한 리스트이다. 연결 리스트는 배열의 한계를 극복한 표현 방법 중 하나로 동적 할당이 가능한 것이 특징이다. 그 구조를 더 이해하기 쉽게 데이터 구조를 먼저 살펴보자. 1. 포인터의 개념 데이터가 담긴 주솟값을 저장하는 변수 다른 어떤 변수의 주소를 그의 값으로 저장한다. C 언어에서는 모든 변수가 주소를 가지고 있기 때문에, 모든 변수에 대해서 포인터 유형이 존재한다. 2. 포인터의 특성 1) 초기화 - 포인터를 선언만 하고, 초기화하지 않으면 값은 미정(undefined), 포인터 변수에 주소를 지정해야 한다. - 주소 연산자 ‘&’를 해당하는 변수..

오늘은 C언어의 자료 표현 방식 중 반드시 기본으로 알아야 할 '배열' 에 대해 알아보고자 한다. 1. 배열의 개념 배열은 종류가 같은 여러개의 데이터를 순차적으로 나열한 것이다. 정수(int), 문자(char), 부동소수(double) 뿐 아니라 구조화 타입의 배열도 허용한다. 2. 배열의 특성 인덱스 범위(index range)가 존재하며 이 범위를 넘게 되면 에러가 발생한다. 배열의 크기는 선언 시 명세하며, 이 크기는 불변하다. (크기 = 길이) 배열의 lower bound는 항상 0이다. upper bound는 최소 lower bound의 +1 이다. 배열의 선언과 초기화가 동시에 가능하다. 예) int a[100]={0} //배열 a를 선언과 동시에 0으로 초기화 3. 배열의 선언 대괄호([ ..

▷ 큐(Queue)이란? 큐(Queue)는 FIFO(퍼스트 인 퍼스트 아웃) 원리를 기반으로 구성된 요소들의 집합을 나타내는 추상적인 데이터 유형이다. 큐는 스택과 다르게 양방향 자료구조이다. 즉 출구, 입구가 따로 따로 존재한다는 것이다. 스택의 삽입,삭제가 top에서 모두 이루어진다면 큐는 -큐의 가장 앞 부분을 가리키는 front -큐의 가장 뒷 부분을 가리키는 rear 에서 삽입, 삭제가 이루어진다. 큐에서 수행되는 작업은 다음과 같다. 큐의 rear에 데이터를 추가하는 add/offer, 큐의 front의 데이터를 제거하고 null값으로 채우는 poll, 제거만 하는 remove, 초기화하는 clear 큐의 맨 앞(front)에 있는 요소를 제거하지 않고 액세스하는 peek ▷ 큐(Queue)의..

▷ 스택(Stack)이란? 스택(stack)은 LIFO(라스트 인 퍼스트 아웃) 원리를 기반으로 구성된 요소들의 집합을 나타내는 추상적인 데이터 유형이다. 스택에서 수행되는 작업은 크게 세 가지로 구분이 가능하다. 요소를 스택의 맨 위에 추가하는 push, 스택의 맨 위 요소를 제거하는 pop, 스택의 맨 위에 있는 요소를 제거하지 않고 액세스하는 peek ▷ 스택(Stack)의 특징? 스택 구조는 위로 쌓아 올린 동전 혹은 접시와 같다. LIFO(Last-In First-out) > 스택에 마지막으로 추가된 요소가 가장 먼저 제거 (가장 나중에 쌓은 접시가 먼저 제거 됨) 스택의 한쪽 끝에서만 액세스 가능 > 일반적으로 스택의 'top'이라고 하는 한쪽 끝에서만 추가 및 제거된다. 일정한 시간 복잡성 ..