lifeofkwon의 등록된 링크

키자드에 등록된 총 253개의 포스트를 확인하실 수 있습니다.

Naver Blog

백준 B3678-카탄의 개척자 with 파이썬

문제 3678번: 카탄의 개척자 문제 "카탄의 개척자"는 많은 사람들이 즐기는 보드게임이다. 게임을 시작하려면, 먼저 게임판을 랜덤으로 만들어야 한다. 게임판은 육각형 타일로 이루어져 있으며, 각 타일은 자원을 하나씩 포함하고 있다. 자원은 총 다섯 가지 종류가 있으며, 점토, 재목, 양모, 곡물, 광석이다. 각 자원은 1부터 5까지 순서로 나타낼 수 있다. 랜덤을 이용해서 게임판을 만들면, 같은 자원이 인접한 타일에 있는 경우가 있을 수도 있다. 이런 배치를 매우 싫어하는 사람이 많다. 따라서, 다음과 같은 과정으로 게임판을 만들려고 한다. 먼저, 게임판의 중앙... www.acmicpc.net 풀이 이 문제는 너무 어려웠다. 평소에는 접해보지 않은 육각형의 방향 전환이었고, 이걸 2차원 배열에서 표현하려고 하니 너무 머리가 아팠다. 개인적으로 방법을 고민하다가 구현 방법은 떠올랐는데 디테일을 잡지 못했다. 예를 들어 배열의 크기 잡는게 계산이 되지 않았다. 관련 코드를 찾아보다가

원문보기 내부링크
Naver Blog

백준 B5213-과외맨 with 파이썬

문제 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단 언어가 통하지 않기 때문에, 과외맨은 자신의 특기를 살려서 일주일간 과테말라에... www.acmicpc.net 풀이 몇 번의 틀림 끝에 해결한 문제다. 처음에는 좋은 아이디어를 생각해냇다고 생각했는데 엣지케이스를 캐치하지 못한 것 같다. 어항 정리에서 진행했던 배열 관리 방법을 했다가 포기하고 N*N으로 그대로 진행했다. 대신 없는 곳은 (-1,-1) 처리를 했다. 이후 흔히 알고 있는 BFS를 진행햇다.

원문보기 내부링크
Naver Blog

