맞았습니다!!

C# 백준 20162 간식 파티 (동적계획법)

2022.02.19·

PS/BOJ

20162번: 간식 파티 서울이는 입맛이 까다로운 고양이다. 입맛이 까다로운 서울이는 전에 먹었던 간식보다 더 맛있는 간식만 먹는다. 서울이는 간식의 평점이 높을수록 맛있다고 느낀다. 집사는 서울이에게 N 일 www.acmicpc.net IDEA 이 문제는 아주 오래전 시도했다가 틀린 문제다. 입출력만 겨우겨우 하던 당시에는 너무 어렵다고 생각해서 취침 시간을 12분 남겨놓고 포기했던 모양이다. 문제를 간단히 정리하면 이렇다. 1. 서울이는 N일 동안 이어지는 간식 파티에서 간식을 골라 먹는다. 2. 서울이는 이전에 먹었던 간식보다 더 평점이 높은 간식만 먹는다. 3. 간식 파티가 끝날 때까지 서울이가 먹은 간식의 평점 총합의 최고치는? 오늘이 i일이고 오늘 주어지는 간식의 평점을 snack[ i ], ..

C# 백준 12100 2048 (Easy) (백트래킹, 브루트포스)

2022.02.19·

PS/BOJ

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net IDEA 브루트포스 문제는 복잡한 생각을 할 필요가 없어서 좋다. 한 때 재밌게 하던 2048 게임을 구현하는 문제다. 모든 가능성을 탐색해서 원하는 결과를 뽑아내면 된다. 탐색 과정에서 이전 과정을 기억해두고 되돌아가 다른 경로를 탐색할 수 있도록 하는 것이 관건이다. N * N 크기의 배열을 스택에 담아 탐색 과정을 관리하도록 했다. 처음에는 N * N 배열을 매개변수로 하는 재귀 호출로 구현했다. 그런데 매개변수로 받아온 데이터는..

C# 백준 9184 신나는 함수 실행 (메모이제이션)

2022.02.18·

PS/BOJ

9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net IDEA 코드가 문제에 그대로 제시되어있어서 그대로 해봤다. w(11,11,11)만 해도 구하는데 몇분 걸린다. 이런 재귀호출의 경우 똑같은 매개변수로 호출된 메소드가 엄청나게 많다. 그럼 첫 호출에 어떤 값에 대한 정보를 기억해두면 두번째부터 불필요한 호출은 줄일 수 있다. 이렇게 여러번 호출될 값을 미리 저장해놓고 다음 호출에 저장된 값을 바로 출력해주는 방법을 메모이제이션 이라고 한다. 간단히 3차원 배열로 구현했다. CODE using System; clas..

C# 백준 2580 스도쿠 (백트래킹)

2022.02.18·

PS/BOJ

2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net IDEA 아주 오래전 군복무 중에 도전했던 문제다. 한창 재귀호출에 대해 (어설프게) 공부하고 있을 때 였는데 백트래킹이라는 것을 연습해보려 몇문제 덤벼들었다가 뼈도 못추린 적이 있었다. 그 때는 대강 이런 알고리즘을 생각했던 것 같다. 1. 입력을 받는다. 동시에 빈칸의 수를 센다. 2. 모든 칸을 순차적으로 확인한다. 3. 빈칸이라면 경우의 수를 파악한다. 4. 만약 한 가지 경우의 수만 있다면 그 칸을 채운다. 5. 아니라면 다음 칸을 확인한다. 6. 끝까..

C# 백준 3687 성냥개비 (동적계획법)

2022.02.17·

PS/BOJ

3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net IDEA 성냥개비는 2개부터 주어진다. 1개의 성냥개비로는 만들 수 있는 숫자가 없다. 각 숫자를 만드는데 필요한 성냥개비의 수는 다음과 같다. 1 2 3 4 5 6 7 8 9 0 2개 5개 5개 4개 5개 6개 3개 7개 6개 6개 큰수를 만들기 위해서는 가능한 자릿수를 많게, 앞자리를 크게 해주면 된다. 단 2개의 성냥개비만 있으면 자릿수를 하나씩 늘려버릴 수 있다. 한개만 더 있으면 맨 앞자리를 1에서 7로 바꿀 수 있다. 가장 큰 숫자를 만들기는 이렇게 간단히 ..

열거형(enum)과 Flag Attribute 클래스

2022.02.14·

C#

입력에 따라 분기를 나누어 처리할 때 분기마다 번호를 부여해주는 방법을 주로 사용했다. 예를 들어 체스 프로그램을 만든다고 하면 백은 양수, 흑은 음수로 킹은 1, 퀸은 2, 비숍은 3, 나이트는 4, 룩은 5, 폰은 6 이런식으로. 체스 정도면 어느정도 가독성을 유지할 수 있겠지만 만약 더 다양한 분기를 나누는 경우엔 코드를 한참 짜다 돌아봤을 때 1번이 뭔지, 5번이 뭔지, 27번이 뭐였는지 알아보기 힘들 수 있다. 이런 불편함을 막고 개발자의 편의를 보장하기 위해 enum 자료형이 있다. 열거형 자료는 enum 키워드로 선언하고 항상 정수 기반이기 때문에 사용할 수 있다. 그럼 체스 기물들은 이런 식으로 표현할 수 있다. using System; class Program { enum Pieces :..

C# 백준 1655 가운데를 말해요 (최소, 최대 힙)

2022.02.13·

PS/BOJ

1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net IDEA 자료를 입력 받음과 동시에 정렬을 해내야하는 문제다. 중앙값을 입력과 동시에 최신화 해주어야하기 때문에 자료는 항상 중앙값에 한해 정렬된 상태를 유지한다. "어떤 자료 구조를 사용하고 어떻게 입력을 받아 정렬 상태를 유지해낼 것이냐"가 이 문제의 빡센 0.1초의 시간 제한을 뚫을 수 있냐 없냐를 결정하는 문제다. 먼저 일반적인 배열을 떠올렸다. 가장 작은 값이 맨 앞으로 오는 오름차순 정렬을 유지한다. 매 N번째 입력마다 Binary S..

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

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 이 되는 식 이렇게 하면 물론 간단한 덧셈 뺄셈은 쉽게 구현 가능하지만 곱셈은? 나눗셈은? 답이 안나온다. 심지어 저런 식으..

티스토리툴바