개요 초기화에 관해서 전체 내용을 정리하기 전에, two phase initialization에 대해서 먼저 보고 들어가는 것이 다른 개념들을 이해하는데 도움이 될 거라고 생각이 들었다. 그래서 two phase initialization에 대해 먼저 정리를 하고 나중에 초기화에 관해 전체적으로 보기로 했다. 두 단계로 진행되는 초기화 Swift의 클래스 초기화는 두 단계로 진행이 된다. 첫번째 단계에서는 클래스에 명시된 값에 따라 각 stored property들이 초기화가 된다. 모든 stored property에 대한 초기 상태가 정해지고 나면(예를 들면 메모리 할당), 두번째 단계가 실행이 된다. 두번째 단계에서는 클래스에게 stored property들의 값을 사용자가 설정 할 수 있는 기회가 ..

개요 기본적으로 거의 모든 컴퓨터는 2가지에 데이터를 보관한다. 하나는 디스크, 다른 하나는 메모리(RAM)로 힙 이라고도 한다. 우리가 보는 메모리 관리는 사실상 힙 메모리 관리라고 볼 수 있다. 디스크에 있는 데이터를 바로 가져다 쓰기에는 데이터를 읽는 속도가 굉장히 느리기 때문에, 당장 사용할 프로그램과 데이터들을 메모리에 미리 불러 놓은 뒤에 메모리의 빠른 읽기 속도를 활용하여 프로그램을 실행시킨다. 이는 아이폰에서도 똑같이 동작을 하며, 앱이 실행되는 동안 사용되는 클래스 인스턴스들은 모두 이 메모리 안에 저장이 된다. 메모리 관리라고 하면 엄청나게 거창한 무언가를 하는 것 처럼 느껴지지만 사실 프로그램이 요구로 하는 곳에 메모리 자원을 주고, 프로그램이 더 이상 사용하지 않는 메모리를 회수하는..

문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 예를 들어, 다음과 같은 트리가 있다고 하자. 현재 리프 노드의 개수는 3개이다. (초록색 색칠된 노드) 이때, 1번을 지우면, 다음과 같이 변한다. 검정색으로 색칠된 노드가 트리에서 제거된 노드이다. 이제 리프 노드의 개수는 1개이다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다. 셋째 줄에는..

개요 간단하게 말하면, 최소 신장 트리란 신장 트리 중에서 사용된 가중치 합이 최소인 트리를 말한다. 신장 트리란? (Spanning Tree) 신장 트리란, 그래프 내의 모든 정점을 포함하는 트리를 말한다. 스패닝 트리, 신장 트리, Spanning Tree 모두 같은 말이다. 신장 트리는 그래프의 최소 연결 부분 그래프를 말한다. 여기서 최소 연결이라고 하면, 간선의 수가 가장 작은 것을 말한다. n개의 정점을 가지는 그래프의 최소 간선의 수는 n - 1 개이고, n - 1 개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되며 이를 신장 트리라고 부른다. 한 그래프에는 아래 그림처럼 여러 개의 신장 트리가 있을 수 있다. 결국, 최소 신장 트리란 최소 연결된 부분 그래프들 중 간선 가중치의 합이..

개요 그래프는 정점과 간선으로 이루어진 자료구조이다. 정확히는 정적(vertex)간의 관계를 표현하는 조직도라고 볼 수도 있다. 이런 면에서 트리는 그래프의 일종인 셈이다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 또한 그래프는 네트워크 모델 즉, 객체와 이에 대한 관계를 나타내는 유연한 방식으로 이해할 수 있다. 특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다. 그래프에서 사용하는 용어 정점(vertice) : 노드(node)라고도 하며 정점에는 데이터가 저장된다.(0, 1, 2, 3) 간선(edge) : 링크(arcs)라고도 하며 노드간의 관계를 나타낸다. 인접 정점(adjacent ver..

추후 원본 내용을 수정하여 업로드할 계획입니다...! 이항계수 피보나치 수열 행렬 곱하기 알고리즘 다이나믹 프로그래밍 예제

문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그..

문제 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. 입력 첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. 문제 링크 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 가장 처음 생각한 것은 자릿수에 따른 숫자 등장 횟수였다. 1234라는 수를 생각해보자. 1부터 이 수에 도달할..

문제 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을 총 동원하여 개발한 공간이동 장치를 탑재하였다. 하지만 이 공간이동 장치는 이동 거리를 급격하게 늘릴 경우 기계에 심각한 결함이 발생하는 단점이 있어서, 이전 작동시기에 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 ..

Verification & Validation Testing은 Verification과 Validation의 과정이라고도 할 수 있다. Verification과 Validation의 차이는 앞의 게시물인 Processs Activities에서 잠깐 다뤘었다. 간단하게 둘의 차이점에 대해서 설명을 하자면, Verification은 개발자 입장에서의 테스트이고, Validation은 유저 입장에서의 테스트이다. Static and Dynamic Verification Verification에는 두 가지 종류의 Verification이 존재한다. 하나는 Static, 다른 하나는 그 반대인 Dynamic이다. Static은 Software Inspections 라고 부르기도 하고, Dynamic은 Testin..