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 배열에 저장할 수 없다. 따라서 우리는 무게를 낮은 순으로 오름차순 정렬한 뒤, 만들수 없는 최소 무게가 나올 때 반복문을 빠져나오는 그리디 알고리즘을 사용할 수 있다. 먼저 무게추 배열을 입력받고, 오름차순으로 정렬해주자..

https://www.acmicpc.net/problem/15686 난이도 : 골드 5 알고리즘 유형 : 브루트포스, 백트래킹  풀이 시간 : 23분 문제 풀이 치킨 ! 집 과 도시의 집들 사이 거리를 치킨거리라고 한다. 문제에서는 프렌차이즈 치킨 가게를 최대  M개만 남긴 상태에서 치킨거리를 최소로 하고 싶다. 주어진 범위를 확인해보면, $N ≤ 50, M ≤ 13$이다. 또한, 도시의 집 개수는 $2N$을 넘지 않기 떄문에, 최대 $100$개라고 할 수 있다. 따라서, $O(2^{13} * 13 * 100)$의 최악의 경우를 갖는다.이를 조금이나마 방지하기위해, 치킨집을 모두 뽑은 뒤, 치킨거리를 계산할 때, 현재 최소 치킨거리보다 값이 커진다면, 바로 return하는 방법을 추가하였다. 코드 작성 ..

https://school.programmers.co.kr/learn/courses/30/lessons/258705 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DP 풀이 시간 : 28분 문제 풀이 문제를 읽어보면, 이후에 계산하는 결과가 이전 결과에 영향을 미치지 않는 구조로 되어있다. 또한, $N ≤ 100000$으로 꽤나 큰 범위를 갖고 있다. 따라서 다음 문제는 DP로 접근을 할 수 있다.문제에서 생각해야 할 부분은 두 가지 경우가 존재한다. 위쪽에 삼각형이 있는 경우옆쪽 삼각형을 침범하는 경우여기서 옆 삼각형을 침범하지 않는 경우는 위쪽 삼각형이 있..

https://www.acmicpc.net/problem/1022 난이도 : 골드 3 알고리즘 유형 : 구현, 수학 풀이 시간 : 54분 문제 풀이 `(0, 0)`에서 시작하여 반시계 방향으로 소용돌이 도는 숫자 배열의 특정 부분을 출력하는 문제다.여기서 생각해야 할 부분이 있다면, 배열의 범위가 $-5000 ≤ r1, r2, c1, c2 ≤ 5000$이기 때문에 (0, 0)이 배열의 왼쪽 위가 아니다. 따라서 초기에 $r1, c1$ 좌표를 `(0, 0)`으로 맞춰줄 필요가 있다.// 초기 1 위치 잡아주기int r = -r1; int c = -c1;r2 += -r1 + 1; r1 = 0;c2 += -c1 + 1; c1 = 0; 이후, 배열 범위의 숫자가 다 채워질 때까지 while문을 돌려준다. 여기서..

https://www.acmicpc.net/problem/1461 난이도 : 골드 4 알고리즘 유형 : 그리디 풀이 시간 : 51분 문제 풀이 문제에서 체크해야 하는 부분은 다음과 같다. 1, 정리해야 하는 책의 위치는 0이고, 세준이의 출발 위치도 0이다.2. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 여기서 주의해야 할 부분은 2번인데, 가장 멀리 위치한 책에 대한 걸음 수는 0으로 돌아오지 않아도 되기 때문에 $*2$를 해주지 않아도 된다. 최솟값을 찾으라 했기 때문에 충분히 그리디 알고리즘으로 접근이 가능하다고 생각하였다. 우선 입력값이 $책의 위치 ≤ |10000|$으로 주어지기 때문에 음수와 양수가 존재한다는 것을 알 수 있다. 따라서 `음수 책의 위치`와 `양수 책의 ..