SWEA 원자소멸시뮬레이션 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 처음에 풀 때 진짜 요령 없이 하나하나 구현하다가 꼬인 문제다. 이후 0.5초라는 개념에 얽매이지 않고 1초로 보는 대신 좌표들을 *2해서 진행하기 쉽게 바꿨다. 또한 -1000, 1000보다는 좀 더 대소 비교 및 관리가 쉬운 0,2000으로 변경함으로써 쉽게 구현할 수 있었다. 코드 import sys sys.stdin = open('input.txt','r') T = int(input()) for tc in range(1, T+1): N = int(input()) dirlst = [(0,1), (0,-1), (-1,0), (1,0)] atomlst = [] for _ in range(N): x, y, d, K = map(int, input().split()) atomlst.append(((x+1000)*2, (y+1

원문보기 내부링크
Naver Blog

삼성 코테 준비 with 추가 알고리즘

다익스트라(dijkstra) import heapq def dijkstra(start): distance = [float('INF')]*(N+1) distance[start] = 0 q = [] heapq.heappush((q, (distance[start], start))) while q: now_dist, now_node = heapq.heappop(q) if distance[now_node]<now_dist: continue for new_node, new_dist in graph[now_node].items(): dist = new_dist + now_dist if dist<distance[new_node]: distance[new_node] = dist heapq.heappush(q, (dist, new_node)) return distance ### N, M은 노드 수, 간선 수 T = int(input()) for tc in range(1, T+1): N, M = map

원문보기 내부링크
Naver Blog

백준 B2933-미네랄 with 파이썬

문제 2933번: 미네랄 문제 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 서있고, 상근은 오른쪽에 서있다. 두 사람은 턴을 번갈아가며 막대기를 던진다.... www.acmicpc.net 풀이 이 문제는 읽고나서 진짜 풀기 귀찮다라는 생각이 들었던 문제다. 기존에 자주 사용하던 중력 관련 함수 사용이 불가능했던 문제다. 처음에는 어떻게 구현해야할까 고민하다가 밑에서부터 올라가면서 클러스터를 찾으면 크게 문제될 부분이 없다는 생각이 들어서 그렇게 진행햇다. 코드 import sys

원문보기 내부링크
Naver Blog

백준 B1888-곰팡이 with 파이썬

문제 1888번: 곰팡이 문제 벽에 곰팡이가 자라고 있다. 곰팡이들은 현재 여러 개의 덩어리를 이루고 있는 상태인데, 이들이 점점 자라나서 한 덩어리로 될 때까지 얼마의 시간이 걸릴지 알고 싶다. 이를 계산하는 프로그램을 작성해 보자. 곰팡이가 피어 있는 벽은 m행 n열의 격자로 나뉘어 있고, 한 칸 당 한 개의 곰팡이가 있다. 곰팡이의 덩어리라는 것은, 격자 상에 가로세로로 인접한 곰팡이들의 집합을 말한다. 맨 처음 상태에서는 한 덩어리 안의 곰팡이들이 모두 같은 종으로, 자라는 속도도 같다. 그러나 서로 다른 덩어리에 속한 곰팡이는 종이 달라 자라는 속... www.acmicpc.net 풀이 이 문제는 여러 q를 어떻게 관리할지를 중요하게 보는 문제인 것 같다. 처음에는 곰팡이의 번식 방법을 이해하는데 어려움이 있었고, 이미 다른 곰팡이가 번식해도 또 해당 위치도 번식할 수 있다는 점에서 놓쳤다. 그 부분을 캐치한다면 큰 어려움은 없을 것 같다. 코드 import sys from

원문보기 내부링크
Naver Blog

SWEA 무선 충전 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 무심코 풀이하면 테케 4번이 잘 나오지 않는다.... 처음부터 성능으로 기준으로 확인했는데 충전기 번호는 다르지만 성능이 같은 경우가 발생해,,, 문제가 되었다. 그 부분만 잘 해결하고 나니 큰 어려움은 없었다. 코드 import sys sys.stdin = open('input.txt', 'r') ### 현재 해당 사람이 있는 위치를 기준으로 충전 가능한 무선 충전기 찾는 함수 def checkbattery(i,j): possible = [] for bnum in range(1, A+1): bx, by, bc, bp = batterydict[bnum] dist = abs(bx-i) + abs(by-j) if dist<=bc: possible.append((bnum, batterydict[bnum][3])) return possib

원문보기 내부링크
Naver Blog

코드트리 - 테트리스 블럭 안의 합 최대화 하기(삼성코테기출) with 파이썬

문제 테트리스 블럭 안의 합 최대화 하기 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제는 삼성 2017 상반기 코테 기출 문제다. 백준에서는 테트로미노라는 문제로 있다. 만약 백준에서 안 풀고 이 문제를 코드트리에서 진행했었다면 단순 구현으로 접근했을 것 같다. DFS로 접근하지 못햇을 것이다. 코드 import sys input = sys.stdin.readline ### 입력 받기 N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] visited = [[0] * M for _ in range(N)] maxnum = max([x for y in arr for x in y]) finalscore = 0 def tetrom

원문보기 내부링크
Naver Blog

코드트리 - 외주 수익 최대화하기(삼성코테기출) with 파이썬

문제 외주 수익 최대화하기 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제는 삼성 2017 상반기 오전 기출문제로 백준에서는 퇴사라는 문제가 있다. 백트래킹으로 문제를 해결했다. 코드 import sys input = sys.stdin.readline ### 입력 받기 N = int(input()) lst = [(0,0)] + [list(map(int, input().split())) for _ in range(N)] answer = 0 def cal(n, cnt): global answer answer = max(answer, cnt) if n > N: ### 휴가 이상이면 return cal(n+1, cnt) ### 해당 날짜 외주 안할 경우 if n+lst[n][0] <= N+1: ### 휴가 내에만 완수할 수 있을 경우 ca

원문보기 내부링크
Naver Blog

코드트리 - 자율주행 자동차(삼성코테기출) with 파이썬

문제 자율주행 자동차 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제는 삼성 2017 상반기 오후 1번으로 출제되었던 문제로 구현 문제다. 백준에서는 로봇 청소기라는 문제와 유사하다. 이 문제의 포인트는 기존 차가 가지고 있는 방향으로 가는게 아니라 일단 회전부터 하는게 제일 중요한 포인트라고 할 수 있다. 코드 import sys input = sys.stdin.readline ### 입력 받기 N, M = map(int, input().split()) si, sj, sd = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] dirlst = [(-1,0), (0,1), (1,0), (0,-1)] ### 북 동 남 서 def solv

원문보기 내부링크
Naver Blog

코드트리 - 방화벽 설치하기(삼성코테기출) with 파이썬

문제 방화벽 설치하기 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 해당 문제는 삼성 2017 상반기 오후 2번 문제로 백준에서는 연구소라는 문제와 유사하다. 백트래킹과 BFS를 조합한 문제로 큰 어려움 없이 해결 가능하다. 코드 import sys from collections import deque input = sys.stdin.readline ### 입력 받기 N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] totalcnt = 0 emptylst, firelst = [], [] for i in range(N): for j in range(M): if arr[i][j] == 0: ### 빈칸이면 totalcnt += 1

원문보기 내부링크
Naver Blog

코드트리 - 술래잡기 체스(삼성코테기출) with 파이썬

문제 술래잡기 체스 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 개인적으로 풀이 과정은 처음부터 파악했지만 제일 어려운 문제인 것 같다. 삼성 2020 상반기 오전 2번 문제로 백준에서는 청소년 상어라는 문제로 있다. 백트래킹인데 배열을 그대로 가져가거나 가져가야할 변수들이 많아서 관리하기가 조금 어려웠던 유형인 것 같다. 코드 import sys input = sys.stdin.readline ### 입력 받기 si, sj, sdir = 0, 0, 0 ### 술래 시작 좌표 및 방향 totalscore = 0 horsepos = [() for _ in range(17)] horsedir = [-1 for _ in range(17)] for i in range(4): line = list(map(int, input().split()))

원문보기 내부링크
Naver Blog

백준 B17779-게리맨더링 2 with 파이썬

문제 17779번: 게리맨더링 2 문제 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해... www.acmicpc.net 풀이 이 문제는 삼성 2019 하반기 오전 번 문제로 난이도는 그렇게 어렵지 않다. 진짜 모든 범위 및 방식을 문제에서 제공해주기 때문에 크게 어려움이 없었다. 코드 import sys input = sys.stdin.readline ### 입력 받기 N = int(input()) arr

원문보기 내부링크
Naver Blog

SWEA - 벽돌 깨기 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 해당 문제는 삼성 모의역량 테스트 문제다. 풀이를 진행하면서 엥 이게 왜 맞지라는 생각을 하게 된 문제다. 혹시 몰라서 가지치기를 추가해서 제출햇는데 당연히 맞긴 햇지만 문제 자체의 테스트케이스가 좀 부실할 수도 있겠구나라는 생각을 했다. 코드 ''' 초기 풀이 과정: 처음에 잘못 생각해서 왜 벽돌의 크기가 1인건 깨지지 않는지 한참 고민함 이후 해당 벽돌의 크기-1만큼 주변 벽돌을 깨뜨리는걸 파악하고 진행하 크게 두가지 함수 생각 -> 깨뜨릴 구슬을 주면 구현하는 함수 & 백트래킹 중력 작용 따로 하려고 했는데 그러면 백트래킹 함수가 복잡해질 것 같아서 breakstone에 포함시킴 과정 피드백 : 마지막 테케에서 실수함 이유는 N개가 되기 전에 다 깨뜨려버리는 경우가 발생할 수 있음 그 경우 answer 값이 갱신이 되지 않음!

원문보기 내부링크
Naver Blog

백준 B16920-확장 게임 with 파이썬

문제 16920번: 확장 게임 문제 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위에 있다. 한 칸 위에 성이 두 개 이상인 경우는 없다. 게임은 라운드로 이루어져 있고, 각 라운드마다 플레이어는 자기 턴이 돌아올 때마다 성을 확장해야 한다. 제일 먼저 플레이어 1이 확장을 하고, 그 다음 플레이어 2가 확장을 하고, 이런 식으로 라운드가 진행된다. 각 턴이 돌아왔을 때, 플레이어는 자신이 가지고 있는 성을 비어있는 칸... www.acmicpc.net 풀이 이 문제는 진짜 많이 고민해서 해결한 문제다. 처음에는 쉽게 접근했는데 그러면 시간초과라는 벽을 만나게 된다. 진짜 최대한 최적화를 진행해야하는데 고민이 많았다. 코드 import sys from collections import deque input = sys.stdin.readlin

원문보기 내부링크
Naver Blog

백준 B8972-미친 아두이노 with 파이썬

문제 8972번: 미친 아두이노 문제 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. 하지만, 미친 아두이노의 움직임은 예측할 수 있다. 게임은 R×C크기의 보드 위에서 이루어지며, 아래와 같은 5가지 과정이 반복된다. 먼저, 종수가 아두이노를 8가지 방향(수직,수평,대각선)으로 이동시키거나, 그 위치에 그대로 놔둔다. 종수의 아두이노가 미친 아두이노가 있는 칸으로 이동한 경우에는 게임이 끝나게 되며, 종수는 게임을 지게... www.acmicpc.net 풀이 단순 구현 문제이다. 크게 어려움은 없었지만 풀면서 삼성에서 좋아할만한 문제라는 생각이 들었다. 주의할 점은 미친 아두이노들끼리 만나면 폭발하는 점과 종수 아두이노와의 거리가 제일 가까운 좌표로만 이동한다는 점이다. 코드 import sys input = sys.stdin.readli

원문보기 내부링크
Naver Blog

SWEA 보물상자 비밀번호 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 16진수 변환하는 법을 알고 있다면 손쉽게 풀 수 있는 문제다! 코드 import sys sys.stdin = open('input.txt','r') from collections import deque ### 입력 받기 T = int(input()) for tc in range(1, T+1): N, K = map(int, input().split()) arr = deque(list(input())) # print(arr) R = N//4 numlst = set() for _ in range(R): for i in range(4): # print(list(arr)[i*R:i*R+R]) word = ''.join(list(arr)[i*R:i*R+R]) changenum = int(word, 16) numlst.add(cha

원문보기 내부링크
Naver Blog

SWEA 홈 방범 서비스 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 처음에 시간 제한이 빡세다고 생각해 브루트포스를 생각하지 않았다. 테케 50개를 3초 만에 돌려야한다는 생각에 더 좋은 방법이 있나 고민했지만, 내가 생각한 방법이 맞았다. 일단 K의 최댓값을 구해야한다. 내가 구한 방법은 각 좌표를 중점으로 생각할 때 K는 max(N-i, i+1)과 max(N-j, j+1)을 더한 값이었다. 이제 각 점마다 방법 서비스를 실행하면 되는데 k를 0에서부터가 아닌 최댓값에서 부터 시작했다. 그 경우, 만약 손해 없이 서비스 제공이 가능할 때 바로 break를 할 수 있기 때문이다. 코드 T = int(input()) for tc in range(1, T+1): N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ i

원문보기 내부링크
Naver Blog

SWEA 등산로 조성 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 삼성 모의 역량테스트를 풀다보면 대부분 브루트포스 알고리즘 사용이 많은 것 같다. 이 문제 같은 경우, 출발할 수 있는 모든 점을 구하고, 각 점을 출발지로, 모든 좌표를 K만큼 팔 경우를 다따져서 진행하면 된다. 코드 from collections import deque T = int(input()) def bfs(si, sj, arr): q = deque() q.append((si,sj)) length = 0 while q: length += 1 for _ in range(len(q)): ci, cj = q.popleft() for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]: ni, nj = ci+di, cj+dj if 0<=ni<N and 0<=nj<N and arr[ni][nj] < arr[ci

원문보기 내부링크
Naver Blog

SWEA 요리사 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 백준 삼성 기출 문제집에 있는 스타트와 포스, 코드트리의 조삼모사와 같은 문제다. 그래서 어렵지 않게 바로 풀이 가능햇다. 코드 T = int(input()) for tc in range(1, T+1): N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] def check(lst): result = 0 for i in range(N//2): for j in range(i+1, N//2): a, b = lst[i], lst[j] result += arr[a][b] result += arr[b][a] return result answer = 1e9 def cook(n, alst, blst): global answer if len(alst) ==

원문보기 내부링크
Naver Blog

백준 B14503-로봇 청소기 with 파이썬

문제 14503번: 로봇 청소기 문제 로봇 청소기와 방의 상태가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 방은 N × M $N \times M$ 크기의 직사각형으로 나타낼 수 있으며, 1 × 1 $1 \times 1$ 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북 중 하나이다. 방의 각 칸은 좌표 ( r , c ) $(r, c)$ 로 나타낼 수 있고, 가장 북쪽 줄의 가장 서쪽 칸의 좌표가 ( 0 , 0 ) $(0, 0)$ , ... www.acmicpc.net 풀이 이 문제는 삼성 코테기출 문제로 다시 복기해보면서 문제를 잘못 이해했었다. 주변에 빈칸이 있다면 무조건 방향 전환부터 한다고 생각하면 된다. 뭔가 항상 문제를 읽으면서 내 방식대로 해석하고 이해하는 경향이 있는 것 같다. 구현 난이도는 어렵지 않았다. BFS, DFS가 들어가지도 않았

원문보기 내부링크
Naver Blog

코드트리 - 바이러스검사(삼성코테기출) with 파이썬

문제 바이러스 검사 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 2015년도 하반기 삼성 코테 기출 문제라고 한다. 난이도는 최근에 비하면 너무 쉽다. 코드 import sys input = sys.stdin.readline ### 입력 받기 N = int(input()) customerlst = list(map(int, input().split())) leader, member = map(int, input().split()) answer = 0 for num in customerlst: num -= leader ### 무조건 팀장은 있음 answer += 1 if num > 0: ### 남은 고객이 있다면 if num%member == 0: answer += num//member else: answer += (num//member)

원문보기 내부링크
Naver Blog

코드트리-2개의 사탕(삼성코테기출) with 파이썬

문제 2개의 사탕 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 해당 문제는 삼성코테기출 문제로 백준에 있는 구슬탈출 2와 같은 문제다. 다른 느낌으로 해결해보기 위해서 코드트리로 풀이를 진행했는데 한 번 틀렸다. 구멍에 빠지면 바로 반복문을 멈춰야했는데 그걸 하지 않아서 틀렸다. 확실히 코드트리의 테케가 백준보다 부실해서 좀 더 고민을 많이 하게 만드는 느낌이 있다. 재귀로 문제를 해결했는데 크게 두 포인트가 있다. 시간을 최적화하기 위해 이전에 온 방향은 가지 않는 것(예로 이번에 좌로 기울인거면 이번에는 우로 기울이지는 않는다!) 그리고 같은 자리에 있을 경우에는 넘기지 않는점(최소한의 움직임) 그리고 어느 방향으로 기울일지에 따라 먼저 체크해야할 캔디가 다르다는 점이다. 코드 import sys input = sys.stdin.re

원문보기 내부링크
Naver Blog

백준 B15684-사다리 조작 with 파이썬

문제 15684번: 사다리 조작 문제 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. 위의 그림에는 가... www.acmicpc.net 풀이 이 문제는 2번째 풀이하는 문제인데 다시 풀이했을 때는 틀리지는 않았지만 속도 자체는 이전꺼가 훨씬 빠르다. 이전에 풀이를 진행했을 때는 진짜 많이 틀리고 최적화를 진행해서 나온 코드이기 때문에 그런 것 같다. 이 문제는 사다리 추가 시에 어떻게 관리할지가 제일 키포인트인 것 같다.

원문보기 내부링크
Naver Blog

SWEA 파핑파핑 지뢰찾기 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 지뢰찾기를 생각하면 편한 문제다. 근데 접근 방식이 바로 떠오르지 않았다. 고민 후에 크게 두과정으로 나누기로 생각했다. 먼저 주어진 지뢰 지도를 통해 칸별로 누르면 무슨 숫자가 나오는지를 파악했다. 그 후, 주어진 조건에서는 무조건 0을 먼저 눌러야겟다고 생각했고 0을 누를 경우 몇개의 좌표들의 숫자들이 노출되는지 확인했다. 이후 해당 좌표들이 노출되고 나서도 남아있는 좌표칸들을 더하는 방식으로 문제를 해결했다. 코드 import sys sys.stdin = open('input.txt', 'r') from collections import deque T = int(input()) for tc in range(1, T+1): N = int(input()) arr = [list(input()) for _ in range(N)] vi

원문보기 내부링크
Naver Blog

SWEA 보호 필름 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 여러번 틀리고 수정해서 해결한 문제다. 시간초과와의 싸움이 컸고 해결하고나서는 문제 이해를 잘못했다. 문제에서 약품 투약 횟수가 최소 2라는 의미가 예시를 설명하는 내용이었는데 그게 조건인 줄 알고 풀이했다가 42개에서 계속 틑렸다. 강화필름 테스트 함수는 쉽게 쉽게 풀이하려다가 시간초과가 났다. 확실히 좀 귀찮더라도 구현에 집중하는게 시간을 단축할 수 있는 방법 같다. 코드 import sys sys.stdin = open('input.txt','r') ### 주어진 보호필름 강화 테스트 함수 (주석은 시간초과 함수) # def check(): # for lst in list(map(list, zip(*arr))): # if not ('0' * K in ''.join(lst) or '1' * K in ''.join(ls

원문보기 내부링크
Naver Blog

백준 B20061-모노미노도미노2 with 파이썬

문제 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다. <그림 1> 모노미노도미노 게임 보드 이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다. <그림 2> 모노미노도미노... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출 문제다. 백준에 있는 청소년 상어와 같이 나온걸로 기억하는데 나는 청소년 상어부터 풀었다. 그 이유는 그림을 보자마자 너무 구현하기 귀찮다고 판단했기 때문이다. 그러나 청소년 상어가 더 어려웠다.... 이 문제는 딱히 크게 구현 난이도가 있지 않았고 배

원문보기 내부링크
Naver Blog

백준 B23288-주사위 굴리기2 with 파이썬

문제 23288번: 주사위 굴리기 2 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼쪽 위에 있는 칸의 좌표는 (1, 1)이고, 가장 오른쪽 아래에 있는 칸의 좌표는 (N, M)이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 각 면에는 1보다 크거나 같고, 6보다 작거나 같은 정수가 하나씩 있다. 주사위 한 면의 크기와 지도 한 칸의 크기는 같고, 주사위의 전개도는 아래와 같다. 2 4 1 3 ... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출 문제다. 구현 난이도가 어렵지 않으며 굳이 헷갈리는 포인트는 점수 C를 구하는 부분으로 문제에서 그림으로 설명하지 않았다면 생각 없이 실수를 할 수도 있는 부분이라는 생각이 들었다. 코드 import sys from collections import deq

원문보기 내부링크
Naver Blog

백준 B23289-온풍기 안녕! with 파이썬

문제 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다. 집에 있는 모든 온풍기에서 ... www.acmicpc.net 풀이 이 문제는 고난이도의 구현 문제다. 삼성 코테 기출 문제로 백준에 있는 기출 문제 중에서는 딱 2개 플래티넘 문제중 하나다. 예전에 풀이를 진행했을 때 시간초과가 몇 번 떴다. 그 이유로는 반복문을 돌 때마다 온풍기가 새롭게 바람을 내뿜었는데 아예 온풍기 바람 테이블을 처음에 따로

원문보기 내부링크
Naver Blog

백준 B19237-어른 상어 with 파이썬

문제 19237번: 어른 상어 청소년 상어 는 더욱 자라 어른 상어가 되었다. 상어가 사는 공간에 더 이상 물고기는 오지 않고 다른 상어들만이 남아있다. 상어에는 1 이상 M 이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 어른 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다. N×N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자신의 냄새를 뿌린다. 그 후 1초마다 모든 상어가 동시에 상하좌우로 인접한 칸 중 ... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출로 솔직히 쉽지는 않은 문제였다. 10일 전에 풀이했었는데 그 때 나는 문제에 대해서 제대로 이해하지 못하고 어렵게 접근했다가 6번인가 틀리고 풀이를 진행했다. 이 문제 같은 경우는 상어 위치, 방향을 관리하는 딕셔너리를 따로 만들고 냄새를 관리하는 배열도 따로

원문보기 내부링크
Naver Blog

백준 B19238-스타트 택시 with 파이썬

문제 19238번: 스타트 택시 스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다. 택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다. M명의 승객은 빈칸 중 하나에 서 있으... www.acmicpc.net 풀이 이전에 풀이를 진행햇을 때는 계속 틀리고 겨우 맞춘 문제였다. 내가 생각한 이유로는 누군가의 목적지가 누군가한테는 출발점이 될 수 있다는 점 하나였고, 거리, 연료 관리를 따로 했는데 시간이 좀 걸리더라도 같이 진행하니깐 실수가 발생하지 않은 것 같다. 코드 import sys fro

원문보기 내부링크
Naver Blog

SWEA 핀볼 게임 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 2번의 시간초고 끝에 해결했다. 해결 과정에는 벽을 처음에는 따로 처리 안했는데 배열을 받을 때 테두리에 5라는 블록을 놔둠으로써 벽을 처리했다. 이로 인해서 pinball 함수가 더 간결해졌다.2번째 시간 초과는 내가 테두리를 둘러쌌다는걸 까멱고 그대로 이전처럼 range를 사용했다가 시간초과가 떴다. 물론 해결 후에도 시간 자체가 빠른 코드는 아니다. 처음 통과한 코드 같은 경우는 블랙홀 리스트를 따로 만들어 해당 리스트 안에 있는지를 조회하는 방식이었지만 두번재 코드는 출발 지점을 따로 등록하고 arr[i][j]로 조회하는 방식을 썼다. 진짜 시간차이가 많이 났다. 코드 Fast(2,571 ms) import sys sys.stdin = open('input.txt', 'r') ### 기본 관리 변수 설정 & 함수 생성 dir

원문보기 내부링크
Naver Blog

코드트리-정육면체 굴리기(삼성코테기출) with 파이썬

문제 정육면체 굴리기 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제는 삼성 2016 하반기 코테 문제로 백준의 주사위 굴리기와 비슷한 유형이라고 보면 된다. 솔직히 구현 난이도에 있어서 어려운 부분이 없었다. 코드 import sys input = sys.stdin.readline ### 입력 받기 N, M, si, sj, k = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(N)] orderlist = list(map(lambda x: int(x)-1, input().split())) dirlst = [(0,1), (0,-1), (-1,0), (1,0)] changedice = [[0,5,1,2,4,3], [0,2,3,5,4,1],

원문보기 내부링크
Naver Blog

백준 B21611-마법사 상어와 블리자드 with 파이썬

문제 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼 , 토네이도 , 파이어스톰 , 물복사버그 , 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, (r, c)는 격자의 r행 c열을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이며 마법사 상어는 ((N+1)/2, (N+1)/2)에 있다. 일부 칸과 칸 사이에는 벽이 세워져 있으며, 다음은 N = 3, 5, 7인 경우의 예시이다. 실선은 벽이고, 점선은 벽이 아니다. 칸에 적혀있는 수... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출 문제다. 역시 마법사 상어 시리즈로 이제 마법사 상어는 다 죽이고 싶을 정도다. 어제 전체 구현 유형을 정리하면서 달팽이는 나중에 해야지했다가 바로 호되게 혼난 문제다. 큰 난이도는 없었지만, 그래도 항상 무언가를 뽑거나 삭제할 때, 해당 리스트나 큐

원문보기 내부링크
Naver Blog

백준 B16985-Maaaaaaaaaze with 파이썬

문제 16985번: Maaaaaaaaaze 문제 평화롭게 문제를 경작하며 생활하는 BOJ 마을 사람들은 더 이상 2차원 미로에 흥미를 느끼지 않는다. 2차원 미로는 너무나 쉽게 탈출이 가능하기 때문이다. 미로를 이 세상 그 누구보다 사랑하는 준현이는 이런 상황을 매우 안타깝게 여겨 아주 큰 상금을 걸고 BOJ 마을 사람들의 관심을 확 끌 수 있는 3차원 미로 탈출 대회를 개최하기로 했다. 대회의 규칙은 아래와 같다. 5×5 크기의 판이 5개 주어진다. 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다. 그림에서 하얀 칸은 참가자가 들어갈 수 있는 ... www.acmicpc.net 풀이 문제를 풀면서 진짜 너무하다고 생각한 문제다. BFS, 재귀를 둘다 사용해야하는 문제였고 순서까지도 랜덤이기 때문에 한번 골탕 먹은 문제다. 구현의 난이도는 높지 않았고 최적화를 하지않아도 통과는 가능한 문제였지만 추가적으로 최적화를 진행했다. 최적화한 부분은 문제에서 특정

원문보기 내부링크
Naver Blog

백준 B23291-어항 정리 with 파이썬

문제 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. <그림 1>은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다. <그림 1> 어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다. 먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출 문제다. 백준 등급으로는 플래티넘이다. 그러나 파이썬으로 문제를 풀게 된다면 비교적 쉬운 문제라고 할 수 있다. 같은 등급의 온풍기 안녕의 난이도가 훨씬 높다. 문제를 읽다보면 알겠지만 나는 그림 6이 안되는 케이스라는 걸 제대로 읽지않고 그림 6처럼 모든 경

원문보기 내부링크
Naver Blog

백준 B17822-원판 돌리기 with 파이썬

문제 17822번: 원판 돌리기 문제 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1) (1, j)는 (2, j)와 ... www.acmicpc.net 풀이 이 문제도 삼성코테 기출문제다. 진짜 이 정도로만 나와도 소원이 없을 것 같다. 원판으로 그림을 보여줬지만 문제를 읽어나가면서 평소 배열처럼 풀어도 되겟다는 생각이 들었고 다른 점은 열 차원에서는 이어진다 정도였다. 이후 코딩을 진행하면서 크게 어렵게 느껴진 부분이 없었지만, 어제와

원문보기 내부링크
Naver Blog

SWEA 미생물 격리 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 큰 난이도 없이 해결 가능한 문제였다. 미생물이 이동하면서 군집이 합쳐지는 경우를 같이 처리하려고 했었지만, 그러면 좀 귀찮기도 하고 따로 관리해야할 변수가 생기는 것 같아서 약품 처리까지만 미생물 이동과 함께 처리를 진행하였고 군집을 새로 합치는 건 따로 진행했다. 그래도 시간초과가 발생하지 않았기 때문이다. 코드 import sys sys.stdin = open("input.txt", "r") T = int(input()) for tc in range(1, T+1): ### 입력 받기 N, M, K = map(int, input().split()) viruslst = [list(map(int, input().split())) for _ in range(K)] ### 방향리스트 dirlst = [(0,0), (-1,0)

원문보기 내부링크
Naver Blog

백준 B2239-스도쿠 with 파이썬

문제 2239번: 스도쿠 문제 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다. 하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프... www.acmicpc.net 풀이 이 문제는 백트래킹 연습용으로 풀기 좋은 문제인 것 같다. 시간 관리를 잘해야하는 문제로 시간초과 2번 발생 후 해결책을 찾았다. 새로운 좌표를 갈때마다 확인하는 것이 아니라 행, 열, 3*3에 대해서 관리할 배열을 만들어놓고 진행하면 시간 초과를 해결할 수 있다. 코드 import sys

원문보기 내부링크
Naver Blog

백준 B4991-로봇 청소기 with 파이썬

문제 4991번: 로봇 청소기 문제 오늘은 직사각형 모양의 방을 로봇 청소기를 이용해 청소하려고 한다. 이 로봇 청소기는 유저가 직접 경로를 설정할 수 있다. 방은 크기가 1×1인 정사각형 칸으로 나누어져 있으며, 로봇 청소기의 크기도 1×1이다. 칸은 깨끗한 칸과 더러운 칸으로 나누어져 있으며, 로봇 청소기는 더러운 칸을 방문해서 깨끗한 칸으로 바꿀 수 있다. 일부 칸에는 가구가 놓여져 있고, 가구의 크기도 1×1이다. 로봇 청소기는 가구가 놓여진 칸으로 이동할 수 없다. 로봇은 한 번 움직일 때, 인접한 칸으로 이동할 수 있다. 또, 로봇은 같은 칸을 여러... www.acmicpc.net 풀이 이 문제는 2번의 시간초과와 한번의 틀렸습니다로 해결한 문제다. 틀렸습니다는 코드 실수로 발생했고 시간초과는 풀고 나니 이해가 되는 부분이다. 어차피 모든 좌표 별로 거리는 변하지 않으니깐 미리 좌표끼리의 최단 거리를 구하고 백트래킹을 진행하는게 좋은 방식인 것 같다. 코드 import

원문보기 내부링크
Naver Blog

코드트리 - 코드트리 빵(삼성코테기출) with 파이썬

문제 코드트리 빵 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제는 삼성 SW 역량테스트 2022 하반기 오후 1번 문제다. 솔직히 구현 난이도가 좀 있었다고 생각한다. 처음에는 경로라던가 그런 부분들을 미리 설정해놓을까 생각했지만, 단계가 진행되면서 막히는 부분이 새롭게 생기기 때문에 그렇제 진행하면 안된다는 걸 파악하고 단계마다 루트를 찾는 방식과 최단 거리를 게산하는 방식을 택했다. 한 번 틀린 이유는 문제를 제대로 이해하지 못해서인데, 고치고 나니 그 부분을 캐치 못했구나 하는데 실제 시험 문제였다면 이유도 모르고 탈락했을 것 같다. 코드 ''' 시도 결과 수행 시간 메모리 풀이시간 풀이과정 1차 런타임 에러 N/A N/A 1h 20m 초기 풀이 과정 2차 맞았습니다! 188ms 33MB 15m 못 가게 막는 걸 사람들이 이

원문보기 내부링크
Naver Blog

코드트리 - 산타의 선물 공장2(삼성코테기출) with 파이썬

문제 산타의 선물 공장 2 | 삼성 SW 역량테스트 기출문제 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제는 코드트리빵에 이어서 나온 삼성 코테 2022년도 하반기 오후 2번 문제다. 특정 자료구조를 모르면 못 푸는 문제로 링크드리스트라는 자료 구조를 사용해야 한다. 나 같은 경우는 그걸 잘 파악하지 못했다가, 산타 선물 공장 1을 보고 딕셔너리로 구현할 수 있다는걸 알았다. prev, next, head, tail, beltboxcnt로 크게 5개 변수로 관리하면서 진행했다. prev[num]은 num 상자 앞, next[num]은 num 상자 뒤로 없는 경우는 -1로 처리한다. head, tail은 각 벨트별 맨 앞 박스, 맨 뒷 박스를 관리하는 변수로 head[num], tail[num]은 num번 벨트의 맨 앞 상자, 맨 뒷 상자를 뜻한다. beltboxc

원문보기 내부링크
Naver Blog

백준 B17824-주사위 윷놀이 with 파이썬

문제 17825번: 주사위 윷놀이 문제 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다. 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출 문제로,,, 진짜 어렵게 풀면 끝도 없이 어렵게 풀리는 역겨운 문제다. 처음 풀 때는 그래프를 생각하지 못하고 직접 리스트로 문제에서 제공한 방식대로 진행했는데 진짜 답도 없었다. 이후 해당 문제는 내가 직접 그래프를 만들어서 풀면 쉽고 간단하고 빠르게 풀

원문보기 내부링크
Naver Blog

백준 B3190-뱀 with 파이썬

문제 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 벽이나 자기자신... www.acmicpc.net 풀이 이 문제는 보면 딱 바로 deque을 써서 풀이하는 방식이구나를 생각할 수 있다. 빠르게 풀이하고 예전 코드를 봤는데.... 내가 이걸 이렇게 풀이했다고? 놀랐다. 예전에는 이 문제를 재귀로 해결했었기 때문이다. 물론 시간은 4ms더 빠르긴 했지만 당시 1번의 Recursion Error와 3번

원문보기 내부링크
Naver Blog

백준 B21608-상어 초등학교

문제 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N 2 명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N 2 번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 ... www.acmicpc.net 풀이 처음 풀 때는 실수도 안하고 한번에 통과했던데 요즘 진짜 슬럼프인지 한번 꼭 실수하고 맞는 경향이 있다. 이 부분에 대해서 많이 생각해봐야할 것 같다. 최종적으로는 더 빠른 코드를 작성했다. 오늘 잊지 않아야할 점은 우선순위를 두고 갱신할 때 초기에 선언하는 변수값이 그대로 유지될

원문보기 내부링크
Naver Blog

백준 B17142-연구소 3 with 파이썬

문제 17142번: 연구소 3 문제 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다... www.acmicpc.net 풀이 이 문제도 삼성 코테 기출이다. BFS와 재귀를 잘 사용할 줄 알아야지 해결 가능하다! 연구소 배열을 입력받으면 재귀를 이용하여 M개 뽑을 수 있는 경우의 수를 계산하고 각 경우마다 몇 초 내로 꽉 채울 수 있는지 계산해야한다. 테케가 제공되긴 하지만 테케가 없다고 한다면 제일 놓치기

원문보기 내부링크
Naver Blog

백준 B14501-퇴사 with 파이썬

문제 14501번: 퇴사 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 T i 와 상담을 했을 때 받을 수 있는 금액 P i 로 이루어져 있다. N = 7인 경우에 다음과 같은 상담 일정표를 보자. 1일 2일 3일 4일 5일 6일 7일 T i 3 5 1 1 2 4 2 P i 10 20... www.acmicpc.net 풀이 이 문제도 삼성 코테 기출 문제다. 보자마자 DP로 풀 수도 있다고 생각했지만, 개인적으로 다이나믹 프로그래밍은 많이 약한 부분이고, 삼성 코테에서 많이 출제되는 유형이 아니기 때문에 재귀로 해결했다. 진짜 간단한 문제인데 생각보다 고생했다. 범위 조절을 잘 못해서 그런 것 같다. 테케가 친

원문보기 내부링크
Naver Blog

백준 B6593-상범 빌딩 with 파이썬

문제 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마... www.acmicpc.net 풀이 이 문제는 BFS 숙련도 향상 겸 풀이를 진행해봤다. 난이도는 어렵지 않다. 1차에 통과했고 크게 고민할 부분도 없었던 문제다. 대부분의 문제가 2차원이라면 이 문제는 3차원이라는 점이 독특하지만 방향 관련해서도 기본적인 동서남북상하로만 제공되어 큰 어려움 없이 해결 가능했다. 코드 im

원문보기 내부링크
Naver Blog

삼성 코테 준비 꿀팁 with 파이썬

삼성 코테 기출 문제를 풀면서 자주 나오는 유형을 일반화해서 문제 풀이 시간을 줄이기 위해 정리해보았다. 이동 중 벽에 부딪혀서 방향이 전환되는 경우 관련 문제 : 백준_낚시왕, 코드트리_토끼의 경주 ''' 배열은 R*C (행, 열)이라고 가정, dir은 0,1,2,3으로 부여되면서 상, 하, 우, 좌라고 가정 speed는 한번 이동할 때 가야하는 칸수 (낚시왕에서는 상어의 속도) sd는 이동하려는 방향 (낚시왕에서는 상어의 방향) ''' ROW = [i for i in range(R)] + [i for i in range(R-2,0,-1)] COL = [i for i in range(C)] + [i for i in range(C-2,0,-1)] dirlst = [(-1,0), (1,0), (0,1), (0,-1)] # 0:상, 1:하, 2:우, 3:좌 changedir = {0:1, 1:0, 2:3, 3:2} di, dj = dirlst[sd] ### 상어의 방향 x, y = (i

원문보기 내부링크
Naver Blog

백준 B20055-컨베이어 벨트 위의 로봇 with 파이썬

문제 20055번: 컨베이어 벨트 위의 로봇 문제 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다. 벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 A i 이다. 위의 그림에서 1번 칸이 있는 위치를 " 올리는 위치 ", N번 칸이 있는 위치를 " 내리는 위치 "라고 한다. 컨베이어 벨트에 ... www.acmicpc.net 풀이 그렇게 어렵지 않은 문제인데 실수해서 많이 시간을 낭비했다. down을 선언할 때 순간 뒤집어야하는 부분을 잊어서 마지막 테케를 계속 해결하지 못했다. 이 부분을 고치고 나서는 빠르게 해결 가능했다. 코드 import sys input = sys.stdin.readline

원문보기 내부링크
Naver Blog

코드트리_싸움땅 with 파이썬

문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 해당 문제는 삼성 코테 22년도 하반기 오전 1번 문제다. 실수가 많이 발생할 수 있는 문제고 난 실수를 완벽하게 캐치해내지 못하고 결국 2번을 다 지우고 새로 작성하면서 문제를 해결할 수 있었다. 제일 큰 차이는 총 관리를 원래는 하나의 값으로 하다가 리스트로 변경했는데 그게 맞는 것 같다. 요즘 한번에 통과 못하는 경우가 너무 많아서 문제가 많다. 조금만 더 깊게 생각하고 상황을 대비하면서 풀이하는 방식으로 해야하는데... 그걸 못하고 있긴 하다. 코드 ''' 시도 결과 수행 시간 메모리 풀이 시간 풀이 1차 틀렸습니다 94ms 30MB 1시간 초기 풀이 과정 2차 틀렸습니다 68ms 29MB 1시간 싹 다 지우고 다시 풀었음 3차 맞았습니다! 116ms 31MB 1시

원문보기 내부링크
Naver Blog

백준 B15686-치킨 배달 with 파이썬

문제 15686번: 치킨 배달 문제 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다. 이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 " 치킨 거리 "라는 말을 주로 사용한다. 치킨 거리 는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리 를 가지고 있다. 도... www.acmicpc.net 풀이 해당 문제를 2번째 푸는데 이전과 같은 실수를 반복했다. 맨해튼 거리를 사용하는데 굳이 BFS를 사용해 시간초과를 야기했다. 다시한번 시간 복잡도 계산 후 문제 풀이를 진행해야겠다는 생각이 들었다. 코드 ''' 오후 1시 15분 start 30분 1차 제출 이전과 같은 실수를 반복함 맨

원문보기 내부링크
Naver Blog

코드트리-토끼와 경주(삼성코테기출) with 파이썬

문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제도 포탑 부수기와 같이 23년도 상반기 오전 삼성 코테 기출 문제라고 한다. 솔직히 구현은 진짜 쉬웠지만, 시간 초과와의 싸움이었다. 우선순위를 강조하기에 우선순위 큐를 사용하여 문제를 푸는 것이 용이하다고 판단했다. 내 시간 초과의 주범은 토끼가 이동할 때 한칸씩 이동했던 부분이었다. 수식으로 일반화하는게 나한테는 개인적으로 어려워서 한칸씩 이동하는 방식으로 풀이했는데 그게 문제였다. 이 부분은 가로 세로 부분을 길게 연장한 리스트를 따로 선언했고 거기를 움직이면서 나머지 연산을 통해 위치 파악을 했다. 그랬더니 시간 초과는 해결되었다. 이후 아직도 잘 모르지만, 다른 코드와의 속도 차이가 커서 확인해본 결과, 토끼 점수 관리 방식의 차이였다. 나는 토끼 점수를

원문보기 내부링크
Naver Blog

백준 B21609-상어 중학교 with 파이썬

문제 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r 1 - r 2 | + |c 1 - c 2 | = 1을 만족하는 두 칸 (r 1 , c 1 )과 (r 2 , c 2 )를 인접한 칸이라고 한다. 블록 그룹은... www.acmicpc.net 풀이 백준에서 문제명에 상어가 들어가면 일단 삼성 기출 문제라고 보면 될 것 같다. 그리고 대부분 구현 문제다. 이번 상어중학교 같은 경우는 빡센 난이도의 구현 문제는 아니었던 것 같다. 이번 문제에서 실수가 많이 발생할 것 같은 부분은 무지개를 블록 그룹을 셀 때 방문처리하고 다시 미방문

원문보기 내부링크
Naver Blog

백준 B14889-스타트와 링크 with 파이썬

문제 14889번: 스타트와 링크 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 S ij 는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 S ij 의 합이다. S ij 는... www.acmicpc.net 풀이 삼성 기출을 다시 풀어보기 시작했다. 이전에 내가 풀었던 코드와 비교해가면서 발전했는지를 확인하고 있다. 이 문제 같은 경우는,,, 이전의 내가 더 잘 푼것 같다. 그 때는 시간초과도 안내고 잘 풀었는데 오늘의 난,, ,시간초과를 발생시켰다. 물론 풀이 방법을 다르게 했지만 내가 너

원문보기 내부링크
Naver Blog

백준 B17472-다리 만들기2 with 파이썬

문제 17472번: 다리 만들기 2 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인... www.acmicpc.net 풀이 해당 문제는 처음에는 풀지 못했다. 다양한 풀이 방식이 있지만, 난 하나도 생각해내지 못했다. 오히려 완전 탐색으로 해결하려고 했다. 그 과정에서 실수를 해결하지 못하고 포기했다가 주말을 이용해 다시 해결한 문제다. 간단히 말하면 섬별 최소 거리를 구한 뒤 프림 알고리즘을 이용해

원문보기 내부링크
Naver Blog

백준 B18808-스티커 붙이기 with 파이썬

문제 18808번: 스티커 붙이기 문제 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연결되어 있다. 또한 모눈종이의 크기는 스티커의 크기에 꼭 맞아서, 상하좌우에 스티커가 포함되지 않는 불필요한 행이나 열이 존재하지 않는다. 아래는 올바른 모눈종이의 예시이다. 주황색 칸은 스티커가 붙은 칸을, 하얀색 칸은 스티커가 붙지 않은 칸을 나타낸다. 반면 아래는 올바르지 않은 모눈종이의 예시이다. 첫 번째는 윗쪽에 불필요한 행이 있고, 두... www.acmicpc.net 풀이 단순 구현 문제다. 배열 회전을 할 줄 안다면 쉽게 풀이 가능하다. 근데 내 코드는 제출하신 다른 분 코드들보다 속도가 많이 느리다. 아마도 계속 새로운 배열을 생성하고 확인하는 과정에서 많은 시간을 소모하는 것 같다. 코드 ### 초기 풀이 과정: 제일 먼저 생각한건 스티커 회전을

원문보기 내부링크
Naver Blog

백준 B4577-소코반 with 파이썬

문제 4577번: 소코반 문제 소코반은 1982년에 일본에서 만들어진 게임으로, 일본어로 창고지기라는 뜻이다. 이 게임은 캐릭터를 이용해 창고 안에 있는 박스를 모두 목표점으로 옮기는 게임이다. 목표점의 수와 박스의 수는 같다. 플레이어는 화살표(위, 아래, 왼쪽, 오른쪽)를 이용해 캐릭터를 아래와 같은 규칙으로 조정할 수 있다. 캐릭터에게 지시한 방향이 빈 칸(박스나 벽이 아닌 곳)인 경우에는 그 칸으로 이동한다. 지시한 방향에 박스가 있는 경우에는, 박스를 민다. 이 경우에는 박스가 이동할 칸도 비어있어야 한다. 지시한 방향이 벽인 경우, 또는 박스가 ... www.acmicpc.net 풀이 이 게임 초등학교 다닐 때 전자사전에 있던 게임인 것 같다. 즐거운 추억을 가지고 시작했다. 문제 난이도는 어렵지 않았다. 진짜 단순 구현 문제라고 생각했고 코딩을 시작하면서 몇 개의 경우의 수가 있구나를 확인했다. 해당 경우의 수들을 정리하고 코딩으로 구현하니 바로 해결 가능한 문제였다.

원문보기 내부링크
Naver Blog

SWEA 프로세서 연결하기 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 지금 받는 교육 첫 야자 때 풀어보라고 주신 문제였고 그 때의 난 아마 약 10번 정도의 시도 끝에 못 풀었다. 오늘의 난 해결했다. 그래도 뭔가 시원시원하게 해결해내지 못해서 많이 아쉽다. 속도도 빠른 편이다. 간단하게 문제를 이야기하자면 이미 전원에 연결된 코어들을 제외하고 코어별로 전선을 연결할 수 있는 경우의 수를 저장해놓고 완전 탐색을 돌리면 된다. 가지치기를 통해서 약 300ms를 단축시킨 것 같은데 그 가지치기 조건으로는 남은 코어의 수를 다 더해도 finalcnt를 넘을 수 없다면 멈추게 했다. 코드 T = int(input()) for tc in range(1, T+1): N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)]

원문보기 내부링크
Naver Blog

백준 B12100-2048(Easy) with 파이썬

문제 12100번: 2048 (Easy) 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) <그림 1> <그림 2> <그림 3> <그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된... www.acmicpc.net 풀이 항상 예전부터 풀고 싶었는데 기출 문제여서 참았던 문제다. 삼성 기출 문제로 언제 기출인지는 모르겠다. 아마도 구현 부분에 있어서 어려운 부분은 없지만 계속 틀린다면 숫자를 합치는 과정을 잘못 구현한 것이라고 생각한다. 아마 밑에 만들어놓은 리스트들 하나씩 적용했을 때 예상

