개발하는 리프터 꽃게맨입니다.

1. 문제 10051https://www.acmicpc.net/problem/11051 1) 주의해야 할 점모듈러 계산에서는 나눗셈을 정의하지 않기 때문에팩토리얼을 통한 조합 계산이 문제 조건상 허용되지 않는다.그렇기에 파스칼 삼각형을 이용해서 풀어야 한다. 2) 탑-다운 풀이더보기#include  #include  #include  using namespace std; #define MAX 10'007 int N, K; vector> dp; int Combine(int n, int k) { if (dp[n][k] != -1) return dp[n][k]; if (k == 0 || n == 0 || k == n) return dp[n][k] = 1; if (k == 1) return dp[n][k] = ..

1. 개요동적 계획법 (Dynamic Programming, 이하 DP)는 메모리를 적절히 사용하여 알고리즘의 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 것이죠. 예를 들어서 '피보나치 수열' 의 예시를 봅시다.  피보나치 수열은 위와 같은 점화식으로 나타낼 수 있으며이를 가장 간단하게 구현하는 방법은 재귀를 사용하는 겁니다.  이런 식으로 말이죠. 그런데 잘 살펴보면 피보나치 수열을 재귀로 구현하면 상당히 비효율적인 코드 진행을 보입니다. 피보나치 수열 알고리즘을 재귀 함수로 표현한 경우를 상태 트리로 나타내면 위와 같습니다. 이 상태 트리를 보면 알 수 있듯이미 계산된 값을 또 계산하고 있는 것을 볼 수 있습니다...

1. 아이디어1) 음의 가중치가 존재하고, 문제 자체가 음의 사이클 또한 염두하고 있기 때문에 해당 문제는 벨만-포드 알고리즘을 사용하는 것이라고 볼 수 있습니다. 2) 즉, 1번 노드에서 출발하여 그래프에 대해서 최단 거리를 갱신한 뒤 문제의 요구에 맞게 출력을 하면 되겠습니다. 3) 음의 사이클을 분별하는 방법은벨만 포드 알고리즘의 결과 dist 배열과벨만 포드 루프를 1번 더 돌린 dist 배열이 다를경우 음의 사이클 이라고 판단할 수 있습니다.2. 주의할 점1) 가중치의 경우의 수가 int 오버플로를 발생시킬 수 있기 떄문에 long long 이나 __int64를 사용해야 합니다.2) 1번 노드에서 그 어떤 노드로 간선이 존재하지 않는 경우에는 그래프에 음의 사이클이 존재하던 말던,-1 을 N-1..

1. 다익스트라 알고리즘의 한계다익스트라 알고리즘은 최단거리를 찾는 일반적인 알고리즘입니다.그러나 그래프 간선의 가중치의 값이 음수일 경우 항상 최적해를 찾는다는 보장은 없습니다. 물론, 다익스트라 알고리즘이 음수 가중치가 존재한다고 해서 항상 최단거리를 찾지 못하는 것은 아닙니다.   먼저, 우선순위 큐를 사용하지 않는 다익스트라 알고리즘 위 그래프에서 최단거리를 찾아낼 수 없습니다.모든 간선의 가중치가 양수일 경우 방문하지 않은 vertex 중 distance 배열의 값이 최소인 노드는 자명하게 최단거리이기 때문이죠. 그러나 음의 가중치 값이 그래프에 존재할 경우미래에 더 저렴한 경로를 찾을 가능성이 존재합니다.  위와 같은 그래프에서는 우선순위 큐를 사용한 다익스트라 알고리즘으로 최단거리를 찾아낼 ..

스스로 공부한 내용을 정리없이 구어적으로 풀어쓴 포스팅입니다.오로지 제가 볼 기준으로 정리한 글이기에참고하는 것을 추천하지 않습니다.   [객체 지향이란?]객체란 속성과 기능을 가진 구체적은 인스턴스를 말합니다.속성과 기능을 C#코드로 표현할 수 있을까요?속성은 데이터로, 기능은 메소드로 표현하면 됩니다. 객체지향 프로그래밍에서 가장 중요한 역할을 하는 것은 클래스입니다.클래스는 객체를 만들기 위한 청사진인데, 객체를 만들기 위해서 어떤 속성과 기능을 가져야하는지명시된 설게도라고 생각할 수 있습니다. 클래스는 객체가 가지게 될 속성과 기능을 정의하지만 실체를 가지지 않습니다.이런 클래스로 만든 객체가 실체를 가지고 독립적인 메모리 공간을 차지합니다.  모든 클래스는 복합 데이터 형식입니다.복합 데이터 형..

