문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는..
인접 행렬 : 2차원 배열로 그래피의 연결로 표현하는 방식 public class AdjacencyMatrix { public static int INF = Integer.MAX_VALUE; public static List graph = new ArrayList(); public static void input() { // INF는 이동이 불가능한 경우를 뜻한다. graph.add(Arrays.asList(0, 7, 5)); graph.add(Arrays.asList(7, 0, INF)); graph.add(Arrays.asList(5, INF, 0)); } public static void print() { input(); System.out.println(graph); } public static ..
dfs와 bfs는 역할은 비슷하지만 그 표현방법이 다릅니다. 대표적으로 dfs는 스택으로 표현하고 bfs는 큐로 표현을 합니다. bfs와 dfs를 들어가기에 앞서 스택과 큐를 간단하게 알아보겠습니다. 스택 : push(), pop() 으로 데이터를 넣고 뺍니다. 즉, 박스 쌓기와 비슷합니다. 하지만 프로그래밍의 특이성 때문에 실제처럼 구현하기는 어렵습니다. 그래서 하얀게 박스이고 노란게 pop, 초록색이 push라 생각했습니다. 즉, 스택은 한쪽에서 pop과 push가 진행이 된다는 것을 알 수 있었습니다. 또, 스택은 선입 후출입니다. 그러면 큐는 어떨까요? 큐 : append(), pop() 스택과 마찬가지로 위의 명령어로 데이터를 넣고 빼는 형식입니다. (언어마다 조금씩 다른것 같군요.) 아무튼 큐..
데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열..
현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각칸은 (A,B)로 나타낼 수 있고, A는 북쪽으로 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위한 메뉴얼은 다음과 같다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 수 있다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한칸을 전진한다. ..
피지컬로 승부하자! - 프로그래밍 언어를 정확히 알고 있어야 하며, 문제의 요구사항에 어긋나지 않는 답안 코드를 실수 없이 작성해야 한 다 - 구현 유형의 문제는 풀이는 떠올리기 쉽지만, 소스코드로 옮기기 어려운 문제'를 의미한다. - 이러한 유형들은 알고리즘을 설계했는데 구현이 먼저 풀 수 있는 문제가 없을 때 푸는 게 좋다'라고 설명했다. - 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제 - 특정 소수점 자리까지 출력하는 문제 - 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등 완전 탐색 - 모든 경우의 수를 주저없이 다 계산하는 방법 시뮬레이션 - 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 메모리 제약! 구현 문제에 접근 하는 방법 - 보통..
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..
문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다. 이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오. 입력 첫째 줄..
문제 병든 나이트가 N × M 크기 체스판의 가장 왼쪽아래 칸에 위치해 있다. 병든 나이트는 건강한 보통 체스의 나이트와 다르게 4가지로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 병든 나이트는 여행을 시작하려고 하고, 여행을 하면서 방문한 칸의 수를 최대로 하려고 한다. 병든 나이트의 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다. 이동 횟수가 4번보다 적은 경우(방문한 칸이 5개 미만)에는 이동 방법에 대한 제약이 없다. 체스판의 크기가 주어졌을 때, 병든 나이트가 여행에서 방문할 수 있는 칸의 최대 개수를 구해보자. 입력 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 ..
문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. 입력 N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다. 출력 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라. 접근 방법 : - int나 long long 이 아닌 string으로 숫자를 받았다. (숫자가 커질 수 있으니까) - 30도 따지고 보면 3의 배수이기 때문에 3의 배수의 특징을 알아야한다. - 인터넷에서 찾아본 결과 3의 배수는..
- 이름에서 알 수 있듯이 Greedy는 단순, 무식하게 탐욕적으로 푸는 알고리즘이다. 하지만 단순, 무식하게 푼다는것은 생각보다 쉽지 않다. 여기서 무식하게 푼다는 의미는 예를 들어 우리가 여러 지폐들중 하나만 가질 수 있다고 한다면, (무조건 한 장만 가능하다.) 가장 값어치가 가장 큰 지폐를 선택하게 된다. 이것은 어쩔 수 없다. 이런게 그리디인데 코딩 테스트에서는 단순하게 문제가 나오지는 않는다. 그리디가 사전에 외우지 않고 있어도 풀 수 있는 가능성이 높은 유형이라고는 하지만, 다른 유형과 함께 등장하는 경우도 많다고 한다. 예를 들어, 정렬알고리즘과 함께 사용하던가, 최단경로를 구하는 알고리즘과 함께 사용한다고 할때 이들을 미리 알고 있지 않으면 문제를 풀지 못하는 상황이 발생할지도 모른다. ..
영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다. 왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데, 그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다. 개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다. (오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.) 이에 호기심이 생긴 영일이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다. 미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지 오른쪽 또는 아래쪽으로만 움직였다. 미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고, 먹이가 2로 주어질 때, 성실한 개미의 이동 경로를 예상해보자. 단, 맨 아래의 가장 오른쪽에 도착한 경우,..