본문 바로가기

vividswan

Notice

블로그 이전 완료

Recent Posts

Popular Posts

Recent Comments

Link

깃허브

Calendar

Tags

더보기

Archives

Visits

Today

Yesterday

완전탐색

Algorithm/BOJ 2022. 3. 16. [BOJ] 치킨 배달(15686) [백준(BOJ)] 15686_치킨 배달 JAVA 문제 : BOJ_15686번 치킨 배달 문제 설명 N*N 크기의 map에서 집과 치킨집이 주어진다. 최대 m 개의 치킨집을 제외한 나머지 치킨집을 다 없애야 한다. 이때 집과 치킨집과의 최소 거리(수직거리의 차 + 수평거리의 차)의 합의 최솟값을 구해야 한다. Solution 완전 탐색(조합) N의 최대 크기는 50, M의 최대 크기는 13이다. 13개의 치킨집에서 7개의 치킨집을 선택하는 조합의 수가 가장 크므로 다음과 같이 계산해보면, 50 * 50(도시의 최대 크기) * 13C7 * 7(모든 경우의 수마다 7개의 치킨집과 거리를 확인해봄) == 30,030,000 이므로 조합을 이용한 완전 탐색으로 해결이 가능하다. Description 조합은 rec..

Algorithm/BOJ 2022. 3. 15. [BOJ] 아기 상어(16236) [백준(BOJ)] 16236_아기 상어 JAVA 문제 : BOJ_16236번 아기 상어 문제 설명 아기 상어가 상하좌우로 움직이면서 물고기를 먹습니다. 이때 물고기는 아기 상어의 크기보다 작은 물고기만 먹을 수 있고, 상어의 크기보다 큰 물고기가 있는 곳은 지나갈 수 없습니다. 가장 가까운 거리에 있는 먹을 수 있는 물고기부터 먹는데, 같은 거리에 있는 물고기가 여러 물고기라면 위 다음 왼쪽에 있는 물고기부터 먹습니다. 또 한 자기의 몸 크기 수만큼의 물고기를 먹으면 몸의 크기가 1 증가합니다. 이러한 조건에서 물고기가 한 번 이동하는 시간을 1초라고 할 때 물고기가 먹을 수 있는 모든 물고기를 먹는데 걸리는 시간을 출력해야 합니다. Solution bfs, 완전 탐색 우선 bfs로 상어의 위치부터 시작..

Algorithm/BOJ 2022. 3. 15. [Programmers] 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT) [Programmers] 기둥과 보 설치(2020 KAKAO BLIND RECRUITMENT) JAVA 문제 : 기둥과 보 설치(2020 KAKAO BLIND RECRUITMENT) 문제 설명 N*N의 벽면이 주어지고 이 벽면에 기둥과 보를 설치, 삭제하는 문제입니다. 기둥은 다른 기둥의 위, 혹은 보의 양 끝 쪽에 설치될 수 있습니다. 보는 양 끝 점 중 한점에 기둥이 있거나, 양 끝 점에 보가 설치되어 있을 시 설치될 수 있습니다. 입력으로 원하는 기둥과 보의 설치, 삭제 유무와 좌표가 주어지며, 출력으로 설치, 삭제가 가능할 때 실행한 뒤의 최종 결과를 출력하는 것이 문제입니다. Solution 구현, 완전 탐색 입력값을 받은 뒤, 이 입력값을 최종 배열에 삽입합니다. 그 후 삽입한 결과(삭제나 설..

Algorithm/Programmers 2022. 3. 15. [Programmers] 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT) [Programmers] 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT) JAVA 문제 : 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT) 문제 설명 크기가 N*N인 자물쇠와 크기가 M*M인 열쇠가 주어집니다. 자물쇠와 열쇠는 각각 홈인 부분과 돌기인 부분이 있습니다. 이때 자물쇠보다 크기가 항상 작거나 같은 열쇠를 90도씩 회전하거나 이동시켜서 자물쇠와 열쇠 서로의 홈과 돌기 부분을 맞추는 것이 문제입니다. solution 메서드에서 맞출 수 있는 경우의 수가 있다면 true, 맞출 수 있는 경우의 수가 존재하지 않는다면 false를 return 해야 합니다. Solution 완전 탐색 만약 어떠한 방법을 써도 맞출 수 없다면 false를 return해야 하기 때..

