[백준] 20058번 마법사 상어와 파이어스톰 자바 정답 풀이
https://www.acmicpc.net/problem/200581. 풀이배열을 시계 방향으로 90도 회전하는 메서드를 구현하자매번 2^L 크기의 부분 격자로 나눠 회전시켜야 하므로, 별도로 메서드를 만들어 놓으면 편리하게 사용할 수 있다.private static int[][] rotate(int L) { // L = 2 ^ l; int[][] rotated = new int[n][n]; for (int i = 0; i 얼음이 있는 칸이 3개 미만인 위치를 모두 파악한 후에, 한꺼번에 얼음의 양을 줄여야 한다.이중 for문으로 격자의 각 위치를 방문하면서 곧 바로 얼음의 양을 줄이면 안 된다. 처음에 이 방식으로 하느라 꽤 오래 헤맸다...아무튼.현재 격자 board의 모습을 깊은..
[백준] 20057번 마법사 상어와 토네이도 파이썬 & 자바 정답 풀이
https://www.acmicpc.net/problem/20057 1. 풀이격자 밖으로 나간 모래의 양은 (일정한 비율로 흩날린 모래 + 격자 밖에 위치한 α로 이동한 모래)이다이걸 확인하겠다고 얼마나 많은 시간을 보냈는지...코드를 작성하기 전에 그림을 그리면서 확인했는데, 앞으론 코드를 작성한 후에 테스트 케이스와 답이 다르면 수정하는 방식을 택해야겠다. 방향에 따라 모래가 흩날리는 위치와 비율을 미리 파악해두자SPREAD 라는 리스트에 y를 기준으로 상하좌우로 움직일 때의 각 비율과 위치를 저장하면 다음과 같다.SPREAD = [ [(-1, 0, 7), (1, 0, 7), (-2, 0, 2), (2, 0, 2), (-1, -1, 10), (1, -1, 10), (-1, 1, 1), (1, ..
[백준] 20055번 컨베이어 벨트 위의 로봇 파이썬 & 자바 정답 풀이
https://www.acmicpc.net/problem/200551. 풀이N 위치에 도달하면 무조건 로봇을 내리는 것에 유의하자!벨트를 회전한 후에 N 위치에 로봇이 있다면 내리고, 로봇이 이동한 후에도 N 위치로 이동한 로봇이 있다면 내려야 한다.두 차례 모두 꼼꼼하게 로봇이 N 위치에 있는지를 확인해야 한다. 벨트의 내구성을 나타내는 배열(길이 2n)과 해당 칸에 로봇이 있는지 나타내는 배열(길이 n)을 사용하자벨트는 위아래로 존재하므로 배열의 길이가 2n이고, 로봇은 위쪽 벨트에만 존재하므로 길이는 n이면 된다. 2. 파이썬 정답 코드import sysinput = sys.stdin.readlinen, k = map(int, input().split())hp = list(map(int, in..
[백준] 1697번 숨바꼭질 파이썬 정답 풀이
https://www.acmicpc.net/problem/16971. 풀이BFS 알고리즘을 사용하자문제에서 말하는 최소 시간은 결국 수빈이가 동생까지 가는 데 이동하는 최단 거리로 치환할 수 있다. 또한 앞으로 1칸 이동, 뒤로 1칸 이동, 순간 이동은 모두 이동하는 데 1초가 걸린다. 즉, 모든 이동 방식의 가중치가 모두 1이다. 따라서 이 문제는 가중치가 1로 동일한 그래프에서 최단 경로를 찾는 것이므로 BFS 알고리즘이 적합하다. 참고로 BFS는 노드를 한 번만 방문하면 되며, 처음으로 노드를 방문한 시점이 가장 빠른 시간임을 보장한다. 번외로 dp를 통해 문제를 해결할 수는 있지만, dp는 일반적으로 이동에 따른 가중치가 서로 다른 경우에 활용한다. 2. 정답 코드from collections..
[프로그래머스] 리코쳇 로봇 파이썬 정답 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/169199 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 풀이최소 거리를 찾는 bfs의 변형우선 노드과 노드 간의 최소 거리를 찾는 알고리즘인 bfs를 사용해야 한다.그러나 일반 bfs는 현재 좌표 (x, y)에서 상하좌우 한 칸씩만 이동하지만, 이 문제에선 장애물이나 게임판 가장자리를 만날 때까지 쭉 이어서 값을 더해줘야 한다. 예를 들어 (x, y)에서 아래로 이동할 때는 (x - 1, y)에서 멈추는지 확인하고 아니라면 (x - 2, y)에서 다시 확인하고 (x - 3, y), (x - ..
[프로그래머스] [1차] 프렌즈4블록 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 풀이완전탐색이다board 전체를 완전탐색해서 사라질 블록들을 찾아 제거하고, 다시 또 완전탐색해서 사라질 블록들을 찾아 제거하는 것을 반복한다. board는 한 번 탐색하고 블록을 제거하고나면 상태가 달라지기 때문에 다시 완전탐색을 해서 새로 사라질 블록을 찾아 제거해야 한다.while True: # board 탐색을 반복할 while문 # board를 탐색하기 위한 이중 for문 for i in range(m - 1): for ..
[백준] 15961번 회전 초밥 파이썬 풀이
https://www.acmicpc.net/problem/159611. 풀이입력이 매우 크므로 일반 input() 대신 빠른 sys.stdin.readline()을 사용하자.N의 크기가 무려 3,000,000이다. 알고리즘이 정답이더라도, 입력 받는 데서 시간이 지체되면 결국 실행 시간이 오래 걸리게 된다. 실제로 오랜만에 백준을 풀어서 습관처럼 input()을 사용했다가 시간 초과가 났었다. 어떤 초밥을 몇 개 먹었는지 저장하는 리스트(dishes)를 사용하자.리스트의 인덱스가 초밥의 종류를 나타내고, 해당 인덱스의 값이 고객이 그 초밥을 의미한다.고객이 먹을 수 있는 초밥 가짓수의 최대값은, 고객이 연속해서 먹은 k개의 접시에 쿠폰 번호 c가 포함되어 있지 않은 경우이다. 이를 다르게 생각하면 고객..
[백준] 1149번 RGB거리 파이썬 풀이
https://www.acmicpc.net/problem/14891 1. 풀이(n - 1)번째 결과를 바탕으로 가장 최소 비용을 만드는 n번째 선택을 하자.이전 결과를 담을 2차원 리스트가 필요하다. 행은 몇 번째 집인지를 의미하고, 열은 R(0), G(1), B(2) 중 어떤 색을 선택했는지에 대한 정보를 나타낸다. 위 그림은 백준의 첫 번째 입력 예제를 바탕으로 만들어진 2차원 리스트이다.예를 들어 1번 집을 초록색과 파란색 중 더 비용이 작은 색을 칠하고, 2번 집에 빨강(R)을 칠한다면 그 비용은 dp[1][0]에 담긴다. 이를 식으로 나타내면 dp[1][0] = min(dp[0][1], dp[0][2]) + COSTS[1][0]이다.그런데 사실 2번 집에 빨간색이 아니라, 초록색 혹은 파란..
[프로그래머스] 유연근무제 파이썬 풀이
https://school.programmers.co.kr/learn/courses/30/lessons/388351 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 1. 풀이모듈러 연산(%)으로 미리 주말 인덱스를 계산해두자.월요일이 1부터 시작하므로 토요일과 일요일은 6, 7이다. 따라서 각 케이스에서의 토요일과 일요일을 나타내는 인덱스는 (6 - startday), (7 - startday)이다. 그럼 이렇게가 끝인가? 아니다!만약 startday가 일요일이라면? 일요일 인덱스는 0이지만, 토요일 인덱스는 -1이 돼 버린다. 따라서 토요일, 일요일 인덱스를 구할 때는 (6 - startday) % 7..
[백준] 14891번 톱니바퀴 파이썬 풀이
https://www.acmicpc.net/problem/14891 1. 풀이회전하는 톱니바퀴의 왼쪽과 오른쪽을 나눠 각 톱니바퀴의 회전 여부를 파악하자 만약 2번째 바퀴를 회전시킨다면, 그것의 왼쪽에 있는 바퀴들과 오른쪽에 있는 바퀴들을 따로따로 고민해야 한다. 왼쪽을 먼저 보자. 2번째 바퀴의 왼쪽 부분, 즉 인덱스 6과 1번째 바퀴의 오른쪽 부분, 인덱스 2를 비교해야 한다. 두 자성이 다르기 때문에 1전째 바퀴는 2번째의 반대 방향으로 회전한다. 그리고 이제 1번째 바퀴의 인덱스 6과 0번째 바퀴의 인덱스 2를 비교해야 하는데, 0번째 바퀴가 없으므로 비교를 종료한다. 그럼 이제 오른쪽 방향을 살펴보자. 2번째 바퀴의 인덱스 2와 3번째 바퀴의 인덱스 6을 비교면하면 두 자성이 같음을 알 수 있다..