원문보기 내부링크
Naver Blog

코드트리-포탑 부수기(삼성코테기출) with 파이썬

문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 이 문제는 23년도 상반기 삼성 오전 기출 문제라고 한다. 문제에서 주어진 테케가 비교적 부실했고 제출해서 틀린걸 알아서 고쳐나간 문제다. 실제 시험이었다면 떨어졌다고 해도 어쩔 수 없다. 이 문제를 풀면서 깨달은 점은 무조건 격자의 크기를 고려하고 최단거리는 BFS로 풀자고 머릿속에 넣어야한다. 솔직히 구현이 어렵지 않았는데 DFS로 접근했다가 시간초과의 벽 때문에 약 2시간을 허비한 문제다. BFS로 바꾸자마자 해결했는데 너무 아쉬움이 많이 남은 문제다. 실제로 코드 사이사이 디버깅용 코드를 삽입해 제대로 문제를 해결하고 있는지 확인했다. 코드 ### 총 풀이시간 : 3시간 개힘듦... ### 1차 시도: 틀렸습니다 풀이 시간: 1시간 반 ### 2,3차 시도: 시간초

원문보기 내부링크
Naver Blog

백준 B17140-이차원 배열과 연산 with 파이썬

문제 17140번: 이차원 배열과 연산 문제 크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다. R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다. C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다. 한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과... www.acmicpc.net 풀이 이차원 배열과 연산이라는 문제 또한 단순 구현인 것 같다. 풀이를 보는 과정에서 몇 분들은 collections 모듈에서 Counter 함수를 불러와서 사용했다. 개인적으로 내 코드에서는 불러와 사용하는 방식이 더 많은 시간을 소모했다. 나는 그 함수를 생각해내지 못하고, 바로

