구름을 채우다

문제 보기이 문제는 시뮬레이션 문제이다.톱니바퀴의 초기상태와 회전 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구해야한다. 나는 이 문제를 보자마자 나는 비트마스크를 써야겠다고 생각했다.톱니의 상태를 2진수로 만들고, 이를 시계방향, 반시계방향으로 회전시키는 함수를 만들었다. (10~25번째 줄)12시 방향의 비트를 MSB로 두었고, MSB 바로 왼쪽의 비트를 LSB로 두었다. 10101111 -> 01011111 각 명령마다 톱니바퀴를 선택하고 돌릴 때, solution 함수를 통해 톱니바퀴를 양쪽으로 탐색한다.비트마스크를 사용해서 문제를 풀 때, 여기서 주의해야할 점이 있다. 1. 오른쪽으로 탐색할 때오른쪽 톱니바퀴를 회전시킬지 결정할 때, 오른쪽 톱니바퀴의 2번째 비트와, 왼쪽 톱니바퀴의 6번째 비..

문제 보기이 문제는 시뮬레이션 문제이다.문제를 풀다보니 코드가 점점 더러워지는 느낌이다.. 문제에서 주어지는 조건은 다음과 같다.이 조건들을 잘 따지면 정답을 구할 수 있다. (말은 쉽지만 이 문제 푸는데 아주 오래 걸렸다...) 이 문제를 푸는데 사용한 로직은 다음과 같다.1. 같은 높이의 블럭이 나오면 갯수를 센다. (13~14번째 줄)2. 다음 블럭의 높이가 2 이상 차이나면 조건을 위반하므로 flag를 False로 바꾼다. (29~31번째 줄)3-1. 다음 블럭이 높을때, count와 경사로의 길이를 비교한다. count가 더 작으면 경사로를 놓을 수 없다는 의미이고, count가 경사로의 길이보다 같거나 더 크면 경사로를 놓을 수 있다는 의미이다. 그러므로 경사로를 놓고 count를 1로 초기화..

문제 보기이 문제는 브루트 포스 문제이다.두 팀의 능력치의 경우의 수를 모두 따져서 그 차이가 최소가 되는 것을 찾아야 한다.먼저 각 팀을 정확히 절반으로 나누는 과정은 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..

문제 보기이 문제는 동적계획법(Dynamic Programming) 문제이다.아주 쉬운 문제이지만, DP에 익숙하지 않아서 고민을 많이 했다.풀이는 다음과 같다. 1. 내일 벌 돈이 오늘 번 돈보다 적다면 이를 갱신한다.2. 오늘 일을 하면 오늘로부터 time[i]번째 날에 돈을 받는다.3. 오늘 일을 해서 time[i]번째날 후에 받을 수 있는 돈이 현재 time[i]번째 날에 받을 수 있는 돈의 최대값보다 크다면 이를 갱신한다. 123456789101112131415161718import sys n = int(sys.stdin.readline())time = [0 for _ in range(n)]price = [0 for _ in range(n)]dp = [0 for _ in range(n + 1)]..

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

문제 보기이 문제는 단순구현 문제이다.단지 주사위를 굴렸을 때 어떻게 주사위의 각 면들을 구할 것인지, 지도와 주사위의 밑바닥 값을 어떻게 복사할 지 주의하면 된다. 첫번째로, 주사위를 상하좌우로 굴려서 면이 바뀌었을 때, 이를 업데이트 하는 방법은 다음과 같다.주사위의 전개도에서 각 위치들을 절대적인 위치로 생각하고, 주사위를 굴렸을 때 바뀐 면들을 업데이트 한다.이를 구현하면 아래와 같다. (전개도는 절대적인 명시되있는 것처럼 절대적인 위치라고 생각한다.) 두번째로, 주사위를 굴릴 다음 위치가 지도에 없으면, 해당 움직임은 무시 해야한다.만약 주사위를 성공적으로 굴렸다면, 문제에서 지시하는대로 값을 복사하면 된다. 123456789101112131415161718192021222324252627282..

문제 보기이 문제는 단순구현 문제이다.문제가 매우 쉽다고 생각하고, 각 방마다 필요한 감독관의 수를 구해서 총 합을 구했는데 WA를 받았다.질문게시판을 찾아보니, 한 방안에 있는 시험자의 수가 총 감독관이 감독할 수 있는 수보다 적으면 음수가 되는데, 이를 처리하지 않아서 WA를 받았던 것이다.이를 처리해주니 AC를 받았다. 123456789101112131415161718import sys n = int(sys.stdin.readline())tester = list(map(int, sys.stdin.readline().split()))b, c = map(int, sys.stdin.readline().split()) answer = 0for i in range(n): tester[i] -= b if te..

문제 보기이 문제는 시뮬레이션 문제이다.이 문제를 풀어보니 시뮬레이션에 많이 취약한 것 같다.시뮬레이션 문제는 적혀있는 그대로 구현하는 것이 어려운 게 아니라, 요구사항을 정확히 이해하고 구현하는게 제일 중요한 것 같다. 다음과 같이 문제의 요구사항이 있다.문제에서 요구하는대로 구현하는 것이 어렵지만, 문제의 구현에 집중하다보니 간과한 부분이 있다.입력의 조건에 보면, 다음과 같이 명시되어 있다.사과의 위치는 모두 다르며, 맨 위 맨 좌측 (1행 1열)에는 사과가 없다.즉, 뱀이 시작하는 위치는 (1, 1)로 생각하고 문제를 풀어야 한다는 것이다.이에 주의해서 구현하면 AC를 받을 수 있다. (내 코드로는 메모리와 시간이 꽤나 걸린다.. 추후에 더 개선 해야겠다.) 123456789101112131415..

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