끄적끄적

출처 : https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net LIS(Longest Increasing Subsequence, 최장 증가 수열)와 DP를 동시에 이용하는 문제 (LIS를 구하는 방법 중 하나가 DP라고 한다.) - LIS란? 원소가 n개인 배열이 주어졌을 때, 이 배열의 원소를 뽑아 만든 부분 수열 중, 각 원소가 이전 원소보다 크며, 그 길이가 최대인 부분 수열을 의미한다. ex) {6,2,5,1,7,4,8,3} 의 LIS -> {2,5,7..

출처 : https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp 이미 저장되어 있는 값과(현재 날짜에서 상담을 하지 않는 경우), 현재 날짜에서 상담을 하여 저장되는 값 중 큰 값을 저장해주면 된다. cur_max 변수를 사용한 이유 -> 예를 들어 7일에 저장된 값이 60이고 그 값이 그대로 간다면 8일에 저장된 값도 60이어야 하는데, 초기값은 0이니까 대입해주는 작업 필요해서 cur_max 변수를 사용한 것

출처 : https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net bfs 각 칸에 사다리 혹은 뱀이 있을 경우 도착 좌표를 적고, 나머지는 0으로 하여 구별한다. 주사위가 1일때 부터 6일때까지 반복해주고 현재 좌표에 더해서 다음 좌표를 만든다. 다음 좌표가 100일 경우 카운트에 +1해서 출력해준다. 만약 100보다 작을 경우 먼저 다음 좌표에 사다리 혹은 뱀인지 확인해서 0이 아닌 경우 적혀있는 값으로 ..

출처 : 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를 적용해준다. 환형탐색이므로 범위를 넘어서면 초기화해주는 작업이 필요하다.