원문보기 내부링크
Naver Blog

백준 B16234_인구이동 with 파이썬

문제 16234번: 인구 이동 문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 ... www.acmicpc.net 풀이 이 문제도 아마 삼성 코테 기출 문제로 알고 있다. 문제 난이도가 높지 않았지만, 풀면 풀수록 더욱더 최적화시켜서 속도를 높일 수 있었던 문제다. 요즘 구현 문제를 풀면 풀수록 배열에서 좌표들을 관리하는 것보다 딕셔너리나 리스트를 상황에 맞게 사용해서 관리하는게 더 편한 것 같다. 좌표

원문보기 내부링크
Naver Blog

백준 B17837_새로운게임2 with 파이썬

문제 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 ... www.acmicpc.net 풀이 새로운 게임2 라는 이 문제는 다양한 풀이 과정이 있는 것 같다. 정확히는 풀이 과정보다는 다양한 자료구조를 사용해서 문제에 접근할 수 있는 것 같다. deque를 사용한 분들도 많이 봤다. 나 같은 경우는 리스트 인덱싱을 통해 문제를 빠르게 해결할 수 있었다. 요즘 딕셔너리로 좌

원문보기 내부링크
Naver Blog

백준 B3197-백조의 호수 with 파이썬

문제 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXX... www.acmicpc.net 풀이 진짜 힘들었다. 처음으로 풀어본 플래티넘 단계의 문제였다. 역시 플래티넘의 벽은 진짜 높은 것 같다. 단순한 BFS라고 생각하고 들어갔다가 호되게 혼난 문제다. 범위가 너무 커서 시간초과가 날 걸 알면서도 처음엔 아이디어가 생각나지 않아서 고생했다. 그러나 최적화를 계속 고민하다보니 빠르

