프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : BFS 풀이 시간 : 17분 문제 풀이 각 부대원들이 여러 지역에서 임무를 수행중이다. 임무가 끝나고 부대로 복귀하는데 걸리는 최단 시간을 부대원 별로 구해서 출력하자.  문제의 제한사항을 확인해보면 꽤나 빠듯하다. 먼저, [전체 정점 ≤ $100000$], [간선(roads)의 개수 ≤ $500000$], [병사의 수 ≤ $500$] 으로 주어졌기 때문에, 각 부대원 별로 한 명 씩 최단거리를 찾아주게 된다면 $O(500 * (100000 + 500000))$으로 시간이 오래 걸리게 된다. 따라서, 부대원 별로 ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 누적합 풀이 시간 : 1시간 30분 문제 풀이 문제의 설명 자체는 간단하다. N x M 크기의 행렬 모양의 게임 맵에는 내구도를 가진 건물이 각 칸마다 존재하는데, 두 개의 스킬(파괴, 회복)을 사용하여 특정 구간의 건물에 적용한 뒤, 내구도가 0 이상인 건물의 개수를 return하는 것이다. 하지만 큰 문제는 각 입력의 범위에 존재한다.먼저 행렬의 범위는 $N, M ≤ 1000$ 이고, $skill 의 개수(K) ≤ 250000$이기 때문에, 완전탐색으로 문제를 풀어나갈 경우에 최악의 경우, $O(N * M * ..

삼성 SW 역량테스트 2024 하반기 오후 1번 문제 Code Tree | Learning to Code with ConfidenceA super-comprehensive, meticulously arranged Coding Learning Curriculum engineered by Algorithm Experts composed of former International Olympiad in Informatics (IOI) medalists.www.codetree.ai 알고리즘 유형 : 구현, 시뮬레이션, BFS 풀이 시간 : 3시간 12분 문제 풀이 --문제 설명의 경우 생략하겠습니다-- 해당 문제는 총 4가지 동작의 반복으로 나눌 수 있다.1. 메두사 이동2. 메두사의 최적의 시야각 찾기3. 전사..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DP 풀이 시간 : 1시간 15분 문제 풀이 어떤 풍선이 최후까지 남아있는지 알아보고싶다. 풍선을 터트릴 수 있는 조건은 다음과 같다.1. 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트림 2. 풍선들 사이 빈 공간이 있다면, 중앙으로 밀착시킨다.최후까지 남기는 것이 가능한 풍선들의 개수를 return하자. 먼저 입력 배열의 길이를 확인해보면 $a ≤ 1000000$으로 주어지기 때문에 백트래킹, 완전탐색으로 접근할 경우 시간초과가 발생한다. 또한, 정렬을 할 수 없기 때문에 그리디로 문제를 해결하기도 어려워..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 :  Level 3 알고리즘 유형 : DP 풀이 시간 : 1시간 8분 문제 풀이 보행자 중심의 경로 탐색 알고리즘을 구현하려고 한다. - `city_map[i][j] == 0` 인 경우에는 자동차가 자유롭게 지나갈 수 있다.- `city_map[i][j] == 1` 인 경우에는 자동차의 통행이 금지된다.- `city_map[i][j] == 2` 인 경우에는 가던 방향으로만 이동할 수 있다.자동차는 오른쪽 또는 아래 방향으로만 이동이 가능하다. 가능한 이동 경로의 개수를 구하자. 해당 문제는 가능한 경로의 총 개수를 구하는 것이 중점이고, 입력 gri..

https://www.acmicpc.net/problem/2342 난이도 : 골드 3 알고리즘 유형 : DP 풀이 시간 : 51분 문제 풀이 DDR의 입력이 지시 사항으로 주어질 때, 승환이가 사용하는 최소 힘을 출력하라. DDR을 하는 데 사용되는 힘은 다음과 같다.중앙 -> 다른 지점 : 2 인접 지점 (왼쪽 -> 위 / 아래) : 3 반대편 (왼쪽 -> 오른쪽) : 4 해당 문제를 마주하면 그리디로 문제를 해결해야 할 지, DP로 문제를 해결해야 할 지 머리가 매우 뜨거워진다. 이럴 땐, 각 알고리즘의 정의를 다시 한 번 떠올리자.그리디 알고리즘의 경우, 항상 최적의 값을 갖는 경우로만 이동하고자 하는 알고리즘이다.DP의 경우, 이전 결과가 현재 결과에 영향을 미치지 않고, 단순히 이전 결과를 사용..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : 그리디, 정렬 풀이 시간 : 20분 문제 풀이 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치할 때, 최소 몇 대의 카메라가 필요한지 구하여라. 문제의 입출력 예제가 매우 친절하게 설명해주고 있다.routesreturn[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]2해당 예제를 그림으로 나타내 확인해보면 다음과 같다.해당 예제의 결과를 살펴보면, -15 지점에서 첫번째, 세번째 차량이 카메라를 만나고, -5 지점에서 두번째, 네번째 차..

https://www.acmicpc.net/problem/4811 난이도 : 골드 5 알고리즘 유형 : DP 풀이 시간 : 29분 문제 풀이 종수 할아버지는 매일 약 반 알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.종수는 2N일동안 약을 먹을 수 있는데, 약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다. 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H를 보낸다. 총 2N일이 지난 뒤, 만들어질 수 있는 서로 다른 문자열의 개수를 구하여라 해당 문제는 경우의 수를 구하는 문제이다. 문제를 읽어보면 알약 한 개를 꺼내서 먹거나, 반 개를 꺼내서 먹거나의 경우가 존재한다. 또한, 문자열의 개수를 구하는 문제이기 때문에, 굳이 문자열..

https://www.acmicpc.net/problem/1406 난이도 : 실버 2 알고리즘 유형 : 자료구조, 덱  풀이 시간 : 17분 문제 풀이 에디터를 구현하려고 한다. 에디터에는 커서가 존재하는데, 각 명령어에 따라 문장을 수정할 수 있다. 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하자.L커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)B커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임P $$라는 문자를 커서 왼쪽에 추가함 문제를 읽고 바로 생각날 수 있는 알고리즘은 단..

https://www.acmicpc.net/problem/2573 난이도 : 골드 4 알고리즘 유형 : 구현, BFS 풀이 시간 : 32분 문제 풀이 빙산의 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하자. 문제는 매 해마다 두가지 동작을 반복한다.1. 빙산이 두 덩어리로 분리되었는지 체크(BFS)2. 빙산의 녹는 정도 계산(구현) 먼저, 빙산이 두 덩어리로 분리되었는지 체크하기 위해서는 BFS를 사용할 것이다. 빙산이 아직 떨어지지 않았다면 BFS는 한 번만 실행하고 끝날 것이다. 하지만, 만약 BFS를 한 번 실행했는데도 불구하고 또다른 BFS..