구름을 채우다

문제 보기 이 문제는 브루트 포스 문제이다. 문제에서 의도하는 바는 9명의 난쟁이 중 키의 합이 100이 되는 7명의 난쟁이를 고르는 것이다. (가능한 경우의 수가 여러 개일 경우 한 가지만 출력한다.) 이제 웬만한 브루트 포스 문제는 막힘없이 풀 수 있는 것 같아서 조금 성장한 느낌이 든다. 문제를 푼 로직은 다음과 같다. DFS를 재귀적으로 사용하여 각 난쟁이를 선택한 경우와 선택하지 않은 경우의 수를 모두 구한다. (19~25번째 줄) 모든 경우 중 한 가지 경우의 난쟁이들을 선택한 뒤, 선택한 난쟁이의 수가 7이고 키의 합이 100인 경우 선택된 난쟁이들의 키를 출력한다. (9~17번째 줄) 이 문제를 풀면서 한 가지 배운 점이 있다면, 한 개의 리스트를 출력할 때, 리스트의 원소마다 구분자를 설..

문제 보기 이 문제는 브루트 포스 문제이다. 이 문제는 2019년 삼성 하반기 SW 역량 테스트에서 나온 두 번째 문제이다. 문제를 푸는데 3일이나 걸렸다... (도움을 주신 정인준 선배님 감사합니다ㅠㅠ) 지금 와서 되돌아보니 풀이의 큰 흐름은 맞았지만, 문제에서 간과하기 쉬운 조건들이 있었다. 이제는 삼성 SW 역량 테스트에서 알고리즘의 구현을 할 수 있는지 묻는 게 아니라, 문제 속에 찾기 힘든 조건들을 포함시키는 게 요즘 추세인 것 같다. 먼저, 백준에 나와있는 윷놀이 판의 그림은 헷갈리는 부분이 있으므로 이를 명확하게 하기 위해서 다음의 그림을 참고하면 좋을 것 같다. 위와 같은 윷놀이 판에서, 모든 경우의 수를 따져야 하므로 말이 지나갈 경로를 정해야 한다. 경로를 어떻게 구성하고 구현할지는 사..

문제 보기 이 문제는 브루트 포스 문제이다. 모든 경우의 수를 따져서 문제에 조건에 해당하는 최적의 결과를 찾아야 하는 게 목적이다. 모든 경우의 수를 따질 대상은 기준점이 되는 (x, y)와 d1, d2이다. (81~84번째 줄) 그리고 각 경우가 유효한 경우인지는 다음과 같이 문제에 명시되어 있으므로 이를 적용해서 필터링한다. (85번째 줄) 맨 처음 문제를 풀 때 다음과 같은 로직으로 문제를 해결하려고 했다. 5번 선거구의 경계를 구한다. 5번 선거구에 포함된 인구를 구한다. 1, 2, 3, 4번 선거구에 포함된 인구를 구한다. 인구가 가장 많은 선거구와 가장 적은 선거구의 차이가 최소가 되는 경우를 찾는다. 그런데 2번 과정에서 5번 선거구에 포함된 인구를 구할 방법이 떠오르지 않았다. 문제를 계..

