개발 일지

문제 14889번: 스타트와 링크 (acmicpc.net) 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 1 itertools 모듈을 쓰지 않고 푸는데 의의가 있는 문제이다. 모든 선수들은 두 그룹으로 나뉘는데, 첫번째 선수를 포함한 그룹과 그렇지않은 그룹이다. 선수를 n/2 만큼 모으면, get_point 메서드를 통해 점수를 계산하고 두 팀의 점수차를 구한다. import sys input = sys.stdin.readline n = int(input()) s = [] for _ in range(n): s.append(l..

문제 14503번: 로봇 청소기 (acmicpc.net) 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 1 재귀함수를 이용한 기본적인 구현문제이다. DFS도, BFS도 아니고 구현 항목을 따라 작성하면 된다. 재밌는 문제라 따로 기록해둔다. import sys input = sys.stdin.readline n,m = map(int,input().split()) r,c,d = map(int,input().split()) board = [] for _ in range(n): board.append(lis..

문제 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 1 언뜻 보면 흔한 DFS 문제같지만... 사실 아니다! 테트로미노 중 오른쪽 하단에 보이는 모양은 흔히 쓰는 '한 칸 씩 전진하는 DFS'로 만들수 없기 때문이다. 따라서 총 세가지 방법 정도를 생각할 수 있고, 두 가지 방법을 이용해 풀이했다. DFS DFS로 만들 수 없는 모양을 제외한 모든 모양을 DFS로 만들어 탐색하고, 문제의 'ㅏ' 모양에 대해서만 90도 씩 회전하며 탐색한다. 2700ms의..

문제 14499번: 주사위 굴리기 (acmicpc.net) 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 1 주사위만 구현할 수 있으면 되는 문제이다. 주어진 전개도가 힌트가 되는데, 전개도에서 가로줄, 세로줄을 각각 deque로 놓고 rotate한다고 생각하면 주사위 굴리기가 쉽게 구현된다. 다른것보다 전개도를 이용해 주사위를 구현하는것이 가장 핵심이 됐던 문제라고 생각한다. from collections import deque n,m,..

문제 12100번: 2048 (Easy) (acmicpc.net) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 1 슬라이드를 최대 5번 해서 얻을 수 있는 가장 큰 블록을 출력해야 하는 문제이다. 가장 큰 값 찾기 가장 먼저 알아차려야 하는 것은, 슬라이드를 한 후의 가장 크기가 큰 블록은 이전 상태의 가장 크기가 큰 블록보다 같거나 크다는 것이다. 따라서 슬라이드를 5번까지 한 4^5 = 1024개의 보드들의 숫자들을 전부 탐색하며 최대값을 찾아내면 되고, 그 연산량은 1..

문제 13460번: 구슬 탈출 2 (acmicpc.net) 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 풀이 1 다음 문제와 상당히 유사하다는 것을 알 수 있다. 블록 이동하기 (lv3) (tistory.com) 블록 이동하기 (lv3) 문제 설명 로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x forteqook.t..

문제 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 풀이 1 뱀의 머리가 벽 또는 자신의 몸에 닿으면 프로그램이 종료되어야 하므로, deque에 뱀이 차지하고 있는 좌표들을 넣는것이 핵심이다. 또한 보드의 크기가 최대 100까지로 제한되어 있는 것에 착안하여 뱀을 1초 씩 이동시키며 주어진 조건을 확인 하는 완전탐색의 방법이 유효하다는 것을 알 수 있다. 처음에 입력된 방향 변환 정보를 모두 사용하고, 이후로는 방향 전환이 없으므로 바라보고 있는 방향으로 직진하여 벽 또는 ..

문제 14501번: 퇴사 (acmicpc.net) 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 1 테이블과 같이 소요시간과 보상이 주어졌을 때, 각 업무를 조합하여 경우들 중 최대값을 찾아내야 하는 문제이다. 가장 먼저, 조합의 경우를 찾는 방법을 바로 알아채기가 힘드니 주어진 예시를 가시화하여 상황을 정리해본다. 아래는 예시를 가시화하여 나타낸 그림이다. 위와 같은 업무 테이블을 이용해 7일차 까지 조합의 경우의 수 중 가장 큰 값을 찾아내야한다. 1일차 업무를 하고 받는 보상과 4일차 이후 부터의 조합 중 보상의 최대값을 더한 경우, 1일차 업무를 포기하고 2일차 혹은 3일차 업무를 하는 경우로 나뉜다. 이와 같은식으로 f(i)를 i일..

문제 16234번: 인구 이동 (acmicpc.net) 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 1 이전에 예제로 풀었던 "음료수 얼려먹기" 문제와 유사하다. 어떤 노드에 대해 인접 노드가 특정 조건을 만족하면 방문하는 DFS나 BFS를 이용해 풀면 된다. 소위 "음료수 채우기" 가 완료되면, 방문한 모든 노드의 값을 평균을 내어 다시 할당해야 하는 작업도 추가적으로 해줘야한다. 이 작업은 연합 형성이 불가능할 때까지 반복한다. 대강의 설계가 끝났으니 구현에 들어갈 차례이다. 한 사이..

문제 14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 1 연산자는 순열로 나타낼 수 있지만, 연습을 위해 풀이는 DFS로 해보기로 했다. 순열 대신 DFS로 푼다는것, 즉 제한된 횟수만큼 경우의 가짓수를 찾아가는 것은 이미 연구소 문제에서 다뤄봤다. 연구소 문제에서는 벽을 3개 세우는 것을 조건으로 뒀으며, 그 조건을 만족했을 때 재귀를 탈출해서 바이러스 감염을 연산했었다. 이번에는 정확히 같은 ..