겜돌이의 개발일지

문제 백준 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..

문제 백준 1987 C++ 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 0, 0 지점부터 DFS를 실행하여 최대 깊이를 구해줍니다. 해당 지점을 방문했는지를 저장하는 mapvisited 배열과 해당 문자열을 방문했는지를 저장하는 charvisited 배열을 모두 사용하여 방문 체크를 합니다. 소스 코드 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 ..

문제 백준 14719 C++ 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 블록을 검은색, 빗물이 차는 곳을 파란색이라고 하면 예시 1 양 쪽 끝에 검은 영역이 있을 때, 그 사이의 모든 영역이 파란 영역이 됩니다. 예시 2 마찬가지로 양쪽 끝에 검은 영역이 있으면, 그 사이의 모든 영역이 파란 영역이 됩니다. 따라서 map을 전부 순회하면서, 블록과 블록 사이의 영역을 모두 구해줍니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2..

문제 백준 13398 연속합 2 C++ 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 점화식을 이용하여 문제를 해결합니다. 소스 코드 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 #include #include using namespace std; int arr[100000]; int dp[100000][2]; int main() { ios::sync_with_stdio(false); cin.tie(0)..

문제 백준 2660 회장뽑기 풀이 각 정점마다 bfs를 해준 뒤 깊이를 비교합니다. 깊이가 더 작으면 갱신해주고, 같으면 추가해줍니다. 소스 코드 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 68 69 70 71 72 73 #include #include #include #include #include using namespace std; vector v[51]; bool visited[51]; int N; i..

개요 C++의 STL 중 하나로, 한 번에 한 타입만 저장 가능합니다. 이번 게시글에서는 vector의 선언과 초기화에 대해 다뤄보겠습니다. 상세 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; int n, m; // 기본적인 1차원 vector 선언 vector v; // 크기가 5인 1차원 vector 선언 vector v(5); // 크기가 5이고 초기값이 1인 1차원 vector 선언 vector v(5, 1); // 기본적인 2차원 vector 선언 vector v; // n x n 2차원 vector vector v(n, vector(n)); // 초기값이 1인 n x m 2차원 vector vector v(..