맞았습니다!!

클래스 (생성자, 접근제한자, 필드와 속성, 메소드)

2022.02.12·

C#

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

C# 백준 13913 숨바꼭질 4 (너비우선탐색)

2022.02.10·

PS/BOJ

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[]..

너비 우선 탐색 (Breadth First Search, BFS)

2022.02.10·

PS/Algorithm

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

C# 백준 1261 알고스팟 (DFS + BFS)

2022.02.09·

PS/BOJ

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,..

BigInteger 구조체(큰 정수의 처리)

2022.02.09·

C#

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

C# 백준 1012 유기농 배추 (너비우선탐색, 깊이우선탐색)

2022.02.08·

PS/BOJ

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

C# 백준 11051 이항 계수 2 (페르마의 소정리, 분할 정복 알고리즘)

2022.02.07·

PS/BOJ

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

C# 백준 18291 비요뜨의 징검다리 건너기(분할 정복 알고리즘)

2022.02.07·

PS/BOJ

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개를 모두 밟는 경우를..

C# 백준 3197 백조의 호수(너비우선탐색)

2022.02.06·

PS/BOJ

3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net IDEA 만약 문제가 "얼음이 전부 녹는 데 걸리는 시간은?" 이었다면 정말 간단히 풀 수 있는 문제다. 이 문제의 함정은 얼음이 녹을 때마다 백조가 만날 수 있는지 없는지 여부를 확인한다는 것에 있다. 여기서 '매일 녹여보고 확인해보면 되지 않을까?' 생각했지만 호수의 범위가 가로 1~1500칸, 세로 1~1500칸이다. 만약 이 방법을 사용한다면 최대 225만칸을 확인해야하는데 무조건 시간초과가 나올 것이다. 다른 분들의 풀이를 ..

switch 문

2022.02.06·

C#

어떤 데이터의 값으로 여러 분기를 나누어야할 때 if문을 반복하는 것보다 더 간단한 방법이 switch문을 활용하는 것이다. switch(데이터) { case 값 : } 형태를 갖는다. using System; class program { static void Main() { int score = int.Parse(Console.ReadLine()); switch (score / 10) { // 입력된 score 값을 10으로 나눈 몫을 확인한다. case 10: Console.WriteLine("Perfect"); break; case 9: Console.WriteLine("Exellent"); break; case 8: Console.WriteLine("Great"); break; case 7: Co..

if, while, for 문

2022.02.06·

C#

if문 조건을 지정하고 지정한 조건에 맞는 경우 코드를 실행한다. 여러가지 경우를 따로 지정할 수 있고, 조건에 맞는 경우와 그렇지 않은 경우, 이렇게 하나의 집합과 여집합으로 나누어 실행한다. 조건은 위에서 아래로 순차적으로 확인하기 때문에 다음 조건이 부분집합인 경우는 무시될 수도 있다. 여러 분기를 나누어야할 때는 조건의 순서를 잘 생각해서 구성해주어야한다. if문으로 조건을 나누다 보면 난잡하고 읽기 어려운 코드가 되기도 한다. 코드를 짜기 전에 조건을 먼저 잘 나누면 복잡한 if문을 간단하게 줄일 수도 있다. using System; public class Product { public string name; public int price; public Product(string Name, in..

자료형

2022.02.06·

C#

정수 자료형 자료형 설명 범위 크기 byte 부호 없는 정수 0~255 8bit sbyte 정수 -128~127 8bit short 정수 -32,768~32,767 16bit ushort 부호 없는 정수 0~65,535 16bit int 정수 -2,147,483,648~2,147,483,647 32bit uint 부호 없는 정수 0~4,294,967,295 32bit long 정수 -922,337,203,685,477,508~922,337,203,685,477,507 64bit ulong 부호 없는 정수 0~18,446,744,073,709,551,615 64bit char* 유니코드 문자 16bit *char 형식은 단일 문자를 정수 형태로 표현함 부동 소수점 형식 자료형 설명 범위 크기 float 단..

티스토리툴바