원문보기 내부링크
Naver Blog

코딩 테스트 준비 링크 정리

백준 BaekJoon 백준 B1799-비숍 with 파이썬 백준 B1941-소문난칠공주 with 파이썬 백준 B17836-공주님을 구해라! with Python 백준 B12581-숨바꼭질2 with Python 백준 B4179-불! with Python 백준 B2573-빙산 with Python 백준 B3055-탈출 with Python 백준 B7569-토마토 with Python 백준 B1726 로봇 with Python 백준 B3197-백조의 호수 with 파이썬 백준 B16927-배열돌리기2 with 파이썬 백준 B10157-자리배정 with 파이썬 백준 B17070-파이프 옮기기1 with 파이썬 백준 B14395-4연산 with 파이썬 백준 B16986-인싸들의 가위바위보 with 파이썬 백준 B17135-캐슬 디펜스 with 파이썬 백준 B1939-중량제한 with 파이썬 백준 B2096-내려가기 with 파이썬 백준 B18809-Gaaaaaaaaaarden with 파이

원문보기 내부링크
Naver Blog

SWEA 벌꿀채취 with 파이썬

문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 해당 문제는 모의 SW 역량테스트 문제다. 문제를 다 읽고 나서 수익을 계산하는 부분이 그리디를 사용해야겠다는 생각이 들었다. 그러나,,, 나는 그리디를 잘 못한다. 기본 그리디인 줄 알면서도 나한테는 쉽지 않았고, 다른 방식이 있나 고민했다. 결국 난 완전탐색을 택했다. 주어진 값들의 범위가 크지 않았기 때문에 시간 복잡도 계산 결과 가능하다고 판단했고 채취한 꿀의 모든 조합을 계산해 최대 수익을 구하는 함수를 만들어 문제를 해결했다. 코드 ### 1차 시도 : 66,716kb 388ms ### 채취한 꿀에서 최대 수익을 구하는 부분을 탐욕(그리디)로 해결하려고 했으나, 생각해내지 못함 ### 시간복잡도 계산 결과 주어진 시간 내에 가능하다고 판단 N이 최대 10, M이 최대 5였기 때문에 충분했음 ### 모든 조합을 구해서 최대

