https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 이분탐색, 매개변수탐색풀이 시간 : 24분 문제 풀이 - 징검다리는 일렬로 놓여있고, 디딤돌을 한 번 밟을 때마다 내구도가 1씩 깎인다.- 내구도가 0이 되면 더이상 밟을 수 없으며, 이때는 그 다음 디딤돌로 여러칸을 건너 뛸 수 있다.니니즈 친구들의 수는 무제한이라는 가정 하에 최대한 많이 건널 수 있는 니니즈 친구들의 수를 return하자. 문제의 입력 변수 범위를 살펴보면, $stones의 배열 ..

https://school.programmers.co.kr/learn/courses/30/lessons/150365# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DFS, BFS 풀이 시간 : 32분 문제 풀이 총 k번 이동하여 미로를 탈출할 수 있는 문자열 경로 중 사전 순으로 가장 빠른 경로를 출력하는 문제이다. 문제의 조건 중 이때, (x, y)와 (r, c)격자를 포함해, 같은 격자를 두 번 이상 방문해도 됩니다. 라는 조건이 있다. 이를 통해 같은 격자를 중복해서 방문해도 된다는 것으로 확인할 수 있다. 우리는 최단경로를 찾기 위해 DFS, BFS ..

https://school.programmers.co.kr/learn/courses/30/lessons/340211# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 2 알고리즘 유형 : 구현, 시뮬레이션 풀이 시간 : 44분 문제 풀이 물류 센터에는 N개의 포인트가 존재한다. 또한, 로봇마다 정해진 운송 경로를 통해 시작 포인트부터 마지막 포인트까지 이동해야 한다. 로봇은 1초에 한 칸씩 움직일 수 있고, 모든 로봇이 동시에 움직인다. 움직이는 과정 중 로봇의 좌표가 중복되는 경우의 수를 구하자. 먼저, 로봇의 움직임 조건은 다음과 같다.  1. 최단경로로 이동. 우선순위는 r이 ..

https://school.programmers.co.kr/learn/courses/30/lessons/340212 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 2 알고리즘 유형 : 이분탐색 풀이 시간 : 38분 문제 풀이 제한시간 내 퍼즐을 모두 풀기 위한 숙련도(level)의 최솟값을 구하는 문제이다. 문제의 조건을 살펴보면, `diffs[i] ≤ level`인 경우, `times[i]`만큼의 시간을 사용하여 문제를 해결하고, `diffs[i] > level`인 경우에는 `(diffs[i] - level) x (times[i] + times[i - 1]) + times[i]`..

https://www.acmicpc.net/problem/11657 난이도 : 골드 4 알고리즘 유형 : 벨만포드 풀이 시간 : 19분 문제 풀이 문제의 주 목적은 1번 정점에서 나머지 모든 정점을 가는 데 걸리는 시간을 구하는 문제이다. 그치만 문제에서 음수 사이클이 존재하기 때문에, 우리는 다익스트라 알고리즘 대신 벨만포드 알고리즘을 사용할 것이다. 벨만포드 알고리즘이란 ? 모든 정점과 엣지를 탐색하여 최소 거리로 업데이트해주기 위한 알고리즘이다. 다익스트라 알고리즘과 차이점이라면, 다익스트라 알고리즘은 최소 거리를 찾기 위해 그리디하게 값을 업데이트하지만, 벨만포드 알고리즘은 모든 정점과 간선을 다 방문해본다는 점이다. 다익스트라 알고리즘의 시간복잡도는 $O(V + E)$이고, 벨만포드 알고리즘의 ..

https://school.programmers.co.kr/learn/courses/30/lessons/150368#  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 2 알고리즘 유형 : 완전탐색, 조합 풀이 시간 : 41분 문제 풀이 이모티콘 할인행사의 목표 우선순위는 다음과 같다.서비스 가입자 최대판매액 최대카카오톡 사용자들은 자신의 기준이 되는 일정 할인율 이상 할인하는 이모티콘들을 모두 구매한다. 만약, 이모티콘을 구매하는 비용이 사용자의 최대 예산을 넘어간다면 사용자는 이모티콘 서비스를 가입한다. 문제를 보면 매우 복잡하고, 완전탐색 진행 시 시간초과가 발생할 것 같지만 ..

