목록알고리즘 (76)

키베이루's diary

[C++] 백준 7562번 나이트의 이동

1) 문제설명 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 2) 아이디어 나이트의 최소 이동 횟수를 구해야 하기 때문에 bfs를 사용한다. 나이트의 이동 규칙은 (1,2) (1,-2) (2,1) (2,-1) (-1,2) (-1,-2) (-2,1) (-2,-1) 이므로 그에 따른 배열을 만든다. 이에 따라 BFS탐색을 한다면 쉽게 나이트의 최소 이동 횟수를 구할 수 있다. ※ 여러 번의 테스트 케이스를 구해야 하기 때문에 memset을 사용하여..
알고리즘/BFS, DFS 2022. 6. 10. 08:20
[C++] 백준 2178번 미로 탐색

1) 문제설명 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 2) 아이디어 거리의 최소를 찾기 위해 BFS를 사용했다. 처음 좌표를 (1,1)로 설정하고 BFS를 통해 값이 1인 곳을 찾아 탐색하였다. BFS로 탐색하기 때문에 1이 존재하는 모든 구간을 탐색한다. 따라서 전역 변수를 설정하여 1인 곳을 방문할 때마다 카운트를 세어주는 것이 아닌 거리에 따른 변수를 하나 설정하여 카운트를 센다. 또한 방문한 곳을 표시하거나 초기화시켜주지 않으면 큐의 메모리 초과가 일어나므로 ..
알고리즘/BFS, DFS 2022. 6. 9. 11:03
[C++] 백준 11286번 절댓값 힙

1) 문제설명 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 2) 아이디어 우선순위 큐를 선언하고 비교 연산자를 호출하여 절댓값이 작은것이 우선순위가 되도록 swap을 하였다. 만약 절대값이 같은 경우, 둘 중 값이 작은 것이 우선순위가 되도록 swap 하였다. 3) 코드 #include #include #include #include #include #include #include #include using namesp..
알고리즘/기타 2022. 6. 9. 09:05
[C++] 백준 1012번 유기농 배추

1) 문제설명 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2) 아이디어 DFS를 사용하여 1이 연속으로 되어있는 구간일 경우 카운트를 세 주었다. 3) 코드 #include #include #include #include #include #include #include #include using namespace std; priority_queue v; // 우선순위 큐를 오름차순으로 정렬 int arr[55][55]; int cnt = 0; void..
알고리즘/BFS, DFS 2022. 6. 8. 12:57
[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
Prev 1 ··· 4 5 6 7 8 9 10 Next