목록알고리즘 (76)

키베이루's diary

[C++] 백준 24480번 알고리즘 수업 - 깊이 우선 탐색 2

1) 문제설명 https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 2) 아이디어 문제에서 내림차순으로 방문한다고 하였으므로 노드들을 입력받은 후 내림차순으로 정렬한다. DFS대로 노드를 순회하며 방문한 곳을 체크하고 새로운 배열에 저장한다. 이후 방문한 순서대로 노드를 출력한다. 3) 코드 #include #include #include #include #include #in..
알고리즘/BFS, DFS 2022. 6. 7. 03:39
[C++] 백준 24479번 알고리즘 수업 - 깊이 우선 탐색 1

1) 문제설명 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 2) 아이디어 문제에서 오름차순으로 방문한다고 하였으므로 노드들을 입력받은 후 오름차순으로 정렬한다. DFS대로 노드를 순회하며 방문한 곳을 체크하고 새로운 배열에 저장한다. 이후 방문한 순서대로 노드를 출력한다. 3) 코드 #include #include #include #include #include #in..
알고리즘/BFS, DFS 2022. 6. 7. 02:48
[C++] 백준 2606번 바이러스

1) 문제설명 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2) 아이디어 그래프를 만들어 BFS로 탐색하고 노드들을 방문할 때마다 카운트를 세서 방문한 총노드를 구한다. 3) 코드 #include #include using namespace std; int graph[101][101]={0,}; int c[101]; queue q; int cnt = 0; void bfs(int start, int n) { queue q; q.push(start)..
알고리즘/BFS, DFS 2022. 6. 5. 01:27
[C++] Vector

Vector는 자동으로 메모리가 할당되는 배열로서 데이터의 끝에서 삽입과 삭제가 이루어진다. 배열처럼 연속되는 저장 위치를 사용하므로 데이터의 추가 및 삭제가 간단하게 처리가 된다. 또한 배열과는 다르게 크기는 동적으로 변경이 되므로 메모리의 사용을 줄일 수 있다. 하지만 중간의 데이터를 삭제할 경우 효율적이지 못하므로 삭제가 자주 이루어질경우 리스트를 사용하는 것이 좋다. Vector의 헤더 #include // 벡터의 헤더파일 Vector의 선언 vector v1 // vector 변수명 vector v1 // 2차원 벡터 생성 Vector의 멤버함수 1) 접근 v.begin() : 벡터의 첫번째 데이터 위치 반환 v.end() : 벡터의 마지막 데이터 위치 반환 v.front() : 벡터의 첫번째 ..
알고리즘/기타 2022. 6. 3. 22:16
[C++] 백준 1932번 정수 삼각형

1) 문제설명 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 2) 아이디어 삼각형에서 DP [줄][몇 번째 숫자] = 합의 최대로 설정하고 0으로 초기화한다. 반복문을 2개 돌려서 DP의 최댓값을 체크한다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; long long dp[501][501]={0,}; int main() { int n; long long arr[501][501]; c..
알고리즘/DP 2022. 6. 3. 12:46
[C++] 백준 1149번 RGB거리

1) 문제설명 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2) 아이디어 DP를 이중 배열로 선언한다. DP [1][X] 에는 RED를 DP [2][X]에는 GREEN을 DP [3][X]에는 BLUE를 선택했을 경우로 나눈다. DP [1][X]에서는 DP [2][X-1] or DP [3][X-1]에 RED를 더했을 때의 최솟값을 DP [2][X]에서는 DP [3][X-1] or DP [1][X-1]에 GREEN를 더했을..
알고리즘/DP 2022. 6. 3. 06:05
[C++] 백준 2156번 포도주 시식

1) 문제설명 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2) 아이디어 포도잔이 1개, 2개, 3개, 4개일때 될 수 있는 경우의 수를 하나씩 생각했다. 1개일때 : ( _ ) 2개일때 : ( _ ) ( _ ) 3개일때 : ( _ ) ( _ ) _ || ( _ ) _ ( _ ) || _ ( _ ) ( _ ) 4개일때 : ( _ ) ( _ ) _ ( _ ) || ( _ ) _ ( _ ) ( _ ) || _ _ ( _ ) ( _ ) 1개일때와 ..
알고리즘/DP 2022. 6. 2. 11:40
[C++] 백준 10844번 쉬운 계단 수

1) 문제설명 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2) 아이디어 dp를 이중배열로 받아서 (i / j) 의 인덱스를 각각 (자릿수 / 마지막 수) 로 생각한다. 마지막수/ 자릿수 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 1 1 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 3 1 3 3 4 4 4 4 4 3 2 4 3 4 7 7 8 8 8 7 6 3 마지막 수가 0 일때와 9일때를 제외한 나머지는 dp[자릿수][마지막수] = dp[자릿수-1][마지막수-1] + dp[자릿수-1][마지막수+1] 인 것을 알 수있다. 3) 코드 #..
알고리즘/DP 2022. 6. 2. 09:36
Prev 1 ··· 5 6 7 8 9 10 Next