free from

들어가기 23253은 자료구조 중 스택에 대한 내용을 알고 있으면 쉽게 풀 수 있는 구현문제입니다. 책 더미에서 제일 위에 있는 한 권씩 꺼낼 수 있는 스택 구조입니다. 풀이 입력값이 N, M 이 먼저 주어집니다. 1

들어가기 3190 뱀 문제는 자료구조 문제입니다. Deque를 활용하면 쉽게 풀 수 있는 문제입니다. 문제에서 제시한 조건대로 시뮬레이션을 진행하면 됩니다. 문제 N은 뱀 문제의 N X N 격자판 크기를 나타냅니다. K는 사과의 개수를 나타내며 격자판에 사과를 표시해둡니다. L은 게임 시작 후 X 초 이후에 뱀의 방향을 변환할 정보 개수입니다. 뱀의 방향은 'L' , 'D'의 정보로 변환합니다. 'L' 일 경우 90도 반시계 방향 'D' 일 경우 90도 시계 방향 풀이 먼저 뱀이 움직이는 방향을 정리합니다. 위와 같이 뱀이 움직일 방향의 index를 두면 'L' / 'D'를 아래와 같이 표현할 수 있습니다. L = 현재 방향 - 1 D = 현재 방향 + 1 뱀 게임에서는 뱀의 머리와 꼬리의 위치를 추적하..

들어가기 17135. 캐슬 디펜스 문제는 삼성 코딩 테스트에 나오는 유형과 비슷한 문제입니다. 시뮬레이션 문제이기 때문에 예제를 활용하여 시뮬레이션을 돌려보고 나온 로직을 구현하는 것이 좋습니다. 또한 문제에서 제시하고 있는 조건들을 꼭 눈여겨봐야 합니다. 문제 게임은 N x M 격자판에서 진행됩니다. N + 1 줄에는 캐슬이 있습니다. 이 캐슬을 지키기 위해서 3명의 궁수를 배치합니다. D는 궁수가 적을 공격할 수 있는 사정거리를 뜻합니다. 게임은 턴 제로 진행됩니다. 한 턴 마다 적이 한줄씩 아래로 내려옵니다. 캐슬까지 내려온 적은 격자판에서 사라집니다. 캐슬을 지키기 위해서 궁수들은 한 턴 마다 하나의 적을 공격할 수 있습니다. 궁수가 공격할 때 D(사정거리) 안에 있는 적만 공격 가능하며 그 중 ..

들어가기 1865. 웜홀은 어떤 node에서 출발해서 출발점으로 다시 되돌아 왔을 때 비용이 음이 되는지를 체크하는 문제입니다. 최소 비용 또는 최단거리를 구하는 그래프 문제에서 자주 적용되는 벨만-포드 / 다익스트라 알고리즘이 있습니다. 1865.웜홀에는 웜홀이라는 음의 간선이 있기 때문에 벨만 포드 알고리즘을 적용하는 문제입니다. 벨만 포드 알고리즘은 잘 정리된 글을참고해주세요. 저는 예시를 활용하여 풀이하도록 하겠습니다. 풀이 문제의 입력 값을 정리해봅시다. 우선 N , M , W의 입력을 받습니다. N은 노드 / M은 간선 / W는 웜홀입니다 그리고 M 간선에 대한 입력을 받습니다. S와 E는 연결된 지점의 번호, T는 이 도로를 통해 이동하는데 걸리는 시간을 의미합니다. S와 E를 연결한다는 의..

들어가기 11404. 플로이드는 모든 노드간의 최단 거리을 구하는 문제입니다 시작과 도착이 같은 노드의 입력 값은 없으므로 Loop는 없습니다. 비용의 입력값이 자연수이므로 음수의 비용도 없습니다. 그러므로 제목 그대로 플로이드 와샬 알고리즘으로 푸는 문제입니다. 플로이드-와샬 알고리즘 플로이드 와샬 알고리즘은 3중 for을 바탕으로 동작합니다. 노드 간의 최소 비용을 기록합니다. 최소 비용을 기록하여 재사용하기 때문에 DP입니다. 3중 for을 바탕으로 계산하기 때문에 복잡도는 O(n3)입니다. 아래는 기본이 되는 플로이드 - 와샬 코드입니다. 동일한 노드(i -> i)를 방문하는 경우, 노드 사이 간선이 없을 경우(여기서는 MAX_COST로 나타냈습니다)를 제외하면 i -> j의 노드 사이에 k 노드..

문제소개 벽 부수고 이동하기는 BFS 최단 거리 문제입니다. 상하좌우를 이동하면서 벽이 없으면 이동할 수 있으며 벽이 있을 때 망치( K > 0 )이면 벽을 부수고 이동할 수 있습니다. 벽을 부술 수 있는 망치가 있기 때문에 망치 사용 여부만 잘 확인해주시면 크게 어려운 문제는 아닙니다. 문제풀이 BFS 최단거리를 풀 때 활용되는 Priority Queue를 통해서 cost가 최소가 되는 Item을 우선적으로 처리합니다. BFS와 Priority Queue를 통해서 풀기 때문에 특정 x , y에 도달하게 되면 cost가 최소입니다. 한 가지 주의해야할 것은 망치의 사용 여부입니다. 'START'에서 '여기까지'로 갈 때 비용은 1번, 2번 경로 모두 3(START 포함)입니다. 하지만 바로 망치 사용 여..

문제소개 5021왕위 계승 문제는 dfs로 tree형태의 그래프를 형성하는 문제입니다. tree형태를 만든 다음 주어진 계승자를 계산하면 풀수 있는 문제입니다. 문제풀이 먼저 노드 구조체를 만들겠습니다. 트리의 노드 형태는 다음과 같습니다. struct node { string _name; vector _child; node(){} node(string name) { this->_name = name; } }; 각 트리의 노드를 정의했으니 트리를 만들겠습니다. 트리는 dfs로 구성할 것이며 제일 먼저 주어진 유토피아의 왕부터 시작합니다. void dfs(node& parent) { int j = 0; for (int i = 0; i < N; i++) { if (lines[i][1] == parent._n..

문제 소개 1756피자굽기 문제는 구현문제입니다. (DP로 풀수도 있습니다.) 반죽을 완료한 순서대로 오븐에 넣습니다. 이때, 반죽의 지름이 오븐의 지름보다 작거나 같을 때만 오븐에 넣을 수 있으며 가능한 가장 깊은 오븐에 반죽을 넣고 싶습니다. 피자반죽 입력 300,000 = 10^5 오븐 입력 300,00 = 10^5 이므로 이중 for문은 10^10의 크기를 가지므로 시간초과가 날 것입니다. 또한, 피자 반죽 지름과 오븐의 지름의 순서가 중요하기 때문에 정렬을 할 수 없습니다. 문제 풀이 7 3 5 6 4 3 6 2 3 //오븐 지름 3 2 5 // 피자 반죽 지름 위 예제를 가지고 예시를 들겠습니다. 먼저, 지름이 3인 첫번째 피자 반죽을 오븐의 가장 깊은 곳까지 넣을 수 있는 위치는 5번째 오븐..