목록분류 전체보기 (23)
free from
들어가기 11376 열혈강호2는 이분매칭 문제입니다. (이분매칭에 대한 설명은 잘 정리된 블로그 내용을 참고해주세요.) 11375 열혈강호1 문제에서 A그룹->B그룹 매칭이 1개가 아닌 최대 2개인 문제입니다. 각 직원(A그룹)은 최대 두 개의 일을 할 수 있으며 각각의 일(B그룹)은 1명만 담당할 수 있습니다. 위와 같은 조건에서 일을 최대한 많이해야합니다. 풀이 A그룹에서 2개의 일을 할 수 있는 노드로 표현하여 매칭하는 것보다 2개의 노드로 생각하는 것이 문제를 푸는 방법입니다. 아래 오른쪽 그림같이 표현을 하면 이분매칭의 기본 형태로 정리할 수 있기 때문입니다. 코드
들어가기 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 노드..