원문보기 내부링크
Naver Blog

백준 B17070-파이프 옮기기1 with 파이썬

문제 17070번: 파이프 옮기기 1 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다. 파이프는 매우 무겁기 때문에, 유현이는 파이프를... www.acmicpc.net 풀이 해당 문제는 3차 시도만에 해결한 문제다. 1차 2차 때는 BFS로 접근했지만 70%대에서 계속 시간초과가 발생했다. 아무리 줄여봐도 시간 초과를 해결할 수 없다고 판단하여서, 다른 접근 방식을 고민해봤고 그 결과 DP를 생각했다. DP 풀이 방식은 코드에 주석으로 자세하게 적어

원문보기 내부링크
Naver Blog

백준 B10157-자리배정 with 파이썬

문제 10157번: 자리배정 문제 어떤 공연장에는 가로로 C개, 세로로 R개의 좌석이 C×R격자형으로 배치되어 있다. 각 좌석의 번호는 해당 격자의 좌표 (x,y)로 표시된다. 예를 들어보자. 아래 그림은 가로 7개, 세로 6개 좌석으로 구성된 7×6격자형 좌석배치를 보여주고 있다. 그림에서 각 단위 사각형은 개별 좌석을 나타내며, 그 안에 표시된 값 (x,y)는 해당 좌석의 번호를 나타낸다. 가장 왼쪽 아래의 좌석번호는 (1,1)이며, 가장 오른쪽 위 좌석의 번호는 (7,6)이다. (1, 6) (7, 6) (4, 4) (7, 4) (1, 3) (6, 3)... www.acmicpc.net 풀이 나는 보통 이런 문제를 먼저 이동해야하는 방향이라던가 좌표를 리스트로 만들어놓고 해당 리스트를 순회하면서 좌표를 이동시키는 방식을 사용한다. 시간은 2배로 걸리지만, 디버깅이 잘되고 바로 생각이 되기 때문이다. 그러나 이 문제는 R, C의 범위가 1000까지고 K 또한 1,000,000까지이

원문보기 내부링크
Naver Blog

백준 B16927-배열돌리기2 with 파이썬

문제 16927번: 배열 돌리기 2 문제 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ... www.acmicpc.net 풀이 이 문제는 단순 구현이다 그러나 1차 시도에서는 진짜 길게 구현해서 코드의 가독성이 매우 떨어졌다. 이후 반복하는 부분을 합치자고 판단했고 2차 시도를 통해 코드의 가독성을 높일 수 있었다. 코드 ### 1차 시도 : 124496kb 196ms ### 진짜 단순 무식하게 직접 구현했다. ### 아이디어 방식은 외곽 줄의 값들을 리스트로 만들어서 R번 회전시킨 다음에 다시 넣는 방식 사용 ### R의 크기가 너무 컸지만 리스트 길이의 나

원문보기 내부링크
Naver Blog

코드트리-예술성(삼성코테기출) with 파이썬

문제 https://www.codetree.ai/training-field/frequent-problems/problems/artistry?page=3&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 해당 문제는 22년 상반도 삼성 코테 기출 문제다. 이전 게시글의 술래잡기와 같이 출제되었던 문제다. 개인적으로 난이도는 술래잡기보다 쉬웠다. 이 문제도 단순 구현이지만, 좀 생각해봐야하는 문제다. 그룹별 맞닿은 변의 수를 구하는 법과 회전하는 법을 구현하는게 쉽지는 않다. 그러나 차근차근 정리해서 코딩하면 크게 어려움이 없고 엣지 케이스도 없는 문제라 쉽게 풀이 가능했다. 코드 ### 1차 시도: 196ms 31MB 풀이시간 : 1시간 ### 중점적으로 생각한건 맞닿은 변의 수를 어떻게 빠르게 계산할지와

원문보기 내부링크
Naver Blog

[일상] 너의 시간 속으로 (넷플릭스) 감상 후기

저번주에 그토록 기다리던 작품 '너의 시간 속으로'가 나왔다. 원작 상견니 영화판을 재밌게 봤었기 때문에 큰 기대를 하고 봤다. 처음에 전여빈이라는 배우가 잘 어울릴까 생각했는데 진짜 캐스팅 제대로 한 것 같다. 내용이 대만 원작이랑 같은지는 잘 모르겠다. 드라마판을 보지 않아서 대만 원작과 같은 전개 방식인지는 모르겠지만, 한국 시대와 배경에 맞게 잘 풀어나갔다. 참고로 요즘 내 눈물 모아만 무한 반복하면서 듣고 있다. 스포가 될 수도 있지만 1화에서부터 알 수 있듯이 시간 워프를 하면서 진행되는 러브스토리다. 감상 후기 간단하게 감상 후기를 남기자면 진짜 재밌게 봤다. 예전에 봐서 확실하지는 않지만 원작 상견니 영화버전에서는 그렇게 해피 엔딩은 아니었던 걸로 기억한다. 너의 시간속으로도 해피엔딩이라면 해피 엔딩이지만, 내가 좋아하는 결말은 아니었다. 대만 작품은 고유의 청량한 느낌(?)이 있는데 너의 시간 속으로는 그런 느낌은 없었다. 청량한 느낌은 대만 로맨스물의 특징이랄까?

원문보기 내부링크
Naver Blog

백준 B16986-인싸들의 가위바위보 with 파이썬

문제 16986번: 인싸들의 가위바위보 문제 혹시 마지막으로 엠티를 간 것이 언제인가? 엠티를 안간지 꽤 오래됐다면 요즘 유행하는 인싸들의 가위바위보를 모를 것이다. 요즘 인싸들은 엠티에서 평범한 가위바위보를 시시하다는 이유로 더 이상 취급하지 않는다. 대신 가위불바위총번개악마용물공기보스펀지늑대나무사람뱀을 한다. 이 게임의 명칭이 다소 긴 관계로 문제 내에서는 전체 명칭을 적는 대신 이 게임의 또 다른 이름인 인싸 가위바위보로 부르겠다. 인싸 가위바위보는 평범한 가위바위보와 같이 각 손동작간의 상성이 정해져있다. 인싸 가위바위보는 평범한 가위바위보보다 흥미진진하고 재밌... www.acmicpc.net 풀이 이 문제는 브루트포스와 백트래킹의 대표적인 문제라고 할 수 있다. 이제 이정도 난이도는 빠르게 구현하고 쉽게 풀어나가야 할 것 같다. 지우가 낼 수 있는 모든 경우의 조합을 구하고 경희와 민호와 비교해가면서 구현하면 빠르게 풀 수 있다. 코드 import sys input = s

원문보기 내부링크
Naver Blog

