본문 바로가기

코딩 테스트

 (202)
[Python] 백준 16236 아기 상어 https://www.acmicpc.net/problem/16236 문제 분석N x N 크기M마리 물고기와 아기상어 1마리한 칸에 최대 1마리의 물고기아기 상어와 물고기는 모두 크기를 가지고 있고, 크기는 자연수가장 처음의 아기상어 크기는 2아기상어는 1초에 상하좌우로 인접한 한 칸 씩 이동조건아기상어는 자신의 크기보다 작거나 같은 물고기가 있는 칸만 지나갈 수 있다.자신보다 작은 물고기만 먹을 수 있다.더 이상 먹을 수 있는 물고기가 공간에 없으면 엄마 상어에게 도움 요청먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러 간다.거리 : 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때 지나야하는 칸의 개수의 최..
[Python] 백준 2583 영역 구하기 https://www.acmicpc.net/problem/2583 문제 분석눈금 간격이 M x N 크기의 모눈종이눈금에 맞춰 K개의 직사각형을 그릴 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어 지는가그리고 각 영역의 넓이는 얼마인가 풀이넓이 우선 탐색 (bfs) 코드 설계직사각형 영역 찾기직사각형 영역 : 1직사각형 x : 0영역 찾기 0이고, 아직 방문하지 않았으면 덱에 넣기같은 영역의 범위 구하기모눈종이의 범위를 벗어나지 않고아직 방문하지 않았으며g 좌표의 값이 0이면 append → 가능한 영역 : area += 1 정답 코드import sysfrom collections import dequeinput = sys.stdin.readlineM, N, K = ma..
[Python] 백준 1238 파티 https://www.acmicpc.net/problem/1238 문제 분석N개의 숫자로 구분된 마을에 한 명의 학생이 살고 있다.N명의 학생이 x (1 이 마을 사이에는 총 M개의 단방향 도로들이 있고, i번째 길을 지나는데 Ti (1 각 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. - 최단거리오고가는 길이 다를 수 있다.N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구인가 풀이N명의 학생M 개의 이동할 수 있는 도로 정보 (단방향, 가중치)X : 모이는 곳1 ~ N 까지 반복distance[ i ] = i ~ X 의 최단거리 + X ~ i 의 최단거리이 중 가장 큰 값을 출력 코드 설계X에서 1~N까지의 최단거리는 다익스트라로 한번에 구하기1 ~ N까..
[Python] 백준 9095 1,2,3 더하기 https://www.acmicpc.net/problem/9095 문제 분석n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하라 풀이순서x, 중복o → 중복 조합 (product)dp뭘 저장해야 할까?초기조건2 = 1+12 = 2 3 = 1+1+13 = 1+23 = 2+13 = 3새로운 숫자에 대해 다음을 굳이 또 계산할 필요가 없다.  정답 코드1. 중복 조합import sysinput = sys.stdin.readlinefrom itertools import producttc = int(input())for _ in range(tc) : ans = 1 n = int(input()) nums = [1,2,3] for i in range(1, n) : # 1을 n..
[Python] 백준 2217 로프 https://www.acmicpc.net/problem/2217 문제 분석N개의 로프각 로프는 들 수 있는 물체의 중량이 서로 다를 수 있다.로프를 병렬로 연결하여 중량이 w인 물체를 들어올릴 때, 각 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.각 로프의 정보가 주어졌을 때, 로프들을 사용하여 들어올릴 수 있는 물체의 최대 중량은?모든 로프를 다 사용하지 않아도 된다. 풀이중량은 정확하게 w/k로 나눔으로 k개의 로프에 대해 최대로 들 수 있는 무게는 k중 가장 적게 들 수 있는 중량 x k 이다.로프의 길이에 대해 내림차순으로 정렬한 뒤각 로프가 추가될 때마다 들 수 있는 최대 중량을 저장한다.1 dp ? 코드 설계작은 로프에 대해 로프가 들 수 있는 무게가 달라지므로 내림차순으로 정렬한..
[Python] 프로그래머스 lv.2 조이스틱 https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 분석최소한으로 조이스틱을 움직여서 주어진 알파벳을 만들 때, 움직인 횟수 return맨 처음에는 주어진 알파벳의 글자 수만큼 A로만 이루어져 있다. 코드 설계수정이 필요한 글자의 idx 확인 (최단 이동거리를 위해)이동 거리에 대한 최솟값알파벳 수정에 대한 최솟값 정답 코드실패def solution(name): ans = 0 init = list('A' * len(name)) modi_idx = [] # 수정이 필요한..
[Python] 백준 2212 센서 https://www.acmicpc.net/problem/2212 문제 분석도로 위 N개의 센서를 설치센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우려고 하는데 K의 집중국을 세울 수 있다.각 집중국은 센서의 수신 가능 영역을 조절할 수 있다.집중국의 수신 가능 영역 : 고속도로 상에서 연결된 구간으로 나타나게 된다.N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며집중국의 수신 가능 영역의 길이의 합을 최소화직선의 고속도로센서들은 직선 위의 한 기점인 원점으로부터 정수 거리의 위치에 놓여 있다.각 센서의 좌표는 정수 하나로 표현각 좌표 사이에 빈 칸 하나? 풀이어떻게 집중국의 수신 가능 영역의 길이의 합을 최소화할 수 있을까?가까운 센서들끼리 묶어서 집중국이 관리를 해야 수신 가..
[Python] 프로그래머스 lv. 0 분수의 덧셈 풀이[ 분자1, 분모1 ] + [ 분자2, 분모2 ] 라고 할 때분수의 합에서분자 = ( 분자1 * 분모2 ) + ( 분자2 * 분모1 )분모 = ( 분모1 * 분모2 )기약 분수로 나타내려면분자와 분모의 최대공약수로 분자, 분모를 나눠주면 된다. 정답 코드import mathdef solution(numer1, denom1, numer2, denom2): answer = [] # 분자 numer = numer1 * denom2 + numer2 * denom1 # 분모 denom = denom1 * denom2 # 최대공약수 n = math.gcd(numer, denom) answer = [numer//n, denom//n] retur..

티스토리툴바