free from

들어가기 14626 ISBN은 모듈로 연산 문제입니다. ISBN는 모듈러 연산의 규칙을 따르는 13자리의 일련번호로 구성됩니다. 13자리 일련번호의 마지막 숫자는 앞에서부터 각 자리마다 가중치 1, 3, 1, 3…. 를 곱한 것을 모두 더하고, 그 값을 10으로 나눈 나머지가 0이 되도록 만드는 숫자로 정의합니다. 아래 예시는 13자리의 마지막 숫자 m의 계산 과정입니다. 978896832227[m] 10 - (1*9 + 3*7 + 1*8 + 3*8 + 1*9 + 3*6 + 1*8 + 3*3 + 1*2 + 3*2 + 1*2 + 3*7)%10 = m 10 - 137%10 = m 10 - 7 = 3 문제의 요구사항은 마지막 숫자를 제외한 1~12자리 일련번호 중 손상된 1개의 일련번호를 복구하는 것입니다. ..

들어가기 2909 캔디 구매는 간단한 수학 문제입니다. 상근이는 늘 한 종류의 지폐를 들고 다닙니다. (1, 10, 100, 1000, ..., 1,000,000,000) 한 종류의 지폐를 좋아하기 때문에 계산도 거스름돈을 받지않고 딱 맞아 떨어지면 좋겠습니다. 사탕 가게 주인은 캔디 가격을 반올림하여 상근이의 지폐 단위에 맞아 떨어지도록 가격을 책정합니다. 사탕 가게를 도와 상근이가 돈을 지불할 수 있도록 하는 문제입니다. 예를 들어 사탕가격: 123450995 / 지폐의 0의 개수가 1일때 반올림된 가격은 123451000입니다. intput: 123450995 1 output: 123451000 풀이 반올림되는 자리수를 구하는 것으로 문제를 풀수 있습니다. 123450995 / 10 => 12345..

들어가기 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 포함)입니다. 하지만 바로 망치 사용 여..