킹의 개발일지

리스트는 선형적으로(순서가 존재한다는 뜻) 값들을 가지고 있는 자료구조이며, 흔히 배열(array)과 연결 리스트 (linked list)로 나눌 수 있다. 먼저 배열을 살펴보자. 배열(Array) 언어 공부를 할 때 배열의 경우 많이 사용해 보았을 것이다. 예를 들어 숫자 1부터 5까지를 저장하고 싶다면, c언어의 경우 아래와 같이 배열을 선언 할 수 있다. int array[5] = {1, 2, 3, 4, 5} 그렇다면 배열이란 무엇일까? 자료구조에서 배열은 다음과 같이 말 할 수 있다. 메모리 상에 원소를 연속하게 배치한 자료구조 아래 그림을 보면 위 말이 무엇인지 상상할 수 있을 것이다. 배열의 이름은 배열이 저장된 시작 주소를 가르킨다고 보면 된다. 때문에 배열의 인덱스로 데이터를 접근하면 해당..

경쟁적 전염 18405번: 경쟁적 전염 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 이 문제의 경우 bfs 알고리즘을 사용하면 해결할 수 있다. 각 종류의 바이러스들이 있는 2차원 배열이 있다. 바이러스는 1초가 지나면 인접한 정점으로 옮겨간다. 이 때 인정한 정점에 두 종류 이상의 바이러스가 전파될 수 있는데, 이 때는 해당 정점의 값이 작은 바이러스가 먼저 전파된다고 한다. 경과가 지나서 다른 정점에 전파되는 유형의 문제는 for 루프를 돌면서 정점 하나 하나 돌면서 먼저 ..

바닥 장식 1388번: 바닥 장식 1388번: 바닥 장식 형택이는 건축가이다. 지금 막 형택이는 형택이의 남자 친구 기훈이의 집을 막 완성시켰다. 형택이는 기훈이 방의 바닥 장식을 디자인했고, 이제 몇 개의 나무 판자가 필요한지 궁금해졌다. 나 www.acmicpc.net ‘-’와 ‘|’로 이루어진 바닥 장식 모양이 주어질때, 만약 두 개의 ‘-’가 인접해 있고, 같은 행에 있다면, 두 개는 같은 나무 판자이고, 두 개의 ‘|’가 인접해 있고, 같은 열에 있다면, 두 개는 같은 나무 판자로 보고 카운트를 해준다. 다음과 같이 입력이 주어진다면 4개의 길이 판자가 4개가 있음으로 4를 출력해준다. 4 4 ---- ---- ---- ---- 다음 예시는 13을 출력해주면 된다. 7 8 -------- |--..

