완전탐색

문제https://www.acmicpc.net/problem/1759 풀이문제에서 주어지는 조건은 다음과 같다.주어지는 알파벳의 개수가 최대 15개 ⇒ 완전탐색?주어지는 L개의 알파벳 중에 C개의 알파벳을 중복없이 고르기 ⇒ 순열? 조합?암호를 이루는 알파벳을 증가하는 순서대로 배열하기 ⇒ 입력받은 알파벳을 정렬하기암호는 최소 1개의 모음, 최소 2개의 자음으로 구성하기 ⇒ 가능성이 있는 암호인지 확인하기 위해 모음의 개수와 자음의 개수 세기a b c는 암호가 될 수 있지만 b a c는 암호가 될 수 없다. 이는 순서가 있는 것처럼 보여, 순열로 풀어야 한다고 생각할 수 있다. 하지만 알파벳이 정렬된 상태에서 고르는 것이므로, 현재 알파벳의 앞부분을 확인하지 않는다. 따라서 조합을 사용하면 된다. // ..

문제https://www.acmicpc.net/problem/14889 풀이N명을 N / 2명씩 두 개의 팀으로 나눠야 한다. 즉, N명 중에서 N / 2명을 고르는 것(순서 상관X)이므로 조합을 사용하면 된다.  DFS 메서드(재귀)를 통해 N / 2명을 다 고른 후, 스타트 팀의 능력치와 링크 팀의 능력치를 구해야 한다. N / 2명을 고를 때 이미 방문 처리를 했으므로 방문 처리한 것은 스타트 팀, 하지 않은 것은 링크 팀으로 구분하면 된다.스타트 팀: used[i] = true링크 팀: used[i] = false 스타트 팀과 링크 팀의 능력치를 계산한 후, 두 팀의 능력치 차이를 최소값과 비교해 갱신하면 된다. 코드import java.io.BufferedReader;import java.io...

문제https://www.acmicpc.net/problem/14500 풀이각 칸에서 DFS 탐색을 이용해서 4개 칸을 선택한 뒤, 선택한 배열의 합 중 최댓값을 찾으면 된다. 그냥 DFS 탐색을 이용해서 4개의 칸을 선택하면 ㅗ 모양을 처리할 수 없다는 문제가 발생한다. 그래서 총 2가지 방법을 사용해서 문제를 풀었다.  풀이 1첫 번째 방법은 DFS 탐색을 이용해서 3개의 칸을 선택한 뒤, 선택한 칸 주변의 칸 중 하나를 선택해서 최댓값을 고르는 것이다.  그러나 이 방법은 메모리를  너무 많이 잡아 먹어서 정석 풀이가 아닌 것 같다ㅎ.. 풀이 2두 번째 방법은 DFS 탐색을 이용해서 4개의 칸을 선택하고, DFS 탐색만으로 처리하지 못하는 ㅗ 방향을 따로 만들어서 확인해 주는 것이다. 이때, 회전과..

문제 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 여담진짜 바보인가? 왜 자꾸 중요한 조건을 놓쳐서 틀리는걸까 ㅎㅎ.... 풀이 방식 잘 생각해놓고 이렇게 어이없이 틀릴 때마다 답답.. 제발 문제를 똑바로 다 읽고 정리하고 끝까지 확인하는 습관을 가지자!!! 풀이N의 범위(2 ≤ N ≤ 15)도 크지 않기 때문에 완전탐색 방식으로 문제를 풀었다. (다른 풀이를 찾아보니 BFS 방식으로도 풀 수 있는 듯 하다. 이건 나중에..) 가장 고려해야 할 부분은 소용돌이 장애물이다. 소용돌이 장애물은 2초마다 나타나고 1초 사라지는 형식을 띄고 있다.0초&1초: 나타남, 2초: 사라짐, 3초&4초: 나타남, 5초: 사라짐..

문제https://www.acmicpc.net/problem/2961 여담하나의 재료에 포함된 신맛과 쓴맛인 줄 모르고 각각 나눠서 생각해서 헤맸다. 다행히 반례 예제가 주어져서 틀렸습니다를 마주하지는 않았다. 나름 다 정리하고 풀었는데 또 제대로 읽지 않았나 보다.. 차근차근 고쳐나가야지😢 풀이주어지는 재료의 수가 최대 10개이므로, 완전 탐색을 통해 풀이할 수 있다. 각 재료의 신맛과 쓴맛을 배열에 저장한 뒤, 완탐을 수행하면 된다. 풀이 로직은 다음과 같다.재료를 적어도 하나 사용했다면 신맛과 쓴맛의 차이가 더 작은 값으로 갱신하기minDiff = Math.min(minDiff, Math.abs(sTaste - bTaste))모든 재료를 다 탐색했으면 탐색을 종료하기해당 재료를 선택한 경우와 선택..

