목록코테준비 (119)
끄적끄적
출처 : https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net bfs/dfs qs = q.size()를 해주는 이유는 변수에 담아주지 않으면 q.pop()을 할때마다 q.size()가 줄어들기 때문에 정확한 횟수만큼 돌지 못하기 때문이다.
출처 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net bfs/dfs 문제 나는 bfs로 풀었다. 첫번째 사람의 번호에서 출발하여 두번째 사람까지의 최단 거리가 얼마인지 구해주면 된다.
출처 : https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net bfs " 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. " 이 말이 무슨말인가 싶었는데, 결국 bfs를 통해서 거리를 탐색했을 때 가장 먼 지점까지의 이동 시간을 구하면 되는 것이었다. 출발지점이 정해지지 않았으므로, 완전탐색 + bfs 를 사용해야한다. 방문여부를 체크해주며 queue에 x,y 좌표와 각 지점까지의 소요시간을 넣어주어..
출처 : https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net dfs / bfs dfs 시작점이 방문한적 없고 1이면 수를 1 증가시켜준다음 dfs함수를 실행한다. 탐색 도중 해당칸이 0이거나 방문한 적이 있으면 리턴한다. 또한, 테스트케이스가 여러 개이므로 각 경우마다 배열을 초기화해주는 작업이 필요하다. -> memset(배열, 초기화하고 싶은 값, sizeof(배열)); memset은 cstring을 헤더로 사용한다. (visual studio에서는 헤더를..
출처 : https://www.acmicpc.net/problem/20166 20166번: 문자열 지옥에 빠진 호석 K개의 줄에 걸쳐서, 신이 좋아하는 문자열을 만들 수 있는 경우의 수를 순서대로 출력한다. www.acmicpc.net dfs+해시 아무곳에서나 시작할 수 있고, 방문순서가 다르면 다른 것이며, 이미 방문했던 곳도 다시 방문할 수 있으므로 방문배열을 사용하지 않고 각 위치에서 시작하는 dfs를 적용해준다. 환형탐색이므로 범위를 넘어서면 초기화해주는 작업이 필요하다.
출처 : https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 우선순위 큐를 사용해서 푸는 문제 점수가 높은 순으로 정렬해준다음, 과제를 하루에 하나씩 할 수 있다고 했으므로 각 과제를 할 날을 지정한다. 해당 일자에 다른 과제를 이미 하기로 했으면(방문한 적이 있다면), 날짜를 줄여가면서 찾기. + 배열을 선언할 때 전역으로 선언하면 초기화 해주지 않아도 되지만, 로컬로 선언할 경우 쓰레기값이 들어가서 초기화해줘야함.
출처 : https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 우선순위큐 vector에 입력된 값을 정렬하지 않고 풀었더니 틀렸다고 떠서 정렬을 해주었다. 끝난 시간도 우선순위큐에 넣음으로써 정렬시켜주지만, 시작시간도 먼저 시작된 순으로 들어가야하기 때문에 벡터 정렬을 해줘야 하는 것 같다.