C#에서 call by refence로 매개변수를 날려주는 방법은 2가지 입니다. ref 키워드와 out 키워드를 사용하는 것이죠. 이 2개의 키워드는 90% 동일한 기능을 수행합니다.  그런데 out은 보통 한 개 이상의 매개변수를 출력받고 싶은 경우에사용하는 키워드입니다. 그리고 out 키워드를 이용해서 넘긴 매개변수는 반드시 함수 내부에서 쓰기 동작이 발생해야 합니다.쓰기 동작이 발생하지 않으면 컴파일 오류가 발생합니다.  ref 를 이용해서 out의 기능을 구현할 수는 있지만,out을 사용하는 것이 더욱 가독성이 좋습니다. call by reference 를 할 경우 가급적이면 ref을 사용하고다수의 리턴 값을 저장하고 싶은 경우에는 out 키워드를 사용하도록 합시다.

switch문은 특정 정수형 변수에 대해서분기 처리를 하여 코드의 흐름을 제어하는 문법입니다. C++에서는 switch 문에서 사용할 수 있는 변수는 '정수'로 제한되었습니다.(int, char 등.. 만 사용할 수 있고 float, const char* 등.. 은 사용할 수 없죠) 그러나 C#에서는 다양한 조건식이 허용되는 모습을 보입니다.  이런 식으로 문자열로 분기 처리를 할 수도 있고가장 신기했던 것은 Type 에 대한 분기 처리를 수행할 수 있다는 것이었습니다.  정말 신기합니다!   [케이스 가드]switch문의 case 절의 패턴을 더 구체적으로 만들어주는 추가적인 조건 검사라고 할 수 있습니다.case 절 뒤에 when 절을 붙여 사용합니다.when 절은 if 문처럼 true/false 로..

저는 몇 년간 C와 C++ 만 다뤄왔고,C# 을 공부하면서 생소한 연산자를 몇개 보았습니다. 그것에 대해서 정리하는 포스팅을 작성하겠습니다. [문자열 결합 연산자]  C# 에서는 문자열을 + 연산자를 통해서결합할 수 있습니다. [Null 조건부 연산자]이 연산자는 C# 6.0에서 도입됐습니다?. 연산자가 하는 일은 객체의 멤버에 접근하기 전에 해당 객체가 null 인지 검사하여 그 결과가 참이면 그 결과로 null을 반환하고, 그렇지 않은 경우에는 뒤에 지정된 멤버를 반환합니다.  Player 객체의 _name에 ?. null 조건부 연산자를 이용하여 접근하고 있습니다.player1의 경우에는 _name 이 null 이었기 때문에 player1?._name 은 null 은 반환한것이고player2의 경우..

[데이터 형식] C#은 다양한 종류의 데이터 형식을 제공하고,수와 텍스트, 이미지, 소리를 다룰 수 있는 데이터 형식도 제공합니다. 하지만 이번에 다룰 것은 모든 데이터 형식의 근간을 이루는'기본 데이터 형식', '상수', '열거형' 입니다. [변수]변수를 코드에서 보자면 값을 대입시켜 변화시킬 수 있는 요소이지만, 메모리 쪽에서 보면 '데이터를 담는 일정 크기의 공간'이라는 의미를 갖기도 합니다.그러므로 우리가 C# 코드를 작성하면서 변수를 만들 때는 그 이면에 있는 메모리 세계도 함께 생각해야 합니다. 우리가 변수를 하나 선업하며, 이것은 컴파일러에게 "이 변수에 빌요한 메모리 공간을 예약해줘."라고 알립니다.가장 먼저 데이터 형식을 명시하고 그 다음에 변수 이름을 명시합니다.그리고 문장 종결을 표시..

1. 신장 트리신장 트리(Spanning tree)란 그래프내의 모든 정점을 포함하는 부분 그래프(혹은 트리)이다.신장 트리는 특수한 형태로 모든 정점들이 연결되어 있어야 하고 사이클을 포함하면 안된다.따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1) 개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다.   신장 트리의 경우 BFS, DFS 를 사용하면 도중에 사용된 간선을 모아 만들 수 있다. 신장 트리는 그래프의 최소 연결 부분 그래프가 된다.여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다.n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 ..