문제https://www.acmicpc.net/problem/14620 여담방문 처리가 제대로 되지 않길래 잘 작성했는데 대체 뭐지? 했는데 방문 처리하는 좌표의 값을 잘못 넣어준 것이었다.. 이런 실수가 대체 몇 번인지 진짜.. 백준 풀 때 아주 나쁜 습관만 들어서 큰일났다..ㅋㅋ 풀이화단의 한 변의 최대 길이가 10이고, 설치하는 꽃도 3개이므로 완전 탐색과 백트래킹을 사용해서 풀 수 있다. 설치한 꽃의 개수가 3이 될 때까지 완탐(=dfs 메소드)을 수행해서 최소 비용을 구하면 된다. dfs 메소드에서 중요한 부분은 방문 처리를 하는 부분이다. 꽃을 설치할 수 있을 때에만 방문 처리를 해야 하므로, 네 방향의 좌표를 저장하기 위한 배열을 하나 선언한다.Pos[] pos = new Pos[4] 그 후..

문제https://www.acmicpc.net/problem/2615 여담오랜만에 "틀렸습니다"를 많이 마주했다^^... 처음에는 육목을 고려하지 않아서, 두 번째는 "검은색 또는 흰색이 이겼을 경우에는 가장 왼쪽에 있는 바둑알의 가로줄 번호와 세로줄 번호를 순서대로 출력" 이라는 문장을 크게 신경 쓰지 않고 풀었기 때문이었다. 특히, 두 번째 반례를 찾아내지 못해서 많은 시간을 소요했다. 제발 문제를 풀기 전에 조건들을 다 정리하고 풀자... 🤦🏻 풀이N = 19이므로 이중 반복문을 사용해도 시간 초과가 발생하지 않는다. 따라서 완전탐색으로 같은 색의 바둑알이 연속해서 5개 나오는지 확인하면 된다. 이때, 2가지를 주의해서 풀어야 한다. 첫 번째는 같은 색의 바둑알이 연속해서 6개 나오는 경우이다...

문제https://www.acmicpc.net/problem/16508 여담완전 탐색하면 for 문만 사용할 것이라는 고정관념에 사로잡혀 있었다. 그래서 결국 오늘도 풀이를 참고해서 풀었다..ㅎ 뭐 이렇게 계속 풀다 보면 실력이 늘겠지! 완탐은 재귀로도 풀 수 있다는 것을 기억하자! 풀이주어지는 책의 개수가 최대 16개이므로 완전 탐색과 백트래킹을 사용해서 풀이하면 된다. 이때, 현재 책을 고르는 경우와 고르지 않는 경우를 나누어서 탐색해야 하며, 자세한 내용은 다음과 같다.현재 책을 고르는 경우책에 포함된 알파벳의 배열 값을 1씩 증가하기count[book.name.charAt(i) - 'A']++total에 현재 책의 가격을 더해서 재귀 호출하기dfs(depth + 1, total + book.pri..

문제 https://www.acmicpc.net/problem/16937 여담 어떻게 풀지 감이 안 잡혀서 다른 분의 풀이를 참고했다. 양심상 풀이를 참고하더라도 완전히 코드를 따라 치지 않으려고 하기 때문에, 풀이 방식을 토대로 다시 생각하고 문제를 풀었다. 풀이를 보기 전에는 엄청 막막해서 풀기 싫었는데, 풀이를 보고 난 뒤에는 생각보다 쉽게 풀 수 있어서 다시 집중해서 풀었다. 이러한 일이 종종 있었는데 "어 이거 좀 어려운데..?"라는 생각이 들면 내가 풀지 못한다고 생각하고 더 이상 생각을 안 하는 것 같다. 진짜 안 좋은 습관인데... ㅎㅏ.. 진짜 6월 내로 꼭 고치자 풀이 이 문제에서 가장 중요한 포인트는 다음과 같다. 두 개의 스티커만 붙일 수 있으며, 두 스티커가 겹치면 안된다. 스티커..