구름을 채우다

문제 보기 이 문제는 브루트 포스 문제이다. 문제에서 의도하는 바는 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: 체스말 리스트 (각 체스 말의 행, 열과 방향을 담고 있다.) 이를 가지고 문제를 해결하였다. 문제를 푼 로직은 다음과 같다. 체스 말이 다..

문제 보기 이 문제는 힙 문제이다. 힙 자료구조를 사용해서 우선순위 큐를 구현하는 것이 문제의 의도이다. 문제를 푼 로직은 다음과 같다. 주어진 스코빌 리스트를 힙으로 변경한다. (7~8번째 줄) 문제에서 주어진 방식대로 음식 2개를 섞어 새로운 음식을 만들고, 이 때의 스코빌 지수를 추가한다. (11~15번째 줄) 모든 음식의 스코빌 지수가 K보다 높아야하므로, 힙의 루트가 K보다 작을 동안(= 힙의 최소값이 K보다 커지면 모든 음식의 스코빌 지수가 K보다 크다) 반복한다. (9~10번째 줄) 더이상 섞을 음식이 없고, 스코빌 지수가 K보다 낮다면 -1을 반환한다. (17~18번째 줄) import heapq def solution(scoville, K): answer = 0 # make scovill..

문제 보기 이 문제는 스택/큐 문제이다. 주식이 시간이 지남에 따라 가격이 떨어지지 않은 시간이 얼마인지 구하는 문제이다. 현재 시간에서 미래에 가격이 떨어지는 시간까지 탐색을 해야하기 때문에 O(n^2)이 나올거라고 생각했다. 문제를 푼 로직은 다음과 같다. 각 시간에서의 주식 가격에 대해서 (5~6번째 줄) 주식 가격이 떨어지지 않는 시간을 구한다. (8~15번째 줄) 각 시점에서의 주식 가격이 떨어지지 않는 시간을 업데이트한다. (17번째 줄) 여기서 눈여겨 볼 점은, 11~15번째 줄이다. 먼저 시간부터 센 다음, 만약 주식 가격이 떨어지면 break를 통해 반복문을 벗어난다. 이는 예제 입력을 보면 알 수 있다. 주식 가격이 상승을 하던 하락을 하던 일단 1초는 지나가기 때문에 시간을 먼저 세는..