본문 바로가기

전체 글

 (47)
[백준] 14502번 연구소 중복을 허용하지 않는 조합과 BFS를 활용하여 문제를 풀었다. 중복을 허용하지 않는 조합으로 벽 3개를 세운 뒤 BFS를 사용하여 바이러스를 퍼뜨린 후 안전 영역의 크기를 구했다. depth는 벽의 갯수를 의미하고 next는 다음 벽을 세울 위치를 뜻한다. 여기서 2차원 배열의 위치 next를 (i, j) 가 아닌 하나의 정수로 표현을 했다. 예를 들어, 3x3의 배열일 경우 위처럼 표현을 했다. 이중 for문에서 j의 시작을 0으로 한 이유는 만약 1번 위치에 벽을 세우고 2번 위치에 벽을 세우면 마지막 벽은 3번 위치에 세워야 하기 때문에 0부터 시작하게 했다. 하지만 i는 벽을 세워도 다시 위로 올라가는 일이 없으므로 시작을 next / M 으로 했다. checkVirus 함수는 바이러스를 모두 퍼..
[백준] 15686번 치킨 배달 중복을 허용하지 않는 조합을 사용하여 구현해야 한다. 초기값을 설정한다. num이 1이면 해당 위치를 house에 넣고 2면 chicken에 넣는다. 중복을 허용하지 않는 조합의 알고리즘을 사용하여 depth는 현재 폐업하지 않은 치킨집의 갯수를 뜻하고 next는 다음 치킨집의 index 값을 뜻한다. depth == M이면 문제의 조건에 만족하므로 각 집들의 치킨 거리를 계산하여 도시의 치킨 거리를 구한다. 전체 코드 #include using namespace std; vector board(51, vector(51));// 도시 vector house;// 집들의 위치 vector chicken;// 치킨집들의 위치 vector tmp_chicken;// 치킨집들의 경우의 수 int N, M, an..
[백준] 14888번 연산자 끼워넣기 입력 받은 연산자들을 사용하여 중복을 허용하지 않는 순열을 구현하면 된다. 연산자들 중 같은 연산자들이 여러 번 나오는 경우가 있기 때문에 해당 경우를 고려해야 한다. tmp는 연산자들을 조합한 경우의 수를 뜻하고 oper_count는 0번째 자리는 + 갯수, 1번째 자리는 - 갯수, 2번째 자리는 * 갯수, 3번째 자리는 / 갯수를 뜻한다. 예를 들어, 예제 2번이 입력으로 주어지면 oper_count에는 [1, 0, 1, 0]이 들어가고 tmp는 [0, 2] 와 [2, 0] 이렇게 2가지 경우가 들어간다. (0은 +, 1은 -, 2는 *, 3은 / 를 뜻한다) 값들을 입력하고 함수를 호출한다. 중복 연산자는 갯수를 활용하여 처리했다. i는 연산자의 종류로 0은 +, 1은 -, 2는 *, 3은 / 를 ..
[백준] 19699번 소-난다! 몸무게의 합이 소수인 경우만 출력해야 하므로 몸무게의 합이 소수인지 판별해야한다. 에라토스테네스의 체를 사용하여 소수의 값들을 초기화한다. 중복을 허용하지 않는 조합을 사용하여 tmp(선택한 소들의 집합)에 몸무게를 추가하고 M마리의 소를 선택했을 때 M마리 소들의 몸무게를 합하여 소수인지, 중복되는지 확인한다. 정답인 배열을 sort를 사용하여 내림차순으로 정렬 후 출력한다. 전체코드 #include using namespace std; vector isPrime(10005, true);// 소수인지 판별하는 배열 vector check(10005, false);// 중복 몸무게 확인하는 배열 vector cow(10);// 소들의 몸무게 vector tmp(10);// M마리 소들의 몸무게 vecto..
[백준] 21735번 눈덩이 굴리기 처음에 문제를 보고 DP를 생각했으나 앞마당 끝에 도달하지 않고 대회 시간이 모두 경과됐을 경우 또한 고려해야 하여 재귀로 모든 경우의 수를 확인했다. 재귀함수는 대회 시간이 경과된 경우와 눈덩이가 앞마당의 끝에 도달한 경우에 종료되도록 했다. for문을 사용하여 눈덩이를 굴리는 경우와 눈덩이를 던지는 경우를 나누어 구현했다. 전체 코드 #include using namespace std; vector snow(101);// 눈덩이 크기 int N, M; int answer = 0;// 가장 큰 눈덩이 크기 void func(int time, int size, int pos) { if (time == M or pos >= N) {// 대회 시간이 경과된 경우 또는 눈덩이가 앞마당의 끝에 도달한 경우 an..
[백준] 1966번 프린터 큐 중요도가 같을 때를 구분하기 위해 문서들을 pair형태로 정의하여 중요도가 같은 경우 bool형이 true인 문서가 찾고자 하는 문서로 설정했다. 프린터의 가장 앞문서를 뽑아 해당 문서보다 중요도가 높은 문서가 있는지 확인한다. 1) 있을 경우 해당 문서를 큐의 가장 뒤로 보낸다. 2) 없을 경우(해당 문서의 중요도가 가장 높은 경우) order 값을 1 더한 후(어차피 문서 하나는 결국 인쇄해야하기 때문) 해당 문서의 중요도가 인쇄하고자 하는 문서의 중요도와 일치하는지 확인한다. 2-1) 일치하는 경우 해당 문서의 bool값을 확인한 후 true면 order값을 출력하고 false면 numCount[해당 문서의 중요도]를 하나 빼서 인쇄한다. 2-2) 일치하지 않는 경우 numCount[해당 문서의 중..
[프로그래머스] 오픈채팅방 우선 record에 담긴 문자열을 띄어쓰기를 기준으로 나누어야 한다. 그래서 split하는 함수를 따로 구현해주었다. 각각 유저 아이디와 닉네임을 매칭시키기 위해 map을 사용하였다. record의 문자열들 중 하나를 command라 하면 split하면 command[0]에는 명령어가 들어가고 command[1]에는 유저 아이디가, command[2]에는 닉네임이 들어간다. 만약 문자열의 첫 단어가 'E' 또는 'C'로 시작할 경우 "Enter" 또는 "Change"이므로 map에서 해당 유저 아이디의 value 값을 초기화한다. 명령어가 Change일 경우에는 출력값이 없으므로 명령어가 Enter일 경우와 Leave일 경우만 설정해주면 된다. 위와 같이 문자열을 띄어쓰기를 기준으로 split 해준 후 ..
[백준] 3273번 두 수의 합 num 배열은 입력받은 수열을 저장하는 배열이고 ncount는 수열 내에 있는 숫자가 존재하는지 확인하는 배열이다. 숫자를 입력받으면 num 배열에 넣고 ncount[해당숫자]의 값을 1 더해줌으로써 해당 숫자가 num 배열에 존재한다는 것을 표시한다. num 배열에 있는 숫자 num[i]와 합하여 x가 되는 수가 존재하면 ncount[x-num[i]]은 1일 것이다. x-num[i]는 음수가 될 수 있으므로 예외처리를 해줬다. 문제에서 쌍의 갯수를 물어봤으므로 count를 2로 나누어 출력한다. 전체 코드 #include using namespace std; int num[100007];// 수열 저장하는 배열 int ncount[2000007];// 수 존재 여부를 저장하는 배열 int main() ..

티스토리툴바