무한 이진 트리 2078번: 무한이진트리 2078번: 무한이진트리 첫째 줄에 두 정수 A, B(1 ≤ A, B ≤ 2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다. www.acmicpc.net 처음 이 문제를 풀었을 때 테스트 코드는 맞는데, 메모리 초과가 계속 발생해서 고민했던 문제다. DFS를 사용해볼까 고민 했었는데, DFS를 쓰면 밑을 찍고 올라와야 하는데, 바텀업 방식으로 (1,1 로부터 만들기 시작.) 만들다보니 바닥을 찍고 다시 돌아올 수 없을 것 같았다. 그래서 BFS를 사용해서 루트값으로부터 타겟 값이 나올 때 까지 이진 트리를 계속해서 만들었다. 메모리 초과 코드 # 무한 이진 트리 import sys from collections import deque..

위상 정렬이 뭔지 알아보기전에 빠른 이해를 위해 실생활에서 예를 들어보자. 위상 정렬의 예시를 들때, 항상 빠지지 않고 등장하는 대학교의 선수 과목 제도를 생각해보자. 프로그래밍 → 프로그래밍2 → 객체지향 프로그래밍 프로그래밍 → 자료구조 → 알고리즘 이산수학 → 알고리즘 위와 같이 특정 과목에 따른 선수과목들이 있다고 하자. 수강을 하는 순서로는 다양한 방법들이 존재한다. 이산수학, 프로그래밍1, 프로그래밍2, 자료구조, 알고리즘, 객체지향 프로그래밍 순으로 들어도 되고, 이산수학을 안 듣고 프로그래밍1, 프로그래밍2, 객체지향 프로그래밍, 자료구조를 듣다가 알고리즘 과목을 듣기전에 이산수학을 들어주면 된다. 그러나 선수 과목을 지켜야하기 때문에, 이산수학을 안듣고 알고리즘을 들을 순 없다. 실제 c..

BFS는 DFS와 동일하게 컴포넌트의 모든 정점을 한 번씩 순회한다. BFS는 이름에서도 알 수 있듯 깊이를 우선적으로 탐색하는 DFS와는 반대의 성향을 지닌다. DFS가 한 방향으로 아래로 아래로 내려가다 끝을 찍고 다시 돌아와 그 방향으로 다시 아래로 탐색하는것과 달리 BFS는 모든곳을 똑같이 조금씩 탐색한다. 위 그림을 통해서 BFS를 해보자 맨처음 1번 정점을 방문하고 그 다음 단계는 자식 정점의 인접 정점을 우선적으로 탐색하던 DFS와 달리 부모 정점과 인접한 정점들을 우선적으로 탐색한다. DFS였다면 1 → 2 → 5 → … 이런식으로 탐색 했겠지만 BFS는1과 인접한 정점들을 우선적으로 탐색한다. 따라서 순서는 다음과 같다. 1 → 2 → 3→ 4 → 5 → 6 → 7 → 8 → 9 → 10..

주어진 그래프나 트리의 모든 정점을 순회 하고자 할 때 사용 할 수 있는 알고리즘에는 DFS, BFS가 있다. 그 중 먼저 깊이 우선 탐색을 알아보자. 깊이 우선 탐색 이름에 걸맞게 DFS는 아래로 아래로 내려가다가 끝을 찍으면 다시 돌아가서 다른 우물을 다시 아래로 아래로 파는 성격의 알고리즘이다. 위 트리를 DFS로 탐색해보자. 먼저 1번 정점에서 탐색을 시작한다고 하자. 1번 정점에서 아직 방문하지 않은 인접한 정점 중 하나를 선택해 방문한다. 여기서 중요한점은 한 정점으로 부터 아래로 아래로 순회해야하기 때문에, 만약 1번 정점에서 2번 정점을 방문한다 했을 때, 1번 정점의 인접한 정점들을 우선적으로 순회하는것이 아니라 2번정점의 인점한 정점들을 우선적으로 순회한다! 그렇다면 1번에서 출발해 2..

정점간에 이동비용이 정해져있고 출발지부터 목적지까지 최소 비용을 구하려면 어떻게 해야할까? 이 고민을 해결해줄 알고리즘이 다익스트라 알고리즘이다. 이 알고리즘은 출발 정점으로부터 나머지 정점들로의 최단거리(최소 비용)를 구할 수 있게 해준다!! 동작 방식 다익스트라 알고리즘은 다음과 같이 작동한다. 1) 아직 방문하지 않은 정점들 중 거리가 가장 짧은 정점을 하난 선택해 방문한다. 2) 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다. 맨 처음에는 시작점으로의 거리만 0이고 나머지는 다 거리를 무한으로 준다. 그리고 정점 i, j 사이의 거리를 d, 거리 테이블을 dist라고 해보자. dist 1 2 3 4 5 6 0 INF INF INF INF INF 1번에서 바로 갈 수 있는 인접..

스택과 정반대의 역할을 수행하는 큐(queue)라는 자료구조를 알아보자! 큐는 스택과 반대로 FIFO(First in First Out), 즉 가장 먼저 들어온 값이 제일 먼저 나온다! 라는 것이다. 가장 흔한 비유로 큐는 은행 줄서기(?)와 비슷하다고 볼 수 있다. 번호표를 뽑고 가장 먼저 들어온 사람이 업무를 보는것처럼 말이다. 연산 또한 스택처럼 삽입과 삭제가 가장 끝에서 일어난다. 그래서 큐 중간에 있는 값들은 관심이 없다. 그러나 스택은 삽입과 삭제의 위치가 같지만 큐는 삽입과 삭제의 위치가 다르다는 차이점이 존재한다. 스택은 출입구가 top 한군데만 존재했던과 달리, 큐는 입구인 rear와 출구인 front가 존재한다. (뒤로넣고 앞으로 뺀다!) 큐는 pop을 할 때 출구인 front에 있는 ..

백트래킹 기법 백트래킹은 해를 찾는 도중에 ‘막히면’ (즉, 해가 아니라면) 되돌아가서 다시 해를 찾는 기법이다. 모든 경우를 다 탐색하는것이 아니라 해가 아니라면 되돌아가기 때문에 최적화 문제와 결정 문제를 해결하는데 사용될 수 있다. 여기서 결정 문제란 문제의 조건을 만족하는 해가 존재하는지의 여부를 ‘yes’ 또는 ‘no’로 답하는 문제를 말한다. 대표적인 결정 문제로 n-queen, map coloring, 부분 집합의 합 등이 있다. 또한 최적화 문제에는 미로찾기(출구까지 최단경로를 찾는), 부분집합의 합중 원소의 개수가 최대인 부분집합을 찾는 문제 등이 속한다. 백트래킹의 대략적인 흐름은 다음과 같다. 여러가지 선택지들이 존재하는 상황에서 한가지를 선택한다. 선택이 이루어지면 그 선택에 따른 ..