https://www.acmicpc.net/problem/16472 난이도 : 골드 4 알고리즘 유형 : 투포인터  풀이 시간 : 19분 문제 풀이 고양이는 너무 귀엽다 !고양이 말 번역기는 최대 n개 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 이 번역기로 인식할 수 있는 최대 문자열의 길이를 구해보자. 우선 이 문제는 투포인터 알고리즘을 생각해낼 수 있다. 문자열의 시작위치와 종료위치를 저장해둠으로써 문자열의 최대 길이를 구할 수 있기 때문이다. 어떤 문자열이 인식되었는지를 파악하기 위해서는 다양한 자료구조를 사용할 수 있지만, 본인은 파이썬의 딕셔너리를 사용하여 정보를 관리해주었다. 문제풀이구상은 다음과 같다.  1. 먼저, 시작위치와 종료 위치 인덱스를 0으로 초기화한다.2. for ..

https://www.acmicpc.net/problem/3273 난이도 : 실버 3 알고리즘 유형 : 투포인터, 정렬 풀이 시간 : 12분 문제 풀이 구하고자 하는 자연수 $x$가 주어졌을 때, 수열의 $a_{i} + a_{j} = x$를 만족하는 수열 쌍의 개수를 구해보는 문제이다. 수열의 크기를 먼저 확인해보면, $n ≤ 100000$으로 주어졌다. 따라서, 조합을 완전탐색으로 풀어본다면, $O(10000C2)$로 약 50억이기 때문에 시간초과가 발생한다.  따라서, 우리는 투포인터 개념을 활용해 이를 해결할 수 있다.투포인터란, 두 개의 인덱스 번호를 통해 한 배열에서 원하는 수를 접근하기 위한 방법론으로, 1차원 배열의 경우 $O(n)$의 시간복잡도로 문제를 해결할 수 있다. 먼저, 투포인터 사..

https://www.acmicpc.net/problem/1520 난이도 : 골드 3 알고리즘 유형 : DFS, DP 풀이 시간 : 33분 문제 풀이 $(0, 0)$ 부터 $(N - 1, M - 1)$까지 가기 위한 경우의 수를 구하자. 단, 이동 시에는 이전 높이보다 항상 낮은 곳으로만 이동해야 한다. 문제의 조건을 살펴본다면, $N, M ≤ 500$으로 주어졌고, 상하좌우로 이동이 가능하기 때문에, 모든 경우에 대해 살펴본다면 $O(4^{500})$으로 시간초과가 나게 된다. 따라서 우리는 DP 테이블을 활용하여 이전에 왔던 경우의수에 대해서 저장해주어야 한다. 먼저 grid 상에서 이동은 dfs 알고리즘을 사용해 진행하였다. 기본적인 틀은 4방향에 대해 탐색하면서, 현재 위치보다 새로운 위치가 낮은..

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 알고리즘을 활용할 수 있다. 문제를 풀며 주의해야 할 부분은, 지름길의 출발지 도착지가 중복될 ..