꺼내먹는지식 준

문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는..

문제 요약 자물쇠와 열쇠 특이한 형태의 자물쇠와 열쇠가 있다. 잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1 인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있다. 자물쇠에는 홈이 파져있고 열쇠 또한 홈과 돌기 부분이 있다. 열쇠는 회전과 이동이 가능하며, 열쇠 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열린다. 자물쇠 영역을 벗어난 부분에 있는 열쇠와 홈의 돌기는 자물쇠를 여는데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기부분과 자물쇠의 홈 부분이 정확히 일치해야하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안 된다. 자물쇠 모든 홈을 채워 비워있는 곳이 없어야 한다. 아이디어 회전 행렬 에대한 개념이 필요하다. 2D..

문자열 압축 한번 풀었던 문제라 간단하게 해결하고 싶었으나 엄청나게 해맸다. ababcdcdababcdcd 2ab2cd2ab2cd : 2개 단위 2ababcdcd : 8개 단위 문자열을 1개 이상 단위로 압축 할 때 가장 짧은 것의 길이를 return 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다. 따라서 주어진 문자열을 x/ ababcdcd / ababcdcd 로 자르는 것은 불가능 한번만 나타난 경우 1 은 생략 해당 문제의 해결 골자는 다음과 같다. 반복이 될 수 있는 경우는 글자 1개 ~ 총 글자 // 2 이다. 총 글자 // 2 를 넘어선 순간 반복하면 총 글자 수를 넘어가서 반복이 불가능하다. 문제에서 구하고자 하는 답은 "반복 하는 경우 중 가장 글자 수가 적은 경우" 이다. 즉 반복이 ..

회전판 위 N 개의 음식 각 음식은 1 ~ N 까지의 번호 각 음식 섭취에는 일정 시간 소요 다음의 방법으로 음식 섭취 1. 무지는 1번 음식부터 먹는다. 회전판 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 2. 마지막 번호의 음식 섭취 후 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 3. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취 (다음 음식이란 아직 남은 음식 중 가장 가까운 번호의 음식) 4. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다. import sys input = sys.stdin.readline food_times = list(map(int,input().split())) k = int(input()) ..

문제 A,B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다. 예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1,3,2,3,2일 때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다. (1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번) 결과적으로..

문제를 봐도 도저히 효율적으로 풀 방법이 떠오르지 않아 결국 비효율적으로 해결했다. 문제는 답안을 살펴봐도 알고리즘이 동작할 것이라는 건 확인할 수 있었지만, 왜 어떻게 동작할 수 있는지에 대해 파악하는 것이 어려웠다. 관련하여 나와 동일한 고민을 하고 내용을 정리해놓은 글을 아래 링크로 걸고, 글을 읽으며 든 생각을 정리한다. https://kk-programming.tistory.com/11 [이코테-그리디] 기출 - 04. 만들 수 없는 금액 [문제] 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N=5 이고 kk-programming.tistory.com 동전 [1, ..

그간 몇가지 기본 알고리즘을 살펴보았다. 마지막으로 다양한 그래프 알고리즘을 살펴보고자 한다. 먼저 다룬 DFS/BFS, 최단 경로 알고리즘도 그래프의 일종이다. 출제 비중은 비교적 낮은 편이다. 그래프와 트리의 차이 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 서로소 집합(union-find 자료구조) 수학에서 서로소 집합이란 공통 원소가 없는 두 집합을 의미한다. 예를 들어 {1,2} 와 집합 {3,4} 는 서로소 관계이지만, {1,2}와 {2,3}은 서로소 관계가 아니다. 서로소 집합 자료구조는 몇몇 ..

다익스트라 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 플로이드 워셜 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 정의에서 살펴볼 수 있듯이 한 지점이 아닌 '모든 지점' 에서 다른 모든 지점까지의 최단 경로를 모두 구하는 것이 플로이드 워셜 알고리즘이다. 다익스트라가 1차원 배열에 최단 거리를 저장했다면, 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장해야 한다. (다익스트라는 특정 점부터의 거리만 저장하면 되었지만 플로이드 워셜은 각 노드에서 각 노드로 가는 거리를 인접 행렬에 작성해야 한다.) 각 단계에서 해당 노드를 거쳐가는 경우를 고려 1번 노드에 대해서 확인할 경우: 1번 노드를 중간에 거쳐 지나가는 모든 경우 고려 A $..

개요 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 다양한 유형 및 상황에 적절한 효율적인 알고리즘이 이미 정립되어 있다. 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야하는 경우 최단 경로 문제는 보통 그래프로 표현 각 지점: 노드 지점간 연결된 도로: 간선 보통 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하는 유형이 빈번하게 등장 보통 다익스트라, 플로이드 워셜, 벨만 포드 알고리즘이 등장하는데, 이 중 벨만 포드는 자주 등장하지 않아 해당 글에서 다루지 않는다. 다익스트라 여러개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 다만 최단 경로 알고리..

다이나믹 프로그래밍 컴퓨터로 해결하기 어려운 문제는 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제들이 해당된다. 특정 문제들을 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적 방법이 바로 다이다믹 프로그래밍이다. (동적 할당이란 '프로그램이 실행되는 도중'에 필요한 메모리를 할당하는 기법이다. 하지만 다이나믹 프로그래밍의 다이나믹은 이 정의에 해당되지 않는다.) 다이나믹 프로그램의 대표적 예시 피보나치 수열 점화식은 수열의 항이 이어지는 형태를 간결하게 표현한다. 피보나치 수열의 점화식은 다음과 같다. $$a_{n+2} = f(a_{a+1}, a_n) = a_{n+1} + a_n$$ $$a_1 = 1, \, a_2 =..