아리의 개발 일상

[파이썬] 백준 3190 뱀https://www.acmicpc.net/problem/3190 문제Dummy라는 도스 게임이 있다. 이 게임에는 뱀이 나와서 기어 다니는데 , 사과를 먹으면 뱀 길이가 늘어난다.뱀이 벽 또는 자기 자신의 몸과 부딪히면 게임이 끝이 난다. N x N 정사각 보드 위에서 진행되고 몇몇 칸에 사과가 놓여 있다. 보드 상하좌우 끝에는 벽이 있다.뱀의 처음 시작위치는 맨 위 맨 좌측에 위치하고 처음 길이는 1이다. 뱀은 처음에는 오른쪽으로 향한다. 뱀은 매초 마다 움직이는데 아래의 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기 자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는..

[백준 파이썬] 1389 케빈 베이컨의 6단계 법칙 문제케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다.케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이으로 이 게임을 했을 때 모든 사람 나오는 단계의 총 합을 케빈 베이컨의 수라고 할 때 이때 이 수가 가장 적은 사람을 찾는 문제이다. 이때 단계를 계산하는 방법으로 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해 보자.1은 2까지 3을 통해 2단계 만에 연결될 수 있으며, 3까지는 1단계 , 4까지 1단계 , 5까지는 4를 통해 2단계만에 연결된다그러면 케빈 베이컨의 수는 2+1+1+2 = 6이다...

[백준 파이썬] 2579 계단 오르기문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에서 위치한 도착지점까지 가는 게임이다.각 계단에는 일정한 점수가 쓰여 있고 그 계단을 밝으면 점수를 얻게 된다.이때 총점수의 최댓값을 구해야 하면 아래의 규칙을 지켜야 한다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.위그림의 예를 가지고 풀어본다면첫 번째 계단 => 두 번째 계단 => 네 번째 계단 => 다섯 번째 계단 밟으면 최댓값이 나온다.  풀이이 문제를 풀기 위해서 해야 할 첫 번째 생..

[백준 파이썬] 2749 피보나치 수 3  처음에는 이게 무슨 골드 2 문제지 하고dp=[0,1]n=int(input())for i in range(2,n+1): dp.append((dp[i-1]+dp[i-2])%1000000)print(dp[n])이렇게 코드를 제출했다 결과는 메모리 초과로 실패하여 문제 조건을 확인하였다입력이 1,000,000,000,000,000,000 작은 n에 대한 피보나치수열인데 메모리 제한이 128MB였다.문제 답을 출력할 때 1,000,000으로 나눈 나머지를 출력한다라고 적혀있었다.이걸 보고 난 반복되는 주기가 발생할겠다고 생각하여 dp=[0,1]n=int(input())for i in range(2,4500000+1): dp.append((dp[i-1]+dp[..

문제동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 그곳으로 가야 한다 이때 블록을 가로질러갈 수 없다 그렇기에 1번 에서 호출이 들어올 경우 x에서 출발하여 1번까가는 거리는 시계방향으로 갈경우 12, 반시계 방향으로 갈 경우 18이 된다.2번에서 호출이 들어올 경우 최단거리는 6이고 3번은 5가 된다 이때 각 상점  사이의 최단 거리의 합을 구하는 프로그램을 작성하시오.입력첫 번째 줄에의 블록의 가로 길이와 세로 길이가 주어진다.둘째 줄에는 상점의 개수가 주어진다.그다음 줄부터는 상점의 위치가 주어지는데  첫번째 수는 1은 북, 2는 남, 3은 서 , 4,는 동쪽을 의미하며 두 번째는 상점의 위치를 의미한다.그리고 마지막 둘은 동근의 위치를 상점 위치과 같이 나타낸다. 출력첫..

[백준 파이썬] 보물 1026 문제길이가 N인 정수 배열 A와 B가 있다 다음과 같이 함수 S를 정의하자. S의 값을 가장 작게 만들기 위해 A의 수를 재배열 하자 단, B에 있는 수는 재배열하면 안 된다.S의 값이 최소가 되는 프로그램을 작성하라.입력첫째줄에 N이 주어진다.둘째 줄에는 A의 배열이 주어진다.셋째 줄에는 B의 배열의 주어진다. 출력첫째줄에 S의 최솟값을 출력한다.풀이A배열만 움직여 B배열과 곱셈을 하여 모든 값을 다 더한 값을 S이다. 이때 A배열의 인덱스만 움직여야 한다고 한다. B배열의 값들의 위치는 정해져 있고 최솟값이 되기 위해서는 B배열의 높은 값을 A배열의 가장 낮은 값을 곱셈하도록 만들어주면 가장 낮은 S값이 된다. 결론은 A 배열을 오름차순으로 정렬한고 B배열을 내림차순으로..

[백준 파이썬] 15654N과 M(5) 문제 N개의 자연수와 자연수 M이 주어졌을대 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. -N개의 자연수 중에서 M개를 고른 수열 입력 첫째 줄에 N과 M이주언지다 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10000보다 작거나 같은 자연수이다. 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안 되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 이 문제는 백트래킹을 이용한 문제로 백트래킹 알고리즘은 모든 경우의 수를 탐색하면서 현재 주어진 조건과 맞는 것을 선택하고 아닐 경우 ..

[백준 파이썬] 15686 치킨 배달 문제유형 브루트포스 알고리즘 백트래킹 구현 문제 크기가 N x N인 도시가 있다. 도시는 1x1 크기의 칸으로 나누어져 있다 0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 2 위와 같이 입력이 주어지는데 이때 r행 c열에 위치한 지점을 (r,c)와 같은 형태로 나타낸다. r, c는 1부터 시작한다. 이때 0은 비칸, 1은 집 , 2는 치킨집이다. 자신의 집에서 가장 가까운 치킨집 과의 거리를 치킨 거리라 한다. 각각의 집은 치킨 거리를 가지고 있으며 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 치킨 거리를 구하는 방법은 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다. 치킨집 중 ..

[백준 파이썬 소로소 집합]1043 거짓말 문제 주인공은 파티 가서 이야기하는 것을 좋아한다. 파티에 갈 때마다 자신의 이야기를 과장해서 말한다. 하지만 거짓말쟁이로 알려지기 싫어한다. 문제는 몇몇 사람들이 이야기의 진실을 알고 있다 그렇기에 진실을 알고 있는 사람들이 있을 때에는 진실을 이야기할 수밖에 없다. 당연히 어떤 사람이 어떤 파이테서는 진실을 듣고 또 다른 파티에서는 과장된 이야기들을 들었을 때도 주인공은 거짓말쟁이로 알려지게 된다. 주인공은 이런 일을 모두 피해야 한다. 사람수 n이 주어지고 진실을 아는 사람과 각 파티에 오는 사람들의 번호가 주어진다. 주인공은 모든 파티에 참가해야 한다. 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하여라. 입력, 출력 풀이 나는 union find..

[백준 파이썬] 1644 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데,20이 그 예이다 7+13을 하면 20이 되기는 하지만 두수는 연속된 소수가 아니기에 적합한 표현이 아니다. 한 소수는 반드시 한번만 사용할수 있다. 입력 첫째 줄에 자연수 N이 주어진다 출력 주어진 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다. 풀이 소수를 찾기위해 난 에스토라체 라는 알고리즘을 사용하여 소수인 경우 1의 값을 넣어 소수인걸 나중에 확인할수 있도록 하였다. 시작위치를 start=1 부터 시작하게 하여 소수이면 sum에 더하게 하여 sum이 찾는값에 도달하면 경우의수 +1 ,start +1 을 하..