[문제 링크]https://www.acmicpc.net/problem/15686문제 설명0-빈칸, 1-집, 2-치킨집 치킨거리 = 집(x1, y1)과 가장 가까운 치킨집(x2, y2) 사이의 거리 → |(x1-x2)| + |(y1-y2)|도시의 치킨거리 = 모든 집의 치킨 거리의 합 치킨집을 최대 m개를 골랐을 때, 도시의 치킨거리의 최소값을 구한다. 문제 풀이도시에 대한 정보를 입력받으면서 치킨집과 집의 위치 정보를 리스트에 따로 저장한다.dfs( ) : dfs 알고리즘을 사용해서 m개의 치킨집을 고른다. 이 때, 치킨집의 위치를 따로 저장한 리스트를 사용해서 m개의 치킨집을 고른다.houseChicken( ) : 하나의 집에 대해서 m개의 치킨집을 돌면서 거리가 가장 가까운 치킨집과의 치킨거..

[문제링크]https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 설명문자열에서 같은 값이 연속해서 나타는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현한다.압축하여 표현한 문자열 중 가장 짦은 것의 길이를 구한다. 문제 풀이문자를 압축하는 패턴 길이의 범위를 1 ~ (문자열 길이 / 2) 로 해서 각 패턴별로 문자열을 압축하는 방법을 모두 구한다. 그 중에서 문자열의 길이가 가장 짧은 단위를 찾는다. 압축 패턴 길이의 범위는 1 ~ (문자열의 길이 / 2..

[문제 링크]https://www.acmicpc.net/problem/14502문제 설명0 - 빈 칸, 1 - 벽, 2 - 바이러스빈 칸에 벽을 3개 세워서 바이러스가 퍼지는 것을 최소로 한다.이 때, 바이러스가 퍼질 수 없는 곳인 안전 영역 크기의 최대값을 구한다. 문제 풀이이 문제를 풀기 위해서는 크게 세 가지로 나눌 수 있다.3개의 벽을 세우는 경우의 수 구하기 → DFS벽 3개를 세운 후 바이러스가 퍼지는 과정 구하기 → BFS안전영역의 크기를 구하고 안전영역의 최대값 구하기그 전에, 입력받을 때 바이러스의 위치 정보를 따로 리스트에 저장했다.(바이러스가 퍼지는 것을 계산할 때 사용하기 위해서)//바이러스가 있는 위치를 리스트에 따로 저장if (map[i][j] == 2) {virus..

[문제 링크]https://www.acmicpc.net/problem/6603문제 설명하나의 테스트 케이스에 k와 k개의 수로 이루어진 집합 S를 입력받는다.집합 S에서 6개의 수를 고르는 방법을 사전순으로 모두 출력한다. 6개의 수를 고를 때, 숫자의 순서는 상관없다. 문제 풀이백트래킹 풀이cnt = 고른 숫자의 개수, start = 반복문 시작 인덱스start ~ k 를 돌면서 숫자를 하나씩 선택한 후, 재귀호출 한다. 재귀 호출을 할 때는 현재 선택한 수의 바로 다음 위치부터 탐색을 시작하도록 start = i + 1 로 설정한다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;..

[문제 링크]https://www.acmicpc.net/problem/15649문제 설명자연수 N과 M이 주어졌을 때, '1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열'을 모두 구하는 프로그램을 작성하시오 입력자연수 N과 M(1 출력사전 순으로 증가하는 순서로 수열 출력입출력 예시입력예시출력예시3 11234 21 21 31 42 12 32 43 13 23 44 14 24 3 문제 풀이DFS를 사용해서 백트래킹 풀이재귀 호출을 통해서 1 ~ n까지 돌면서 중복없이 m개의 수를 탐색한다.종료 조건 : count가 m과 같으면 해당 수열을 출력하고 재귀 호출 종료(1) ArrayList 사용(나의 풀이)ArrayList의 contains() 함수를 사용해서 중복체크를 하고, 재귀가 종료되면 A..

[문제링크]https://www.acmicpc.net/problem/14501문제 설명상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.오늘부터 N+1일째 되는 날 퇴사를 하기 위해서 남은 N일동안 최대한 많은 상담을 하려고 한다.하루에 하나씩 서로 다른 사람의 상담이 잡혀있고, 각각의 상담은 상담을 완료하는 데 걸리는 시간 T_i, 상담을 했을 때 받을 수 있는 금액 P_i로 이루어져 있다.하나의 상담을 하는데 필요한 기간이 1일보다 클 수 있기 때문에 모든 상담을 수행할 수 없다.예를 들어 N=7인 경우 상담 일정표가 다음과 같을 때, 1일의 상담을 수행하면 2일, 3일의 상담은 수행할 수 없다.N+1일 이후부터는 회사에 없기 때문에 6일, 7일의 상담은 수행할 수 없다.퇴사 전 할 수 있는 상담의..