일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 문자열
- SSAFY
- MST
- DP
- lis
- 순열
- 클래스
- BFS
- dfs
- 우선순위 큐
- Knapsack
- 분할 정복
- 링크드리스트
- 피보나치 수
- 재귀
- 큐
- 조합
- 빠른 입출력
- 스택
- 완전 탐색
- 메모리풀
- 세그먼트 트리
- BeautifulSoup
- 백트래킹
- 그리디
- 이분 탐색
- 중복 순열
- 비트마스크
- 크루스칼
- 시뮬레이션
- Today
- Total
목록큐 (22)
작심 24/7
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 � www.acmicpc.net 안전한 영역의 개수 중 최댓값을 출력하는 문제이다. 먼저 입력받을 때 높이 중 최대 높이를 구한 후 높이 1부터 최대 높이까지 비교해야 한다. 원래 이런 BFS문제들을 풀 때 입력 배열의 비교가 끝나면 값을 0으로 만들어주었지만 이번엔 한 입력 배열로 여러 번 비교해 줘야 하기 때문에 따로 visited 배열을 만들어서 방문 여부를 체크해준다. BFS의 원리는 현재 위치(큐의 front)를 기준으로 상하좌우를 비교해 주는데 안전한 영역일 때인 현재 위치의 높이(ar..
10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 처음엔 두 가지의 버전의 BFS를 만들었다가 애초에 입력받을 때 R과 G를 통일을 해주면 BFS함수 하나만으로도 풀 수 있다는 걸 깨달았다. 이차원 배열 두 가지를 만들어 하나는 정상적으로, 하나는 R과 G를 R로 통일해준다. BFS함수는 늘 짜던 그 방식으로 해주면 된다. #include #include using namespace std; int daltonism = 0, non_daltonism = 0, x, y; void Bfs(..
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 같은 단지인 애들을 BFS로 찾아준 다음 집의 수를 카운트 해주고 단지 배열에 넣어준다. 이차원 배열을 돌면서 값이 1인 곳이 있으면 그걸 시작으로 해당 위치의 상하좌우의 값이 1이면 큐에 그 위치를 넣어놓고 큐가 empty할 때까지 반복해주는 BFS함수를 만들면 된다. #include #include #include #include using namespace std; int cnt = 0, town[625] = { 0 }; void Bfs..
1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있� www.acmicpc.net 백준 유기농 배추와 거의 같은 문제이다. 그룹들 중 가장 큰 그룹을 bfs로 찾아 출력하면 된다. BFS는 현재 위치의 상하좌우가 1이면 큐에 넣고 큐가 빌 때까지 계속 반복해서 비교하도록 만들면 된다. #include #include #include using namespace std; int Max = 0; void Bfs(int i, int j, int N, int M, int arr[][101]) { int cnt = 1; queue q; q..
1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net 이차원 배열을 돌면서 값이 1인 곳이 있으면 그걸 시작으로 BFS 해준다. 해당 위치의 상하좌우의 값이 1이면 큐에 그 위치를 넣어놓고 큐가 empty할 때까지 반복해준다. #include #include using namespace std; int cnt = 0; void Bfs(int field[][51], int i, int j, int M, int N) { queue q; q.push(pair(i, j)); field[i][j]..
1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료�� www.acmicpc.net 현재 문서의 중요도가 가장 클 경우에만 인쇄될 수 있는 조건이다. 1. M위치에 있는 문서가 몇 번째로 인쇄되었는지를 출력해야 하므로 큐에 pair로 중요도와 인덱스를 넣어준다. 2. 현재 문서의 중요도가 가장 큰지 판단해 주기 위해 중요도 배열을 따로 만들어 내림차순으로 정렬해준다. 3. 인쇄될 때마다 카운트 해주고 인쇄되는 문서가 M위치에 있을 때 카운트를 출력한다. #include #include #include #include using namespace..