목록전체 글 (96)

키베이루's diary

[C++] 백준 2667번 단지번호붙이기

1) 문제설명 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 2) 아이디어 처음 좌표는 0,0으로 잡고 가로를 X 세로를 Y로 잡았다. 배열을 순환하다가 값이 1일 경우 DFS함수를 호출하여 카운트를 하나 증가시키고 값을 0으로 초기화시킨다. 이후 다시 X의 좌표와 Y의 좌표에 각각 +1, -1 씩 더하여 DFS를 재귀적으로 호출하였다. 이때 X, Y의 좌표가 1이 아닐 경우 아무것도 하지 않고 return 하기 때문에 1이 연속적으로 붙어있는..
알고리즘/BFS, DFS 2022. 6. 8. 12:30
[C++] 백준 2217번 로프

1) 문제설명 https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 2) 아이디어 문제에 대해서 잘 이해하기만 하면 쉽게 풀 수 있는 과제이다. 로프가 견딜 수 있는 무게가 10, 20 인 경우 각각 10, 10을 들면 되므로 최대 중량은 20이 된다. 다른 예로 로프가 견딜 수 있는 무게가 10, 20, 30 인 경우 10의 무게로 3개의 로프가 전부 다 견딘 다면 최대 중량은 30이 된다. 하지만 전부다 사용할 필요 없이 20, 30의 ..
알고리즘/Greedy 2022. 6. 8. 08:51
[C++] 백준 24445번 알고리즘 수업 - 너비 우선 탐색 2

1) 문제설명 https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 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) 아이디어 문제에서 내림차순으로 방문한다고 하였으므로 노드들을 입력받은 후 내림차순으로 정렬한다. BFS대로 노드를 순회하며 방문한 곳을 체크하고 그 노드를 몇 번째 방문했는지 알기 위해 카운트를 세고 저장한다. 이후 카운트를 저장한 배열을 순서대로 출력한다. ※ 정점을 방문한 순서가 아닌 정점이 몇 번째로..
알고리즘/BFS, DFS 2022. 6. 7. 11:31
[C++] 백준 24444번 알고리즘 수업 - 너비 우선 탐색 1

1) 문제설명 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 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) 아이디어 문제에서 오름차순으로 방문한다고 하였으므로 노드들을 입력받은 후 오름차순으로 정렬한다. BFS대로 노드를 순회하며 방문한 곳을 체크하고 그 노드를 몇 번째 방문했는지 알기 위해 카운트를 세고 저장한다. 이후 카운트를 저장한 배열을 순서대로 출력한다. 3) 코드 #include #include #..
알고리즘/BFS, DFS 2022. 6. 7. 11:24
[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
Prev 1 ··· 7 8 9 10 11 12 Next