백준 B17144-미세먼지 안녕! with 파이썬

문제 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 A r,c 이다. 1초 동안 아... www.acmicpc.net 풀이 삼성 기출 문제다. 생각보다 어렵지 않은 구현 문제였다. 테스트케이스가 잘 되어있어서 실수가 발생할 확률도 매우 적었다. 요즘 한줄한줄 종이에 적으면서 놓치는 부분이 없도록 읽어서 그런지 아예 이해를 하지 못해서 발생하는 오류가 아닌 이상, 포인트를 놓쳐서 발생하는 실수는 확실히

원문보기 내부링크
Naver Blog

백준 B17143-낚시왕 with 파이썬

문제 17143번: 낚시왕 문제 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다. 낚시왕이 오른쪽으로 한 칸 이동한다. 낚시왕이 있는 열... www.acmicpc.net 풀이 이 문제는 난이도가 골드 1이다. 그만큼 구현에 있어서 큰 어려움이 있다는 것이다. 내가 생각하기에 난이도가 있는 부분은 상어의 이동이다. 한칸씩 이동할 경우 100% 시간 초과가 발생하게 된다. 솔직히 스피드를 최적화하고 이동시킨다면 속도는 빠르지 않아도 구현하는데 큰 어려움이 없다. 나

원문보기 내부링크
Naver Blog

백준 B14395-4연산 with 파이썬

문제 14395번: 4연산 문제 정수 s가 주어진다. 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오. 사용할 수 있는 연산은 아래와 같다. s = s + s; (출력: +) s = s - s; (출력: -) s = s * s; (출력: *) s = s / s; (출력: /) (s가 0이 아닐때만 사용 가능) 입력 첫째 줄에 s와 t가 주어진다. (1 ≤ s, t ≤ 10 9 ) 출력 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지... www.acmicpc.net 풀이 진짜 3번의 틀림 끝에 풀었다. 다 풀고 나니 그렇게 난이도가 높은 문제가 아니란걸 알 수 있지만, 너무 쉽게 본 문제다. T가 해당하는 경우를 다 구분해서 코딩한다면 쉽게 풀이 가능한 문제였다. 코드 ### 1차 시도 -> 시간 초과 ### 무조건 된다고 생각하고 진행했기 때문에 시간 초

원문보기 내부링크
Naver Blog

코드트리-술래잡기(삼성코테기출) with 파이썬

문제 https://www.codetree.ai/training-field/frequent-problems/problems/hide-and-seek/description?page=3&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 풀이 해당 문제는 코드트리에서 풀 수 있는 문제다. 22년도 상반기 삼성 코딩테스트 기출 문제로 1번으로 나왔던 문제라고 한다. 이 문제랑 예술성이라는 문제가 같이 출제된 문제인데 개인적으로는 예술성이 좀 더 난이도가 낮다고 느껴졌다. 단순 구현 문제지만 엄청난 빡구현이다. 도망자, 술래의 위치를 배열에 넣지 않고 따로 리스트와 좌표를 선언해서 컨트롤했다. 그리고 입력하면서 바로 내가 컨트롤하기 편하게 변경해서 입력하여 쉽게 처리할 수 있었다. 처음에 도망자를 딕셔너리로 관리할까 생

원문보기 내부링크
Naver Blog

백준 B20058-마법사 상어와 파이어스톰 with 파이썬

문제 20058번: 마법사 상어와 파이어스톰 문제 마법사 상어는 파이어볼 과 토네이도 를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2 N × 2 N 인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다. 파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2 L × 2 L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. ... www.acmicpc.net 풀이 진짜 이 문제는 힘들었다. 솔직히 난이도가 높지 않았는데 a로 분배되는 모래 양에 대해서 제대로 이해하지 못해서 큰 어려움이 있었다. 문제를 이해하고나서는 20분도 안돼서 해결했던 문제였다. 대신 N의 범위 때문에 재귀로 넘어가게 된다면 큰 문제가 발생한다. 코드 ### 테스트케

원문보기 내부링크
Naver Blog

백준 B21610-마법사 상어와 비바라기 with 파이썬