문제 보기이 문제는 브루트 포스 문제이다. n의 범위가 50이하이고, 선택해야하는 치킨집의 갯수가 13이하이므로, 브루트포스임을 유추할 수 있다.나는 처음에 문제를 제대로 이해하지 못해서 BFS 문제라고 생각했다. 하지만 모든 경우의 수를 따져봐야 하기때문에, 브루트포스임을 나중에 깨달았다.문제에서 주어지는 정의는 다음과 같다. 치킨거리: 집과 가장 가까운 치킨집까지의 거리도시의 치킨거리: 모든 집의 치킨거리의 합 최대 M개의 치킨집을 고르고, 최솟값이 되는 도시의 치킨거리를 구해야한다.따라서 주어진 모든 치킨집에서 m개를 선택하는 조합(Combination)을 사용해야한다.문제를 해결하기 위한 로직은 다음과 같다. 1. 주어진 치킨집에서 M개의 치킨집을 선택할 수 있는 모든 경우의 수를 조사한다. (조..

문제 보기이 문제는 브루트 포스 문제이다.완전탐색을 위해서 DFS를 재귀적으로 구현하였다.문제를 풀기위한 로직은 다음과 같다. 사다리를 놓을 수 있는 경우의 수 0, 1, 2, 3에 대하여, 그 갯수만큼 사다리를 놓을 때의 모든 경우의 수를 순서대로 탐색한다. (44~46번째 줄)만약 answer의 값이 변경되었다면(= sys.maxsize가 아닐 때), 필요한 사다리의 갯수를 찾았다고 간주하고 정답을 출력한다. (47~51번째 줄)사다리를 놓을 수 있는 모든 위치를 탐색하면서, 사다리를 놓을 모든 경우의 수를 DFS로 탐색한다. (32~41번째 줄)DFS를 재귀적으로 실행하면서 정해놓은 갯수만큼 사다리를 놓았다면, 사다리 게임을 시작하고, i번째 사다리에서 시작해서 i번째 사다리에서 모두 끝나는지 검사..

문제 보기이 문제는 브루트 포스 문제이다. 다음과 같은 감시카메라로 감시를 할 때, 주어진 맵에서 최소의 사각지대를 구해야한다.감시카메라의 종류는 다음과 같다.각 종류의 감시카메라가 90도마다 회전할 때의 최소 사각지대를 구해야한다.다음 그림을 보면 이해할 수 있다.위 그림을 설명하자면, CCTV 리스트에 있는 모든 카메라들에 대해서 4번씩 회전시키고, solution()함수를 재귀적으로 실행시킨다. 이때의 매개변수는 현재 CCTV 리스트와 그 index이다. 1. 리스트 내의 index가 0인 1번 CCTV의 모든 회전에 대해서 재귀적으로 탐색을 한다. (그림에서는 1번 CCTV를 4번 회전시킨다.)2. 1번 CCTV의 각 회전에 대해서 리스트 내의 index가 1인 2번 CCTV의 모든 회전에 대해서..

문제 보기이 문제는 브루트 포스 문제이다.두 팀의 능력치의 경우의 수를 모두 따져서 그 차이가 최소가 되는 것을 찾아야 한다.먼저 각 팀을 정확히 절반으로 나누는 과정은 DFS로 구현하였다. 문제를 해결하는 단계는 다음과 같다.1. n 명의 선수들을 2개 팀으로 나누어서 배치한다. (DFS 적용)2. 각 팀에서 선수 2 명을 선택하여, 팀에 더해지는 능력치를 구하고, 팀의 총 능력치에 더한다. (조합)3. 두 팀의 능력치 차이의 최소값을 구한다. 다른 사람들의 풀이를 보아하니, itertools의 combination 함수를 사용한 것을 보았다.다음에는 나도 itertools를 사용해서 문제를 풀어봐야겠다. 123456789101112131415161718192021222324252627282930313..

문제 보기이 문제는 브루트 포스 문제이다.N개의 수로 이루어진 수열에서, 각 숫자 사이에 사칙연산자 +, -, *, / 를 집어넣어서 최대, 최소값을 구하는 문제이다.Iterative한 방법은 실력이 부족해서 구현하지 못했다.. 이 문제를 풀면서 깨달은 점은, 파이썬에서 음수의 나눗셈을 할 때 신경을 써야한다는 것이다.123print(-3 / 4)print(int(-3 / 4))print(-3 // 4)cs이 값들의 결과값은 다음과 같다.문제를 풀면서 파이썬에서 나누기연산은 부호에 관계없이 모두 floor division을 한다는 것을 알았다. 따라서 문제에서 요구하는 올바른 몫을 구하기 위해서는 결과값에서 int형으로 캐스팅해서 몫을 구해야한다. 1234567891011121314151617181920..

문제 보기이 문제는 브루트 포스 문제이다. (DFS로도 풀 수 있다.)위의 도형들을 회전, 대칭하여 만들 수 있는 총 블록들을 리스트에 저장하여, 종이의 각 칸에 방문할때마다 최대값을 찾는다. 다른 풀이를 보아하니, 보라색 테트로미노를 제외하고는 모두 DFS로 탐색 가능한 도형이다.보라색을 제외한 모든 테트로미노들을 DFS로 탐색할 시, 모두 Depth가 3이다.종이 위의 모든 칸을 순회하면서, DFS로 Depth가 3인 테트로미노와 보라색 테트로미노의 경우의 수 4가지를 비교해서 최대값을 구하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041import sys n, m = map(int, sys.stdin.rea..

문제 보기이 문제도 BFS와 브루트 포스를 합친 문제이다.처음에 문제를 읽었을 때, 완전탐색을 해야하지만 무엇을 완전탐색 해야할 지 감이 잡히지 않았다.계속 고민을 하다보니, 상, 하, 좌, 우로 블록들을 이동시켰을 때의 판의 상태를 완전탐색해야겠다고 생각했다. BFS 부분은 그래프 내에서 최대값을 구하는 알고리즘과 동일하다. 구현 상의 어려운 부분은 moveBoard 메소드인데, 블록들을 이동시켰을 때의 상태를 새로운 판 객체로 반환해서, 이를 큐에 추가하는 것이다. 문제는 최대 5번 이동시켜서 얻을 수 있는 최댓값을 구하는 것이기 때문에, 5번이 넘어가면 BFS를 중단하고 결과값을 반환한다. 판 객체를 큐에 추가한다는 개념은 아래의 그림을 보면 이해하기 쉽다. 위 그림은 블록들을 1번 이동시켰을 때의..