본문 바로가기
반응형

알고리즘/프로그래머스

 (22)
[Python] 블록 이동하기 https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 1. 이해하기 (1,1)에서 시작하여 (N,N)에 도착하는데 걸리는 최소 시간을 구해야 한다. 로봇은 두 칸을 차지한다. 로봇은 회전과 이동이 가능하다. 회전 시 조건에 맞아야 회전이 가능하다. 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어진다. 2. 구현하기 걸리는 최소 시간을 구하기 위해서는 BFS를 이용하여 구현이 가능하다. 그 이유는 회전, 이동 모두 가중치가 1이기 때문..
[프로그래머스] 숫자 게임 숫자 게임(https://programmers.co.kr/learn/courses/30/lessons/12987) 1. 이해하기 숫자가 큰 쪽이 승리하게 된다. A팀의 출전 순서가 정해져 있을 때, B팀의 최대 승점. 큐를 이용하여 구한다. 2. 구현하기 이 문제를 푸는 아이디어는 다음과 같다. B에 있는 가장 작은 수부터 A의 가장 작은 수와 비교를 한다. 만약 B의 수가 A의 수보다 크면 answer++를 하고 두 수를 큐에서 지운다. 만약 B의 수가 A의 수보다 작다면 B의 수만 큐에서 지운다. Python from collections import deque def solution(A, B): answer = 0 A.sort() B.sort() aQ = deque() bQ = deque() for..
[프로그래머스] 기지국 설치 기지국 설치(https://programmers.co.kr/learn/courses/30/lessons/12979) 1. 이해하기 기존에 기지국이 설치되어 있는 곳도 있고 없는 곳도 있다. 기지국이 설치되어 있는 곳은 w만큼의 지역을 커버한다. 최소의 기지국을 설치하고 모든 아파트에 전파를 전달하려고 한다. 2. 구현하기 기지국이 설치되어 있지 않은 지역의 시작을 start, 기지국이 설치되어있는 곳의 위치를 location이라고 한다면 기지국이 설치되고 전파가 전달되는 곳 중 왼쪽 l은 location-w-1이다. 이 때, 전파가 전달되지 않는 지역의 거리 len은 l-start+1이다. 이를 이용하면 이 구간에 몇개의 기지국을 설치해야하는지 알 수 있다. len/(w*2+1)을 통해 기지국이 몇개가 ..
[프로그래머스] 배달 배달(https://programmers.co.kr/learn/courses/30/lessons/12978) 1. 이해하기 각 마을은 양방향으로 통행할 수 있는 도로가 있다. 각 도로를 지날 때 걸리는 시간은 도로별로 다르다. 배달은 1번 마을에 있는 음식점에서 각 마을로 음식배달을 한다. K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 한다. 최단거리 문제. 2. 구현하기 1번에서 시작하는 다익스트라 구현을 통해서 각 마을마다 최단거리를 구한다. Python dijkstra(road,N): 우선순위 큐를 이용해서 다익스트라를 구현한다. 어느 지점과 이어져있는지를 알기 위하여 road를 받고 각 마을마다 거리를 초기화하기 위해서 N을 받는다. 이후 반복문을 이용하여 각 지점의 최단거리를 갱신해준..
[프로그래머스] 야근 지수 야근 지수(https://programmers.co.kr/learn/courses/30/lessons/12927) 1. 이해하기 N시간 동안 야근 피로도를 최소화하도록 일하려고 한다. Demi는 1시간 동안 작업량 1만큼을 처리할 수 있다고 한다. n의 범위와 works의 배열의 길이가 크기 때문에 일반적으로 해서는 시간초과가 나게 된다. heap혹은 binary_search를 이용해서 최댓값을 찾는다. 최댓값을 찾는 이유는 큰 값일수록 제곱의 값이 커지기 때문이다. 2. 구현하기 만약 works에 있는 양이 n값보다 작으면 0을 리턴해준다. 시간안에 모든 일을 처리할 수 있고 야근을 하지 않아도 되는 상황이기 때문이다. heap에 works의 값들을 넣어준다. 이후 n이 0이 될 때까지 최댓값을 찾아서..
[프로그래머스] 방문 길이 방문 길이(https://programmers.co.kr/learn/courses/30/lessons/49994) 1. 이해하기 게임 캐릭터를 4가지 명령어를 통해서 움직인다. U: 위쪽으로 한 칸 D: 아래쪽으로 한 칸 R: 오른쪽으로 한 칸 L: 왼쪽으로 한 칸 캐릭터를 0,0에서 시작하고 경계가 주어진다. 경계에서 벗어난 움직임을 할 경우 명령어를 무시한다. 캐릭터가 처음 걸어본 길의 길이를 구한다. 거쳐간 길을 갈 경우 길이에 포함시키지 않는다. 2. 구현하기 경계에서 벗어난 움직임을 할 경우에는 명령어를 무시한다. 맨 왼쪽 아래를 0,0으로 설정하고 맨 오른쪽 위를 10,10으로 잡는다. Python def out_bound(x,y): return x 10 or y < 0 o..
[프로그래머스] 등굣길 등굣길 1. 이해하기 물에 잠기지 않은 지역을 통해 학교를 가려고 한다. 집에서 학교까지 갈 수 있는 최단 경로의 개수를 1000000007로 나눈 나머지를 반환해야한다. DP문제이다. 2. 구현하기 dfs(x,y,d,m,n,map): 현재 위치 x,y, 온 방향 d를 가지고 map크기가 nxm이다. 현재 위치: x,y, 온 방향: d를 모두 가지고 dp에 저장해야 한다. 그렇지 않으면 dp를 더해주는 부분에서 의도치 않은 값이 더해지게 된다. x,y가 가는 방향에 대해서 문제를 풀어주면 된다. int dfs(int x, int y, int d, int m, int n, vector& map) { if(x >= n or y >= m) return 0; if(map[x][y] == 1) return 0; ..
[프로그래머스] 여행경로 여행경로 1. 이해하기 주어진 항공권을 모두 이용하여 여행경로를 짜려고 한다. 항상 "ICN" 공항에서 출발한다. 방문하는 공항 경로를 배열에 담아 출력한다. dfs문제이다. 2. 구현하기 dfs(here,tickets,visited,tmp,answer,cnt): 현재 위치에서 tickets들을 살펴보면서 출발지가 현재위치이고 아직 방문하지 않은 곳을 방문한다. 이때 방문한다면 cnt를 1 증가시킨다. cnt가 모든 티켓의 수와 같다면 answer에 경로가 담긴 tmp값을 answer에 넣어주고 true를 반환한다. bool dfs(string here, vector& tickets, vector& visited, vector& tmp, vector& answer, int cnt) { tmp.push_b..

티스토리툴바