객체지향 프로그래밍 언어(Object - Oriented Programming Language, OOP) C# 말고 다른 언어를 배워 본 적이 없어서 객체지향 프로그래밍 언어와 그렇지 않은 언어들과의 차이점, 그로 인한 장단점은 잘 모른다. 배운 걸로 정리해보면 객체지향 언어는 변수, 속성, 메소드 등을 모두가 다같이 공유하는 코드 평야에 놓아두고 골라쓰는 것이 아니라 어떤 객체를 만들어 놓고 그 객체가 각자의 변수, 속성, 메소드 등을 갖고 있어 다른 객체들이 서로의 것에 접근하는 것에 제한을 두는 언어다. 어떻게 보면 객체를 만들 때마다 매번 필요한 요소들을 만들어줘야하니 "메모리를 많이 먹지 않나? 비효율적인 것 아닌가?" 라는 생각을 할 수도 있지만(나도 처음엔 그렇게 느꼈다.) 배우면 배울수록 ..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질 1번부터 시작해야겠다. 모든 정점 V가 범위 내의 정점 V + 1, V - 1, V * 2 와 연결되어있고 가중치는 1이다. BFS로 탐색을 시작해서 찾는대로 시간을 출력하게 하면 될 것 같다. using System; using System.Collections.Generic; class Program { static int n, k; static int[] time = new int[100001]; static bool[]..

BFS는 그래프나 트리의 자료구조에 적용할 수 있는 맹목적 탐색 알고리즘이다. 맹목적 탐색은 주어진 정보에 따라 효율적인 탐색을 실시하는 것이 아닌 이미 정해진 순서로 탐색을 실시하는 방법으로 실용적으로 따져볼 때 매우 비효율적인 알고리즘이지만 구현이 쉽고 간단한 문제에 한해 아주 유용하다. 이름 그대로 트리에서 노드를 깊게 파고드는 것보다 한 계층을 순차적으로 모두 살펴보는 것을 우선하는 알고리즘이다. BFS는 Queue로 구현할 수 있다. 1. 탐색을 시작할 정점을 Queue에 삽입한다. 2. Queue가 비었다면 '9'로 이동한다. 3. Queue의 가장 위에 있는 정점이 현재 탐색 중인 정점이다. 4. 탐색 중인 정점이 찾으려는 자료이면 '8'로 이동한다. 5. 탐색 중인 정점과 연결된 정점을 Q..

1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net IDEA 9376번 탈옥 문제를 보다가 난 아직 준비가 덜 된 것 같아서 분류되어있는 더 쉬운 문제를 찾다 풀게 되었다. 다익스트라 알고리즘의 한 종류인데 특이하게 가중치가 0, 1 밖에 없다. '0-1 너비우선 탐색' 문제다. 이건 BFS로 해결할 수 있다. 정석적인 풀이를 찾아보려고 고수님들의 설명을 찾아보다 justicehui님의 깃허브 페이지에 있는 글을 발견했다. 요약하면 그래프 G에 V개의 정점, E개의 간선이 있고 가중치는 0,..

높은 정확도의 자료 처리를 위해 float, double과 같은 부동소수점 자료형과 decimal 자료형을 사용할 수 있다. 그런데 소수점 아래의 정확도가 아닌 큰 수의 정확한 처리는 어떨까. 자주 사용하는 정수형 int보다 더 큰 값은 long, 더 큰 값은 ulong, 그보다 더 큰 값은 어떻게 처리할까. 한 때는 오버플로우 되는 값을 미리 처리하기 위해 최대값의 절반 범위에서 넘어간 값을 다른 변수에 옮겨담아 자리올림 같은 개념으로 구현한 적이 있다. A0 = 1,073,741,823 ( int.Maxvalue / 2 )일 때 A0 값이 1 증가하면 A1 = 1, A0 = 0 이 되는 식 이렇게 하면 물론 간단한 덧셈 뺄셈은 쉽게 구현 가능하지만 곱셈은? 나눗셈은? 답이 안나온다. 심지어 저런 식으..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net IDEA 두 알고리즘은 이름에서 나타내는 것처럼 탐색의 우선순위가 다르다. 최초 탐색 지점에서 연결된 곳들을 순차적으로 확인하는 너비우선탐색(BFS)은 한 계층의 정점을 모두 확인하고 다음 계층으로 내려가기 때문에 최단거리를 찾는 탐색에서 유리하다. 깊이우선탐색(DFS)은 탐색 경로를 기억해둬야할 때 유리하다. 모든 정점을 탐색해야하는 문제에서는 어떤 알고리즘을 선택해도 시간복잡도 상의 차이는 없다. 이 문제는 모든 정점을 탐색해야하는 문제이기 때문에 너비우선탐색, 깊이우선..

11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net IDEA 이항 계수를 구하는 문제다. 간단한 다음 공식을 사용하면 바로 해결 가능하다. 그런데 여기서 간단하지 않은 것은 주어진 N의 최댓값이 1,000이다. 20!만 계산해도 long의 표현 범위를 넘어가버린다. 그래서 이 문제에도 분할 정복을 사용해야한다. 그리고 값을 10,007로 나눈 나머지를 출력해야한다. 연산을 모두 끝내고 한꺼번에 나머지를 출력하기엔 너무 큰 숫자를 처리하기 어려울 것 같다. 모듈러 연산을 이용하면 좋겠지만 나눗셈에 대한 모듈러 연산은 없다. 페르마의 소정리에 따르면 어떤 수 a가 정수이고 p가 소수일 때..

18291번: 비요뜨의 징검다리 건너기 강을 건너는 방법은, (1 → 4), (1 → 2 → 4), (1 → 3 → 4), (1 → 2 → 3 → 4)의 4가지이다. www.acmicpc.net IDEA 현재 위치에서 1~N까지의 범위 안에 자유롭게 이동이 가능하다. 브루트포스로 작성하는 것도 가능하겠지만 기상청 컴퓨터를 빌려써야 할 것 같다. N개의 징검다리가 있을 때, N이 1이라면 출발점과 도착점이 같은 것이기 때문에 경우의 수는 1이고 2 이상일 때부터 출발점과 도착점 사이의 징검다리들을 각각 밟을 것인지 건너 뛸 것인지 선택하는 것과 같다. N - 2 개의 징검다리 중 1개만 밟는 경우, 2개만 밟는 경우, 3개만 밟는 경우, ..., N - 3 개를 밟는 경우, N - 2개를 모두 밟는 경우를..