Algorithm/BOJ 2022. 3. 15. [BOJ] 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해!(20153) [백준(BOJ)] 20153_영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해! C++ 문제 : BOJ_20153번 영웅이는 2의 거듭 제곱을 좋아해! 영웅이는 2의 거듭 제곱을 좋아해! 문제 설명 우선 n 개의 자연수가 주어집니다. 이 n 개의 수를 모두 이진수로 바꾸고 각 자리의 1의 개수를 조회합니다. 각 자리수의 1의 개수가 홀수이면 최종 결괏값에 (2^자리수)를 더해주고, 짝수이면 더하지 않습니다. 이때 최종 결괏값이 최대가 될 수 있도록 n 개의 자연수 중 최대 하나의 자연수를 제외할 수 있습니다. 마지막으로 결괏값을 띄어쓰기 없이 두 번 출력하면 정답입니다. Solution 완전 탐색, 수학 주어질 수 있는 수의 최고값이 2222222이므로, 그에 맞게 2222222의 숫..

Algorithm/AOJ 2022. 3. 14. [AOJ] BOARDCOVER [ALGOSPOT Online Judge(AOJ)] BOARDCOVER C++ 문제 : AOJ BOARDCOVER 문제 설명 테스트 케이스마다 H*W 크기의 게임판이 주어집니다. 게임판의 각 자라니는 검은 칸이나 흰 칸으로 되어있는데, L자 모양의 블록으로 흰 칸이 안 남도록 채워야 합니다. L자 모양의 블록을 자유롭게 회전할 수 있지만, 블록끼리 겹치거나 검은 칸을 덮으면 안 됩니다. 이때 L자 모양의 블록으로 모든 흰 칸을 채울 수 있는 경우의 수를 구하는 문제입니다. Solution 완전 탐색 게임판의 가장 위쪽, 왼쪽의 판부터 시작해서 오른쪽, 아래쪽으로 내려가며 완전 탐색으로 해결해야 합니다. 게임판의 한 칸을 기준 삼아 순회하면서 L자 모양의 블록이 그 칸을 기준으로 회전할 수 있는 네 가지 ..

Algorithm/AOJ 2022. 3. 14. [AOJ] PICNIC [ALGOSPOT Online Judge(AOJ)] PICNIC C++ 문제 : AOJ PICNIC 문제 설명 n 명의 학생이 주어지고, m 개의 가능한 짝의 수가 주어집니다. m 개로 주어진 조건에 맞게 짝을 지을 수 있는 모든 경우의 수를 구하는 문제입니다. 가능하다고 주어지지 않은 학생들 끼린 짝이 될 수 없고, 모든 학생들은 각자의 짝이 있어야 합니다. Solution 완전 탐색 학생의 수가 최대 10명으로 완전 탐색으로 모든 경우의 수를 확인하여 풀 수 있습니다. 최악의 경우 최대 학생 수 10명이 자신을 제외한 9명과 모두 짝이 될 수 있는 경우인데, 이 경우는 9*7*5*3*1이므로 시간제한 안에 해결할 수 있습니다. 해당 학생이 짝을 찾았는지의 유무인 isFind 배열을 만들어 이 배열로 ..

Algorithm/BOJ 2022. 3. 14. [BOJ] 소문난 칠공주(1941) [백준(BOJ)] 1941_소문난 칠공주 C++ 문제 : BOJ_1941번 소문난 칠공주 문제 설명 5 * 5의 map이 주어지고, 각 자리는 'Y' 혹은 'S'로 표현되어 있습니다. 위, 아래, 좌, 우에 서로 인접한 7개의 자리에서 'S' 가 최소 4개 이상 있는 7 자리의 수를 찾는 문제입니다. Solution 완전 탐색, bfs 각 자리에 대한 정보를 벡터에 저장해 줍니다. 저장할 정보는 각 자리의 위치, 'S'인지의 여부입니다. 저장된 상태에서 7개의 자리를 check 해주고 이 7개의 자리에서 'S'가 4개 이상인 경우 bfs를 돌려줍니다. bfs에서 다음을 확인하며 순회해 줍니다. 주어진 크기 안에 있는 map의 자리인지 좌, 우, 상, 하로 인접돼있는지 앞선 완전 탐색에서 check 되어 ..

이전 1 2 다음

티스토리툴바