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|$으로 주어지기 때문에 음수와 양수가 존재한다는 것을 알 수 있다. 따라서 `음수 책의 위치`와 `양수 책의 ..

https://www.acmicpc.net/problem/1253 난이도 : 골드 4 알고리즘 유형 : 이분탐색, 투포인터  풀이 시간 : 51분 문제 풀이 대락난 감;;; 했던 문제. 문제의 이해를 잘못해서 삽질을 엄청 한 문제이다. 처음 문제에 접근했을 때는, 해시맵을 사용해서 배열의 데이터들을 저장한 다음, 2중 반복문을 돌면서 해시맵에 키가 존재한다면, ans에 더해주려고 하였다. 하지만, 틀렸습니다. 를 받았고 이유를 찾아보다가 여러 상황이 있음을 깨달았다. 1. 입력되는 값의 크기는 오름차순으로 주어지지 않는다.2. 같은 입력값이 들어올 수 있다.3. 한 번 선택된 GOOD수(좋다)는 다시 선택되면 안된다.4. GOOD수를 만들 때는 선택된 나머지 두 수가 포함되면 안된다. 또한, $N ≤ 2..

https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 트리, 해시맵 풀이 시간 : 33분 문제 풀이 일단 문제가 꽤 길다. 문제를 읽어보면 어떤 직원이 판매한 칫솔의 수익에서 10%만큼 직원의 추천인(트리의 부모)에게 전달되고, 이 구조가 재귀적으로 반복되고 있음을 알 수 있다.문제를 풀며 주의해야 할 점은 수익을 나누는 방법인데, 돈을 받은 직원은 받은 돈의 10%를 추천인 직원에게 넘기고, 나머지를 자기가 갖게 되는 것이다. 다시 말해서 돈의 10%를..

https://www.acmicpc.net/problem/4485 난이도 : 골드 4 알고리즘 유형 : BFS , 다익스트라 풀이 시간 : 49분 문제 풀이 목적지까지 가는 데 뺏기는 루피의 최솟값을 구하는 문제이다. 처음에는 단순히 BFS 돌리면 되겠지 ~ 하고 룰루랄라 돌렸는데 아뿔싸 ! BFS를 돌리는 도중, 방문처리를 하게 되면 다른 노드에서 온 값에 대해 처리를 하지 못해 빼앗기는 최소 루피를 구할 수 없게 된다.따라서 나는 다익스트라 알고리즘을 사용해보았다. 다익스트라 알고리즘이란 ? 최단거리를 찾기 위한 알고리즘 중 하나이며, 현재 값과 가중치를 더해 새로운 값과 비교하고, 우선순위큐를 사용하므로 최단거리를 찾을 수 있다.  그런데, 우선순위큐를 구현하고, 실행하자 바로 시간초과가 뜨는 것이..

https://www.acmicpc.net/problem/2458 난이도 : 골드 4 알고리즘 유형 : 그래프탐색, BFS 풀이 시간 : 39분 문제 풀이 문제의 입력으로 주어지는 정보는 자신보다 키가 큰 사람의 정보이다. 또한, 이를 단방향 그래프로 연결할 수 있다. 문제에서 물어보고자 하는 것은 자신의 위치를 정확히 아는 사람의 수 이기 때문에, 한 정점에서 다음 정점의 개수와 이전 정점의 개수를 모두 알아야한다. 따라서 나는 정방향 그래프와 역방향 그래프를 생성하여, 각 정점에서 모두 BFS 탐색을 진행한 뒤, 모든 탐색이 끝나고 $현재 정점의 개수 == N - 1$인 경우의 개수를 체크하여 정답으로 출력하였다.그림으로 나타내면 다음과 같다. 코드/*두 학생의 키를 비교한 결과의 일부가 주어짐.N명..