Records rather than Memories

키워드(keyword) __abstract 2 __alignof 연산자 4 __asm 4 __assume 4 __based 4 __box 2 __cdecl 4 __declspec 4 __delegate 2 __event __except 4 __fastcall 4 __finally 4 __forceinline 4 __gc 2 __hook 3 __identifier __if_exists __if_not_exists __inline 4 __int16 4 __int32 4 __int64 4 __int8 4 __interface __leave 4 __m128 __m128d __m128i __m64 __multiple_inheritance 4 __nogc 2 __noop __pin 2 __property 2 __p..

C++에서 출력을 하기 위해서 어떻게 해야할까? std: cout (iostream 라이브러리)를 사용하면 C언어에 비해 훨씬 간결하게 출력할 수 있다. std::cout 1 2 3 4 5 6 7 8 9 10 11 #include int main() { std::cout

프로그래밍에서 가장 기초가 되는 변수(variables)의 초기화(initialization)와 할당(assignment)에 대해 알아보자. 컴퓨터 내에서 관점에서 보면 변수는 RAM이라는 메모리에서 특정 위치에 할당된다. 변수 - 변수를 만들기 위해 가장 먼저 정의가 필요한데 다음과 같이 선언함으로써 이루어진다. 1 int x; cs 변수 x를 정수 값을 가지는 변수로 정의했다. 다음 명령문이 실행되면 변수 x에 특정한 메모리 위치가 지정되고 표현식이나 명령문에서 변수 x가 필요할 때마다 해당 특정 메모리 위치를 참조할 것이다. 1 x = 10; cs 그리고 '='를 통해 할당을 한다. 다음 명령문이 실행되면 앞서 지정한 메모리 위치에 10이라는 값을 입력하게 된다. L-value, R-value 대입..

네트워크 플로우 알고리즘이란? - 특정한 지점에서 다른 지점까지 데이터가 얼만큼 흐르고 있는지를 측정하는 알고리즘입니다. 좀 더 쉽게 이해하기 위해 파이프에 흐르는 물의 양을 구하는 방식이라고 설명합니다. 네트워크 플로우는 교통 체증, 물류, 네트워크 데이터 전송 등 다양한 부분에서 활용 될 수 있습니다. 리니지라는 게임에 나오는 마을과 사냥터를 가정해 생각해보자. 말하는 섬에서 폐허의 땅이라는 사냥터까지 가는 길의 폭이 10, 폐어의 땅에서 아덴대륙 가는길의 폭이 5라고 가정해보자. 한 사람이 말하는 섬에서 아덴대륙까지 가는데 1시간이 걸린다면 10명의 사람을 한번에 말하는 섬에서 아덴대륙까지 보낸다면? 다음과 같이 폐허의 땅에서 아덴대륙으로 갈 수 있는 양은 3명이므로 2명은 폐허의 땅에 남게된다. ..

위상 정렬(Topology Sort)이란? 자료구조에 있어서 수를 정렬하는 여러가지 알고리즘이 존재한다. 하지만 위상 정렬은 방향 그래프(Directed Graph)를 정렬하는 알고리즘이다. 쉽게 말해서 순서대로 작업을 수행할 수 있게 그 순서를 결정해주는 알고리즘이다. 스타크래프트라는 게임을 예로 들어보자. 탱크라는 유닛을 뽑고 싶다고 한다면 커맨더센터 짓기 - SCV 뽑기 - 서플라이 디팟 짓기 - 배럭 짓기 - 가스통 짓기 - 팩토리 짓기 - 탱크 뽑기 다음과 같이 탱크를 뽑기 위해서 그 전 작업을 만족해야 다음 작업을 진행할 수 있기때문에 작업의 순서를 정렬해주는 알고리즘이 필요하게 된 것이다. 그런데 여기서 가스통을 짓고 배럭을 지어도 논리적으로 문제가 없다. 팩토리를 짓기 위해 두 가지 작업이..

플로이드 와샬이 무엇인지 알아보기 전에 다익스트라 알고리즘에 대해 먼저 생각해보자. 다익스트라 알고리즘은 특정 하나의 노드에서 시작해 다른 노드로 가는 최단 경로를 구하는 알고리즘이다. 때문에 한번에 하나의 노드에서 시작된 경로밖에 알 수 없는 것이다. 반면 플로이드 와샬 알고리즘은 모든 노드에서 본인 제외 다른 모든 노드로 가는 최단 경로를 구할 수 있다. 플로이드 와샬의 핵심 구조는 각각의 노드에서 출발한 경로가 거쳐가는 정점을 기준으로 최단 거리를 구하는 것이다. 이해하기 쉽게 그래프 예시를 통해 알아보자. 다음과 같이 그래프가 있다면 각각의 노드에서 다른 노드로 가는 비용을 2차원 배열로 정리한다. (자기 자신은 0, 이어지지 않은 경로는 무한) 바로 이 2차원 배열을 반복적으로 갱신하여 최종적으..

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2 x n 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수 를 구하는 프로그램을 작성하시오. 아래 그림은 2x5 크기의 직사각형을 채운 한 가지 방법의 예이다. 해당 문제의 점화식을 세워보자. 2 x 1 크기의 직사각형을 채우는 방법은 2x1 타일 하나로 채우는 방법 하나이다. 2 x 2 크기의 직삭각형은 2x1 타일 2개 혹은 1x2 타일 2개로 두가지 이다. 여기서 규칙을 찾아야 하는데 만약 열이 N인 직사각형을 채운다고 하면 N-1번째까지 채운 방법에서는 오직 2..

다이나믹 프로그래밍은 하나의 문제를 풀기 위해서 다른 범위의 값을 이용해 효율적으로 문제를 푸는 방식이다. 쉽게 말해 한번 했던 계산을 다시 하지 않고 그 값을 이용한다는 의미이다. 식상하지만 이를 고안한 벨만(Richard E. Bellman)은 그냥 멋있어서 이름을 이렇게 지었다고 한다. 보통 동적계획법이라고도 하고 컴퓨팅적 사고력이 필요하기 때문에 문제가 굉장히 많고 프로그래밍 대회에 빠지지 않는 부분이다. 그렇다면 왜 이러한 다이나믹 프로그래밍을 사용할까? 일반적으로 분할 정복 기법은 동일한 문제를 반복해서 풀어야 한다는 단점이 있다. 즉, 문제를 풀어야하는 시간이 늘어나게 된다. 모든 분할 정복이 그렇지는 않지만 대표적으로 피보나치 수열이 그러하다. n번 째 피보나치 수열의 값을 구하기 위해 n..