문제 21610번: 마법사 상어와 비바라기 문제 마법사 상어는 파이어볼 , 토네이도 , 파이어스톰 , 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다. 격자의 가장 왼쪽 윗 칸은 (1... www.acmicpc.net 풀이 이 문제도 삼성 기출 문제이다. 백준 삼성 기출에서 마법사 상어 시리즈가 있다. 개인적으로 이런 문제 유형들이 나랑 상성이 좋다. 단순 구현이다. 물론 최적화된 속도로 코드를 작성하지는 못하더라도 예전에 데이터를 자주 처리해와서 그런지 구현이 제일 쉽고 정확도가 높다. 이런 문

원문보기 내부링크
Naver Blog

백준 B15685-드래곤 커브 with 파이썬

문제 15685번: 드래곤 커브 문제 드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다. 시작 점 시작 방향 세대 0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다. 1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 ... www.acmicpc.net 풀이 해당 문제는 다음 세대로 넘어갈 때의 좌표 변화의 규칙을 파악하면 진짜 쉬운 문제다. 솔직히 말하자면, 나는 해당 규칙을 찾을 생각보다 직접 10세대까지 좌표 리스트 생성을 목표로 하고 있었다. 그러나 경우의수가 2배씩 커지는걸 깨닫고 5세대까지 만들다가 포기했다. 해당 문제 또한 삼

원문보기 내부링크
Naver Blog

백준 B17135-캐슬 디펜스 with 파이썬

문제 17135번: 캐슬 디펜스 문제 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격... www.acmicpc.net 풀이 해당 문제도 삼성 상시 코테 기출 문제로 알고 있다. 문제 자체는 단순 구현이지만 아이디어에 따라 시간 단축이 가능하다. 나 같은 경우는 문제 설명 그대로 대부분 구현했지만, 다른 코드를 살펴보면 다양한 방식이 있다. 내가 보기엔 제일 이해하기 쉽고 빠른 코드는 다음 링크에 첨부하려고

원문보기 내부링크
Naver Blog

백준 B16236-아기 상어 with 파이썬

문제 16236번: 아기 상어 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 ... www.acmicpc.net 풀이 해당 문제는 단순 구현 문제지만 여러 포인트들을 놓치지 않고 구현하는 것이 중요하다. 아기 상어보다 물고기 크기가 작거나 같으면 지나갈 수 있음, 작으면 먹을 수도 있음 거리는 가장 가까운 물고기부터 먹고, 기준은 가장 위, 가장 왼쪽일수록 먼저 먹음 맨해튼 거리로 물고기와의 거리는 측

원문보기 내부링크
Naver Blog

백준 B20056-마법사 상어와 파이어볼 with 파이썬

문제 20056번: 마법사 상어와 파이어볼 문제 어른 상어 가 마법사가 되었고, 파이어볼을 배웠다. 마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (r i , c i ), 질량은 m i 이고, 방향은 d i , 속력은 s i 이다. 위치 (r, c)는 r행 c열을 의미한다. 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는... www.acmicpc.net 풀이 삼성 기출 문제로 구현 문제이다. 구현 난이도가 높지 않았다. 단순히 내가 빨리 풀고 싶은 마음에 일반화를 잘못해서 한번 틀렸지만, 문제 난이도는 높지 않았다. 코드 ### 1차 실패 원인 -> 모두 홀수거나 짝수인 경우 일반화를 잘못함 import sys input = s

원문보기 내부링크
Naver Blog

백준 B20058-마법사 상어와 파이어스톰 with 파이썬

문제 20058번: 마법사 상어와 파이어스톰 문제 마법사 상어는 파이어볼 과 토네이도 를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2 N × 2 N 인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 얼음의 양을 의미한다. A[r][c]가 0인 경우 얼음이 없는 것이다. 파이어스톰을 시전하려면 시전할 때마다 단계 L을 결정해야 한다. 파이어스톰은 먼저 격자를 2 L × 2 L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다. ... www.acmicpc.net 풀이 이 문제도 삼성 기출문제다. 단순 구현 문제지만, 구현하는데 어느정도 난이도가 있다. 나 같은 경우는 문제를 제대로 이해하지 못해서 테스트케이스를 해결하지 못했지만, 마지막에 제대로 이해하고 쉽게 풀 수 있었다. 여기서 중요한건 2^N 부분을 회전시키는걸 잘 구현하면 큰 어려움이

원문보기 내부링크
Naver Blog

백준 B1939-중량제한 with 파이썬

문제 1939번: 중량제한 1939번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 중량제한 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 33256 9040 5539 25.613% 문제 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데... www.acmicpc.net 풀이 이 문제는 메모리 초과, 시간 초과 둘 다 발생해서 큰 어려움을 겪었다. 고민 끝에 다익스트라 알고리즘을 이용하여 문제를 해결했다. 기존 다익스트라를 그대로 사용하지 않고 기존 다익스트라에서는 거리를 가중치로 여겼다면 나는 다리가 버틸 수 있는 무게를 가중치로 여겨서 처리했다. 기존 알고리

원문보기 내부링크
Naver Blog

백준 B18809-Gaaaaaaaaaarden with 파이썬

문제 18809번: Gaaaaaaaaaarden 문제 길고 길었던 겨울이 끝나고 BOJ 마을에도 봄이 찾아왔다. BOJ 마을에서는 꽃을 마을 소유의 정원에 피우려고 한다. 정원은 땅과 호수로 이루어져 있고 2차원 격자판 모양이다. 인건비 절감을 위해 BOJ 마을에서는 직접 사람이 씨앗을 심는 대신 초록색 배양액과 빨간색 배양액을 땅에 적절하게 뿌려서 꽃을 피울 것이다. 이 때 배양액을 뿌릴 수 있는 땅은 미리 정해져있다. 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다. 아래는 초록색 배양액 2개를 뿌렸을 때의 예시이다. 하얀색 칸은 배양액을 뿌릴 수... www.acmicpc.net 풀이 이 문제도 시간과의 싸움이다. 골드 문제들을 풀면서 느낀건데 아이디어 자체가 어렵다기보다는 해당 아이디어를 얼마나 최적화해서 풀이하는지가 중요한 것 같다. 실제로 해당 문제 아이디어는 어렵지 않았고 계속 시간초과가 발생하다가 지우고 새로 작성해보니 바로 문제를 해결할

원문보기 내부링크
Naver Blog

백준 B2096-내려가기 with 파이썬

문제 2096번: 내려가기 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다. 먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다. 별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가... www.acmicpc.net 풀이 이 문제는 메모리 제한과의 싸움이다. 다행히 문제를 읽기 전에 메모리가 최대 4MB 밖에 되지 않다는 점을 확인해서 최대한 메모리를 사용하지 않는 코드를 구상하였고 그 결과 다음과 같은 코드를 작성했다. 윗 줄을 기준으로 구하는 것이 아니라 아랫줄을 기준으로 구상한다면 더 빠르고 메모리를

원문보기 내부링크
Naver Blog

백준 B14502-연구소 with 파이썬

문제 14502번: 연구소 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다. 예를 ... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출 문제로, BFS와 DFS를 조합한 문제라고 생각된다. 최근에 해당 문제를 풀기 17일 전에 풀이한 코드가 있는데 최근 코드와 비교해보니 진짜 많은 발전이 있다는 걸 알 수 있었다. 먼저 빈 칸들 리스트를 생성해서 벽을 세울 조합을 만들고 바이러스 리스트에서 뽑아서

원문보기 내부링크
Naver Blog

백준 B17471-게리맨더링 with 파이썬

문제 17471번: 게리맨더링 문제 백준시의 시장 최백준은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 최백준은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 백준시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다. 백준시는 N개의 구역으로 나누어져 있고, 구역은 1번부터 N번까지 번호가 매겨져 있다. 구역을 두 개의 선거구로 나눠야 하고, 각 구역은 두 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어... www.acmicpc.net 풀이 내 풀이 과정은 두 선거구가 아닌 한 선거구의 경우의 수를 구하고 각 경우마다 남은 선거구와 뽑은 선거구가 연결이 되어있는지의 여부를 확인하고 인구차를 계산하는 방식이다. 내 코드에서 개선 가능한 부분은 한 선거구만 구하는 것이 아니라 함수 내에서 두 선거구를 같이 구해준다면 시간을 비

원문보기 내부링크
Naver Blog

백준 B2668-숫자고르기 with 파이썬

문제 2668번: 숫자고르기 2668번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 숫자고르기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 15972 7032 5459 45.393% 문제 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이... www.acmicpc.net 풀이 진짜 어려움이 많았던 문제다. 계속된 시간초과로 풀기 어려웠는데 앞서 게리맨더링 문제를 풀고 힌트를 얻어서 해결하게 되었다. 조합을 만들고 2번째 줄의 수를 set를 이용하여 연산하는 과정에서 계속된 시간 초과가 발생했다. 게리맨더링에서의 풀이 방식에서 힌트를 얻어서 그래프를 통해서 문제

원문보기 내부링크
Naver Blog

백준 B15683-감시 with 파이썬

문제 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다. 1번 2번 3번 4번 5번 1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다. CCTV는 감시할 수 있는 방향에 있는 칸... www.acmicpc.net 풀이 이 문제는 삼성 코테 기출 문제로 알고 있다. 단순히 구현 문제로 큰 어려움이 없었다. 시간 초과나 메모리와의 싸움도 아니었기 때문에 쉽게 풀 수 있었던 문제가 아닌가 싶다. 더 깔끔한 코드들을 보면 일반화를 잘했지만, 난 주어진 짧은 시간동안은 일반화도 좋지만 양이 적다면 어느정도 좌표 처

원문보기 내부링크
Naver Blog

백준 B17281-야구 with 파이썬

문제 17281번: 문제 는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종료되고, 두 팀이 공격과 수비를 서로 바꾼다. 두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다. 9번 타자까지 공을 쳤는데 3아웃이 발생하지 않은 상태면 이닝은 끝나지 않고, 1번 타자가 다시 타석에 선다. 타순은 이닝이 변경되어도 순서를 유지해야 한다. 예를 들어, 2이... www.acmicpc.net 풀이 이 문제는 진짜로 야비하고 치사한 문제다. 어느 정도 코테를 준비한 사람들은 해당 문제의 풀이 방식을 쉽게 생각해낼 것이다. 여기서 포인트는 함수 사용이나 리스트 갱신도 좋지만 변수가 적을 때는 직접 선언해서 컨트롤하는게 편할 수도 있다. 내 코드를 보면 first, second, third 라는

원문보기 내부링크
Naver Blog

백준 B2606-바이러스 with 파이썬

문제 2606번: 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받... www.acmicpc.net 풀이 이 문제는 진짜 전형적인 BFS나 DFS로 해결 가능한 코드다. 시작하는 노드도 1번으로 지정되어 있기 때문에 간단한 BFS나 DFS 코드 구현이 가능하면 해결 가능한 문제다. 코드 ### 초기 그래프 생성 및 방문리스트 생성 N = int(input()) graph = [[] for _

원문보기 내부링크
Naver Blog

백준 B14500-테트로미노 with Python

문제 14500번: 테트로미노 문제 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다. 테트로미노 하나를 적... www.acmicpc.net 풀이 첫번째 방식은 문제에서 나온 테트로미노를 모두 좌표화 시켜서 리스트에 넣고 모든 좌표마다 테트로미노를 입력해보고 게산하는 방식으로 단점이 많음. 좌표 리스트를 만드는 과정에서 실수가 발생할 수 있고, 회전, 대칭한다는 점을 놓쳐서 몇 번 시도에서 틀림 두번째 방식은 소문난 칠공주에서 힌

원문보기 내부링크
Naver Blog

백준 B1799-비숍 with 파이썬

문제 1799번: 비숍 문제 서양 장기인 체스에는 대각선 방향으로 움직일 수 있는 비숍(bishop)이 있다. < 그림 1 >과 같은 정사각형 체스판 위에 B라고 표시된 곳에 비숍이 있을 때 비숍은 대각선 방향으로 움직여 O로 표시된 칸에 있는 다른 말을 잡을 수 있다. < 그림 1 > 그런데 체스판 위에는 비숍이 놓일 수 없는 곳이 있다. < 그림 2 >에서 체스판에 색칠된 부분은 비숍이 놓일 수 없다고 하자. 이와 같은 체스판에 서로가 서로를 잡을 수 없도록 하면서 비숍을 놓는다면 < 그림 3 >과 같이 최대 7개의 비숍을 놓을 수 있다. 색칠된 부... www.acmicpc.net 풀이 이 문제는 보통 N-queen을 풀고 나서 다음 난이도의 문제라고 하지만 생각보다 난이도가 매우 높았다. 시간 제한이 10초인 것을 봐서는 엄청난 시간이 걸리는 문제인지 알고 있었지만 이 문제를 스스로 푸는데 너무나도 많은 시간이 소모됐다. 오늘은 2가지 코드를 살펴보려고 한다. 하나는 내가 작

원문보기 내부링크
Naver Blog

백준 B14888-연산자 끼워넣기 with 파이썬

문제 14888번: 연산자 끼워넣기 문제 N개의 수로 이루어진 수열 A 1 , A 2 , ..., A N 이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 6... www.acmicpc.net 풀이 이 문제도 삼성 코테 기출 문제다. 문제 자체의 접근은 쉬웠다. 그러나 더 빠르게 더 간단하게 구현할 수 있었다는 걸 놓치고 있었다. 재귀를 구현할 때는 최대한 간결하게 만들어야지 실수를 줄일 수 있다는 점을 간과했다. 풀이 깃허브 : https://github.com/taeksg

원문보기 내부링크
Naver Blog

백준 B14499-주사위 굴리기 with 파이썬

문제 14499번: 주사위 굴리기 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 곳의 좌표는 (x, y) 이다. 가장 처음에 주사위에는 모든 면에 0이 적혀져 있다. 지도의 각 칸에는 정수가 하나씩 쓰여져 있... www.acmicpc.net 풀이 이 문제도 삼성 코테 기출 문제다. 솔직히 난이도가 높은 구현 문제는 아니었다. 근데 내가 아주 큰 실수를 해서 너무 오래 풀었다. 이런 사소한 실수를 줄여야하는데 다행히 스스로 캐치해서 해결했다는 점에 의의를 두고 있다. 처음에는 문제를 어렵게 접근했지만 계속 보면서 최대한 일반화하고 간결

원문보기 내부링크
Naver Blog

백준 B2636-치즈 with 파이썬

문제 2636번: 치즈 문제 아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다. 이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘... www.acmicpc.net 풀이 이 문제는 처음에는 보고 치즈에서 어떻게 접근해야하는지 생각했는데 빈칸에서 출발하면 되겠다라는 판단과 함께 아주 쉽게 풀 수 있었다. 코드 import sys from collections import deque input = sys.stdin.readline N, M = map(int, in

원문보기 내부링크
Naver Blog

백준 B2638-치즈 with 파이썬

문제 2638번: 치즈 문제 N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진... www.acmicpc.net 풀이 이 문제느 2636번 치즈와 거의 비슷한 문제지만 한 단계 업그레이드된 문제라고 볼 수 있다. 이 문제의 관건은 방문처리를 어떻게 처리해서 2개 이상의 변에서 외부 공기를 접촉하는지를 생각하면 풀 수 있다. 코드 import sys from collections import deque inpu

원문보기 내부링크
Naver Blog

백준 B16469-소년 점프 with 파이썬

문제 16469번: 소년 점프 문제 “OK 계획대로 되고 있어” 한국 힙합의 떠오르는 신성인 마미손은 악당 무리에게서 도망치고 있다. 악당 무리는 넉살, 스윙스, 창모 3명으로 이루어져 있다. 마미손은 도망치는 도중 R*C 크기의 미로를 만났고, 미로 안에 숨기로 했다. 뒤늦게 미로에 도착한 악당 무리는 마미손을 찾기 위해 뿔뿔이 흩어져 찾아보기로 했다. 이때 악당들은 항상 상하좌우로만 이동 가능하고, 이동 속도는 모두 같으며 칸 단위로만 이동 가능하다. 또한 악당들은 움직이지 않고 제자리에 멈춰있을 수도 있다. 넉살, 스윙스, 창모는 서로 다른 지점에서 마미... www.acmicpc.net 풀이 이 문제는 쉽게 접근하면 바로 풀 수 있지만 난 너무 어렵게 생각해서 골머리를 앓았다. 그러다가 갑자기 쉽게 접근할 수 있겠다는 생각이 들었고 바로 그 방식으로 해결할 수 있었다. 코드 import sys from collections import deque input = sys.stdi

원문보기 내부링크
1 2 3