구름을 채우다

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

문제 보기 이 문제는 수학 문제이고, 에라토스테네스의 체가 필요하다. 문제가 요구하는 것은 말 그대로 골드바흐의 추측을 검증하는 것이다. 골드바흐의 추측이란 다음과 같다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 주어진 범위 내에 이 추측을 검증하기만 하면 된다. 문제를 푼 로직은 다음과 같다. 에라토스테네스의 체로 주어진 범위 내의 모든 소수를 구한다. (5~18번째 줄) 숫자 n을 입력받고 합이 n을 이루는 소수 a, b를 구한다. 두 소수 a, b를 찾았다면 "n = a + b"를 출력한다. (26~33번째 줄) 두 소수 a, b를 찾지 못했다면 "Goldbach's conjecture is wrong."을 출력한다. (35~36번째 줄) 이 문제가 생각보다 까다로운 점은 시..

문제 보기 이 문제는 수학 문제이다. 알고리즘 분류는 에라토스테네스의 체도 포함되어 있지만, 굳이 그럴 필요는 없는 것 같다. 문제에서 요구하는 바는 주어진 숫자들 중 소수가 몇 개인지 찾는 것이다. 딱히 어려운 구현은 없기 때문에, 나는 소수를 판별하기 위해 다음의 조건을 생각하였다. 소수의 약수는 1과 n밖에 없다. 이 조건을 확인하는 함수는 8~16번째 줄에 작성되어 있다. 문제를 푼 로직은 다음과 같다. 자연수를 입력받는다. (4~5번째 줄) 주어진 수에 대해서 소수의 개수를 세고, 이를 출력한다. (19~23번째 줄) import sys from math import sqrt n = int(sys.stdin.readline()) numbers = list(map(int, sys.stdin.rea..

문제 보기 이 문제는 수학 문제이다. 최대 공약수를 활용한 문제인데, 최대 공약수를 구하는 부분은 math 모듈의 gcd 메소드를 사용하였다. 문제를 푼 로직은 다음과 같다. 숫자의 개수와 숫자들을 입력받는다. (6~7번째 줄) 주어진 숫자의 모든 경우의 수에 대해서 최대 공약수를 구하고, 이 최대공약수들의 합을 구해야 하기 때문에 answer 변수에 더해준다. (9~13번째 줄) 주어진 테스트 케이스만큼 실행한다. (4~5번째 줄) import sys from math import gcd t = int(sys.stdin.readline()) for _ in range(t): line = list(map(int, sys.stdin.readline().split())) n, numbers = line[0]..

문제 보기 이 문제는 시뮬레이션 문제이다. (시뮬레이션 구현을 위해 노가다가 필요하다..) 문제에서 요구하는 바는 주어진 순서대로 큐브를 회전시켰을 때의 상태를 구하는 것이다. 문제를 푸는 로직 자체는 매우 쉽지만, 이를 구현하기 위한 방법이 매우 까다롭다. 먼저, 나는 문제를 풀기 위해 다음과 같이 큐브의 전개도를 구성하였다. 이 전개도는 가상의 위치로써, 큐브가 회전하더라도 어떻게 큐브가 회전하였는지 우리가 알기 쉽게 도와준다. 이 전개도를 구현하기 위해 나는 cube라는 3차원 리스트 변수를 두었고, 다음과 같이 구성하였다. 즉, cube는 3*3 2차원 배열을 6개 가진 변수이다. 큐브의 각 칸에 대한 숫자들은 나중에 큐브가 회전할 때 우리가 쉽게 이해하기 위해 임의로 둔 숫자이다. 이제 우리는 ..

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

문제 보기 이 문제는 BFS와 시뮬레이션 문제이다. 갈수록 삼성 SW 역량 테스트의 문제가 점점 더 구현에 까다로운 조건을 추가하기 시작하는 게 느껴진다. 먼저, 문제를 풀기 위해 원판의 숫자를 어떻게 표현할 것인지에 대해서 생각해보아야 한다. 문제에서 주어진 원판을 행렬로 표현하면 다음과 같다. 이제 원판을 행렬로 나타냈으니, 원판을 회전시키는 함수를 작성한다. i번째의 원판을 회전시킬 때, i의 배수인 원판 모두 회전을 시켜야 한다. 이 부분에 대한 구현은 13~27번째 줄에 다음과 같이 구현되어 있다. def rotate(_x, _d, _k): # rotate counter-clockwise if _d: # for all disks which is multiple of x for i in range..

문제 보기 이 문제는 알고리즘 분류는 되어있지 않지만, 시뮬레이션 문제라고 생각한다. 갈수록 삼성의 SW 역량 테스트가 점점 어려워지는 게 느껴진다. 개인적으로 문제를 읽자마자 스택/큐의 개념이 떠올랐지만, 막상 파이썬으로 구현하니 스택/큐를 쓸 일이 없었다. 또한 C/C++의 포인터를 쓰고 싶었지만, 파이썬에는 포인터의 개념이 없기 때문에 해결법을 구상하는데 꽤나 오랜 시간이 걸렸다. 문제를 풀기 전, 중요한 변수가 3개 있다. board_info: 체스판의 색깔 정보를 담고있는 변수 board: 체스판 위의 체스말 정보를 담고 있는 변수 chess_pieces: 체스말 리스트 (각 체스 말의 행, 열과 방향을 담고 있다.) 이를 가지고 문제를 해결하였다. 문제를 푼 로직은 다음과 같다. 체스 말이 다..

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

문제 보기 이 문제는 DFS, BFS 문제이다. (DFS로는 안 풀어도 된다.) 연구소 내의 모든 바이러스 중에서 m개의 바이러스를 선택하는 과정을 DFS로 풀면 DFS 문제가 되겠지만, 나는 itertools 모듈의 combinations 함수를 사용하였다. 문제를 푼 로직은 다음과 같다. 입력으로부터 연구소 내의 빈 방의 개수와 바이러스의 위치를 저장한다. (9~17번째 줄) 모든 바이러스 중에서 m개의 바이러스를 선택하는 모든 경우의 수를 구한다. (20~21번째 줄) 2번에서 구한 m개의 바이러스를 큐에 삽입한다. (22~26번째 줄) 3번에서 큐에 삽입한 m개의 바이러스를 BFS를 통해 확산시킨다. (확산될 수 있는 경우의 수는 빈 방일 경우와 비활성 바이러스일 경우 확산될 수 있다. 빈 방의 ..