https://www.acmicpc.net/problem/1446 난이도 : 실버 1 알고리즘 유형 : DP 풀이 시간 : 18분 문제 풀이 D킬로미터 길이의 고속도로를 지나는 데 운전해야하는 거리의 최솟값을 출력하는 문제이다. 고속도로를 지나는 데에는 몇 개의 지름길이 존재한다. 그 지름길을 활용하면 최소한의 거리로 D킬로미터의 고속도로를 통과할 수 있다. 문제에서 모든 지름길은 일방통행이고, 고속도로는 역주행할 수 없다고 하였다. 여기서 우리는 현재 계산한 결과가 이전 결과에 영향을 미치지 않는다는 것을 파악할 수 있다. 또한, 최솟값을 출력하라고 하였으므로, 우리는 무난하게 Bottom-Up 방식의 DP 알고리즘을 활용할 수 있다. 문제를 풀며 주의해야 할 부분은, 지름길의 출발지 도착지가 중복될 ..

https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 완전탐색 풀이 시간 : 42분 문제 풀이 처음 문제를 보고, 모든 조합을 생각해야 한다는 사실에 머리가 매우 아팠다. 그래서, 완전탐색으로 풀 경우 시간초과가 나지 않을까? 를 걱정하며 시간복잡도를 계산해보았다. 먼저, 주사위 중 절반을 고르는 경우부터 계산해보도록 하자.$N ≤ 10$이므로 최대 경우의 수는 $10C5 = 252$가 된다. 또한, 주사위 중 6면을 5번 뽑는 경우가 최악이 되므로, ..

https://www.acmicpc.net/problem/2169 난이도 : 골드 2 알고리즘 유형 : DP 풀이 시간 : 42분 문제 풀이 로봇은 두 가지 이동 조건을 갖고 있다.아래, 왼쪽, 오른쪽 방향으로만 갈 수 있다.한 번 방문한 곳은 다시 방문하지 않는다.문제를 마주하고 가장 처음 생각할 수 있는 알고리즘은 그래프 탐색(BFS / DFS)이다. 하지만, N과 M의 범위가 $0 ≤ N, M ≤ 1000$이기 때문에 DFS로 접근할 경우, 시간초과가 발생하게 되고 BFS로 접근할 경우, 최댓값을 찾기에는 힘들다. 문제를 다시 한 번 생각해보면, 위쪽 방향으로는 갈 수 없다고 한다. 다시말해, 이전 결과를 생각하지 않는다는 것이고, 이는 즉 DP로 해결이 가능하다는 소리이다. 아래로 이동할 때, 우..

https://www.acmicpc.net/problem/2437 난이도 : 골드 2 알고리즘 유형 : 정렬, 그리디 풀이 시간 : 49분 문제 풀이 주어진 무게추를 사용하여 만들 수 없는 무게 중 가장 작은 값을 출력하는 문제이다.본 문제를 처음 마주할 때 생각할 수 있는 알고리즘은 그리디, DP 가 있다. 하지만 주어진 범위를 잘 살펴보면 $N ≤ 1000, 각 무게추의 무게 ≤ 1000000$이기 때문에 입력으로 $1000000$의 무게가 $1000$개 들어오는 경우 1차원 DP 배열에 저장할 수 없다. 따라서 우리는 무게를 낮은 순으로 오름차순 정렬한 뒤, 만들수 없는 최소 무게가 나올 때 반복문을 빠져나오는 그리디 알고리즘을 사용할 수 있다. 먼저 무게추 배열을 입력받고, 오름차순으로 정렬해주자..