SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 난이도 : D4 알고리즘 유형 : 완전탐색 풀이 시간 : 24분 문제 풀이 숙소에는 다음과 같이 긴 복도가 있고, 방이 서로 마주보게 배치되어 있다. 모든 학생들은 현재 위치에서 자신의 방으로 돌아가려고 하는데, 만약 두 학생이 자기방으로 돌아가면서 지나는 복도의 구간이 겹치면 두 학생은 동시에 돌아갈 수 없다.이동하는데는 거리에 관계없이 1 단위시간이 걸린다. 이 문제에서 가장 중요하게 생각해야 할 부분은 방은 서로 마주보고 있는 것이다. 이동하는 데 거리와 상관없이 1 단위시간이 걸린다고 하였기 때문에, 문자는 간단히 완전탐색으로 풀어낼 수 있다. 우선, 복도 배..

SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 난이도 : D4 알고리즘 유형 : 완전탐색 풀이 시간 : 53분 문제 풀이 N개의 문제 중 틀리면 0점, 맞으면 배점만큼 점수를 받는다. 학생들이 받을 수 있는 점수의 경우의 수는 총 몇 가지인지 구하는 문제이다. 문제를 간단하게 생각해보면, 받을까 ? 받지 않을까 ? 에 대해서만 생각하면 된다. 하지만, 문제의 총 개수가 $N ≤ 100$이기 때문에, 단순히 완전 탐색을 사용한다면, $O(2^{100})$으로 시간초과가 나게 된다. 따라서, 점수를 하나씩 더해가며, 받을 수 있는 점수 배열에 추가한 다음, 중복되는 단어는 visited 배열을 통해 가지치기를 진행해..

https://www.acmicpc.net/problem/14658 난이도 : 골드 3 알고리즘 유형 : 브루트포스, 완전탐색 풀이 시간 : 1시간 3분 문제 풀이 욱제는 커다란 네모난 $L * L$ 크기의 트램펄린을 준비했다. 이 트램펄린을 사용하여 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 최소 개수를 구하자. 문제의 조건을 먼저 살펴보면, 지구의 크기를 나타내는 $0 ≤ N, M ≤ 500000$, 트램펄린의 크기를 나타내는 $1 ≤ L ≤ 100000$이 주어진다. 모든 지구를 탐색하는 방법을 사용한다면, 최악의 경우, $O(n^2)$로 시간초과가 날 것이다. 문제에서는 별똥별의 개수도 주어졌다($1 ≤ K ≤ 100$). 별똥별의 위치 정보를 활용한다면 조건 안에 문제를 해결할 ..

https://www.acmicpc.net/problem/1806 난이도 : 골드 4 알고리즘 유형 : 투 포인터 풀이 시간 : 24분 문제 풀이 길이 $N$인 수열에서 연속된 수들의 부분합 중에 그 합이 $S$ 이상이 되는 것 중 가장 짧은 길이를 구하자. 연속된 수들의 부분합을 구하는 문제이기 때문에, 정렬을 사용할 수 없다. 또한, 특정 구간이기 때문에 누적합을 사용할 수 없다. 따라서 본 문제는 투 포인터를 활용해 문제를 풀어나갈 수 있다. 먼저, 배열의 위치를 제공해줄 포인터 두 개 `left`, `right`를 생성하고, 수열의 0번 주소의 값으로 초기화를 진행해준다.이후, 반복문을 통해 배열을 순회할 것인데, while 문을 사용하여 `left` 인덱스 번호가 `right` 인덱스 번호보다 ..

