전체 글

1-1. 자료구조란?

자료구조(Data Structure) 인터넷의 발달과 함께 우리는 정보화된 시대를 살아가고 있다. 찾아보고 다룰 수 있는 정보의 양이 엄청나기 때문에 자료를 얼마나 효율적으로 관리하고 사용하는가가 굉장히 중요한 문제가 되었다. 자료의 특성에 따라 자료를 다루고 정리하고 처리하는 방법이 다르다. 자료를 잘 다루기 위해서는 자료의 특성을 알아야 한다. 자료구조의 분류 컴퓨터에서 사용하는 자료들은 크게 단순 자료구조와 복합 자료구조로 나눌 수 있다. 단순 자료구조는 프로그래밍 언어에서 기본적으로 제공하는 정수, 실수, 문자 등을 의미하고, 복합 자료구조는 여러가지 자료들이 복합적으로 구성된 자료구조로 다시 선형 자료구조와 비선형 자료구조로 나눌 수 있다. 선형 자료구조 선형 자료구조(linear data st..

[C/C++] 백준 11497번 - 통나무 건너뛰기

11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 이 문제는 통나무들이 원형으로 놓여있고, 맞닿은 두 통나무의 높이 차이를 최소로 만들도록 통나무를 배치하는 문제이다. 처음에는 단순히 통나무의 높이를 오름차순으로 정렬을 해보았다. 그럼 배열 상에 맞닿아있는 요소들은 높이 차가 최소가 되겠지만 문제는 양 끝에 있는 통나무들이다. 양 끝에 있는 통나무들의 높이 차이는 항상 최대가 될 것이다. 그래서 생각한 것이 인덱스 기준으로 제일 큰 값과 가운데 있는 값을 교환하는 방법이었다. 이렇게 하면 단순 오름차순 방법보다..

[C/C++] 에라토스테네스의 체

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 n보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 알고리즘은 다음과 같다. 2부터 n까지 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않음) 더 이상 반복할 수 없을 때까지 2번, 3번을 반복한다. 위 과정을 사진과 함께 보자. 1번 과정) 2부터 n(26)까지 모든 자연수를 나열한다. 2번, 3번 과정) 남은 수 중에서 가장 작은 수 i(2)를 찾고 i의 배수를 모두 제거한다. 2번, 3번 과정) 남은 수 중에서 가장 작은 수 i(3)를 찾고 i의 배수를 모두 제거..

[C/C++] BFS(Breadth-First Search)

BFS(Breadth-First Search, 너비 우선 탐색)는 가까운 노드를 먼저 탐색하는 그래프 순회 알고리즘이다. 그래프 탐색(Search)은 임의의 한 노드를 시작으로 다른 노드들을 방문하는 것을 말한다. 그래프 탐색 알고리즘을 알아보기 전에 그래프를 다루는 방법을 알아보자. 그래프는 노드(Node 혹은 정점, Vertex)와 간선(Edge)으로 표현된다. 프로그래밍에서 그래프를 표현하는 방식은 크게 2가지 방식이 있다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 graph[i][j]와 같이 노드간의 연결 관계를 빠르게 알 수 있다. 노드 간의 모든 연결 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 인접 리스트(Adj..

[C/C++] DFS(Depth-First Search)

DFS(Depth-First Search, 깊이 우선 탐색)는 그래프의 깊은 부분을 먼저 탐색하는 그래프 순회 알고리즘이다. 그래프 탐색(Search)은 임의의 한 노드를 시작으로 다른 노드들을 방문하는 것을 말한다. 그래프 탐색 알고리즘을 알아보기 전에 그래프를 다루는 방법을 알아보자. 그래프는 노드(Node 혹은 정점, Vertex)와 간선(Edge)으로 표현된다. 프로그래밍에서 그래프를 표현하는 방식은 크게 2가지 방식이 있다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 graph[i][j]와 같이 노드간의 연결 관계를 빠르게 알 수 있다. 노드 간의 모든 연결 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 인접 리스트(A..

[C/C++] 백준 2003번 - 수들의 합 2

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 이 문제는 연속된 수들의 부분합을 찾는 문제이다. 배열을 가리키는 포인터를 두 개(투 포인터)두어서 부분합을 계산하는 방식으로 해결했다. 이 문제에서는 4가지 상황이 있을 수 있다. 부분합이 m가 같을 때 count를 하나 증가시키고 end포인터를 하나 증가시켜 그 값을 부분합에 더한다. 부분합이 m보다 작을 때 end포인터를 하나 증가시켜 그 값을 부분합에 더한다. 부분합이 m보다 클 때 start포인터가 가리키는 값을..

[C/C++] 백준 1021번 - 회전하는 큐

1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 위 문제의 3가지 연산을 action1, action2, action3라고 칭하겠다. 입력받은 숫자를 찾기 위해 action2와 action3 중 무엇을 하는 것이 더 최소의 연산 수 인지를 확인하는 문제이다. 크기(n)가 9인 숫자열을 기준으로 생각해보면 쉽게 규칙성을 찾을 수 있다. 위 표는 target을 찾기 위해 action2와 action3를 몇 번씩 해야하는 지에 대한 표이다. action2와 action3 횟수의 합이 항상 덱의 크기가 나오는 것..

[C/C++] 백준 10610번 - 30

10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 이 문제는 3의 배수의 성질을 이용하면 쉽게 해결할 수 있다. 3의 배수는 각 자리의 수를 더했을 때 3으로 나누어 떨어지는 성질을 갖고 있다. 이 문제는 3의 배수가 아닌 30의 배수를 구해야 하므로 일의 자리 숫자가 0이어야 한다. 또 가장 큰 수를 찾아야 하기 때문에 숫자를 문자열로 입력받아 내림차순으로 정렬했다. 정렬된 문자열의 일의 자리가 '0' 인지와 3의 배수인지를 검사해서 문제를 해결했다. #include #include #include using n..