겜돌이의 개발일지

문제 백준 1707 이분 그래프 C++ 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 풀이 모든 정점을 bfs로 돌면서 색깔을 확인해줍니다. 인근 노드와 색깔이 같다면 이분 그래프가 아니므로 즉시 break 후 Ispipartite를 false로 설정합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

문제 백준 1806 부분합 C++ 1806번: 부분합 첫째 줄에 N (10 ≤ N >..

문제 백준 3055 탈출 C++ 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 풀이 고슴도치의 위치에서 bfs를 실행합니다. time이 늘어날 때만, 물을 확산해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 ..

문제 백준 1197 최소 스패닝 트리 C++ 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용합니다. 1. 간선들을 가중치 기준 오름차순으로 정렬합니다. 2. 간선의 시작과 끝이 연결되지 않았다면 (부모가 같지 않다면) 연결하고 가중치를 더해줍니다. 2-1. 시작과 끝이 연결된 경우에는 해당 간선은 연결할 필요가 없으므로 무시합니다. 3. 간선 배열을 모두 확인해 준 뒤 답을 출력합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10..

개요 대리자, 메서드를 매개변수처럼 넘길 수 있게 해 줌. 매개 변수의 데이터 형식과 반환형은 참조할 메서드의 매개 변수의 데이터 형식과 반환형에 맞추어야 함. 선언 delegate 반환형 delegate명(매개변수)

문제 백준 1520 내리막 길 C++ 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 풀이 Top-down 방식의 DP입니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 #include using namespace std; int dx[] = { 0, 0, -1, 1 }; int dy[] = { -1, 1, 0, 0 ..

개요 Static 필드는 인스턴스를 생성할 때마다 메모리에 새로 생성되는 Non-static 필드들과 다르게 프로그램 실행 후 해당 클래스가 처음으로 사용될 때 한 번 초기화되어 동일한 메모리를 사용한다. Static 변수 (정적 변수)는 인스턴스에 종속적이지 않고 클래스에 종속적인 변수이다. 호출 시에는 [클래스명.변수 이름]으로 호출한다. Static 메서드 (정적 함수) 또한 인스턴스에 종속적이지 않고 클래스에 종속적인 메서드이다. 마찬가지로 호출 시에는 [클래스명.메서드 이름]으로 호출한다. Static 메서드에서는 정적 변수가 아닌 일반 멤버 변수를 호출할 수는 없다. Static 클래스 (정적 클래스)는 모든 클래스 멤버가 static으로 선언되어야 하고 생성자를 만들 수 없다. (Static..

문제 백준 14499 주사위 굴리기 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 풀이 map에 관한 입력을 받고, 주어진 입력에 따라 주사위를 동서남북으로 움직이며 조건을 수행합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50..

문제 백준 1717 C++ 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 풀이 bfs로 접근했으나 시간 초과가 나왔습니다. Union - Find를 활용합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 #incl..

문제 백준 2206 C++ 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 풀이 일반적인 BFS 문제였습니다. 다른 문제들과 거의 비슷한데, 벽을 1번까지는 뚫을 수 있으므로 방문체크를 3차원으로 합니다. (x, y, 벽 부순 횟수) 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4..