https://www.acmicpc.net/problem/6087 난이도 : 골드 3 알고리즘 유형 : BFS, 다익스트라 풀이 시간 : 51분 문제 풀이 'C'로 표시된 두 칸을 레이저로 통신하기 위해 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성해야 한다. 거울은 '/' 혹은 '\' 두 개로 주어진다. 빈 칸은 ' . ', 벽은 ' * '로 주어진다. 문제 예시를 처음 보게 되면 바로 떠오르는 알고리즘은 너비우선탐색(BFS)이다. 하지만, 문제에서 요구하는 것이 통신을 위해 필요한 최단거리 가 아닌 "통신을 위한 거울의 최소 개수"이기 때문에, BFS 대신 우선순위 큐를 활용한 다익스트라 알고리즘을 활용할 수 있다. 먼저, 우선순위 큐에 저장하기 위한 구조체를 생성해주었고, 생성된 구조체..

https://www.acmicpc.net/problem/1202 난이도 : 골드 2 알고리즘 유형 : 그리디, 우선순위 큐풀이 시간 : 1시간 25분 문제 풀이 각 보석은 무게 $M_i$와 가격 $V_i$를 가지고 있고, 상근이는 무게가 $C_i$인 가방을 K개 가지고 있고, 이 가방에는 한 개의 보석만 담을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구해보자. 문제의 조건을 확인해보면 보석의 총 개수와 가방의 개수가 $1 ≤ N, K ≤ 300000$ 이고, 보석의 정보는 $1 ≤ M_i, V_i ≤ 1000000$이다.  먼저 베낭 문제처럼 각 보석의 개수와 가방의 총 개수에 대한 완전 탐색을 진행하게 되면 $300000 * 300000$으로 무조건 시간초과가 난다. 따라서, 우리는 그리..

https://www.acmicpc.net/problem/16197 난이도 : 골드 4 알고리즘 유형 : 시뮬레이션, 재귀풀이 시간 : 36분 문제 풀이 두 동전은 상하좌우로 이동이 가능하고, 두 동전은 항상 같은 방향으로 이동한다. 단, 새로운 좌표가 벽이라면 이동이 불가능하다. 동전이 한 개만 남기 위한 최소 이동 횟수는 몇 번인지 구해보자.  먼저, 좌표의 범위를 확인해본다면, $0 ≤ N, M ≤ 20$으로, 재귀함수로 충분히 접근이 가능해 보인다. 또한, 문제의 마지막 조건을 확인해보면, "버튼을 10번보다 많이 눌러야 한다면, -1을 출력한다." 라는 내용이 존재하기 때문에, 시간초과는 신경쓰지 않고 문제에 접근이 가능하다. 시간복잡도를 계산해본다면, 재귀적으로 최대 10번 들어갈 수 있기 때..

https://www.acmicpc.net/problem/1781 난이도 : 골드 2 알고리즘 유형 : 그리디, 힙  풀이 시간 : 1시간 2분 문제 풀이 데드라인 내에 각 문제를 풀어 얻을 수 있는 컵라면 수의 최대를 구하는 문제이다. 본 문제의 예시를 본다면, 다음과 같다.문제 번호1234567데드라인1133226컵라면 수6721451이 예시에서는, 단순히 데드라인 별 오름차순을 진행하고, 컵라면 수에 대해 내림차순을 진행하여 문제를 해결할 수 있다. 하지만 다음 예시를 살펴보자.문제 번호1234데드라인1233컵라면 수111010이 예시를 보면, 데드라인 순으로 오름차순을 진행하는 것은 의미가 없어보인다. 따라서 이 문제는 힙을 사용하여 문제를 풀어나갈 수 있다. 간단하게 생각해보자. 하나의 문제를 ..

https://school.programmers.co.kr/learn/courses/30/lessons/92343  프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3 알고리즘 유형 : DFS, BFS 풀이 시간 : 43분 문제 풀이 이진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여있다. 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 한다. 만약 늑대를 만나면 늑대가 양을 따라다니게 되고, 늑대의 수가 양의 수보다 같거나 큰 경우 모든 양을 잡아먹는다. 최대한 많은 양을 모으자. 문제는 이진 트리 형식으로 되있고, DFS와 BFS 모두 사용가능하다. 다만, 이..

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