https://www.acmicpc.net/problem/1012 1012번은 구역 나누기 같은 문제입니다. 문제에서 주어지는 예제에서는 아래와 같은 상황이 주어졌고, 문제의 규칙에 따라 지렁이는 배추가 있는 위의 그림에 빨간색 동그라미로 감싸져 있는 인접한 1들의 모임입니다. 즉, 배추의 구역들을 나누는 문제입니다. 문제에서는 지렁이가 상하좌우만 움직일 수 있기 때문에 우리가 찾아야 하는 인접한 배추들이라 하면 상하좌우 4방의 배추만 인접하다고 할 수 있겠군요. Hint! 저는 배추가 있는 곳의 좌표의 인접한 구역에 배추가 있는지 모두 확인하여 영역을 구별지었습니다. 그래서 M과 N과 같은 배추밭의 크기와 관련된 input은 사용되지 않았습니다. 제가 풀어낸 순서에 대해 간단히 정리해 볼게요!: 각 케..
https://www.acmicpc.net/problem/1011 1011번은 알파 센타우리라는 행성으로 날아가고자 하는 한 우주선이 문제의 규칙에 따라 공간이동장치로 날아갈 때 공간 이동 장치의 촤소한의 작동횟수를 구하는 문제입니다. 이 문제도 거리가 1일 때부터 하나씩 손으로 풀며 규칙을 찾아 풀었습니다. 거리 이동 방식 최소 횟수 1 1 1 2 1, 1 2 3 1, 1, 1 3 4 1, 2, 1 3 5 1, 2, 1, 1 4 6 1, 2, 2, 1 4 7 1, 1, 2, 2, 1 5 8 1, 2, 2, 2, 1 5 9 1, 2, 3, 2, 1 5 10 1, 1, 2, 3, 2, 1 6 11 1, 2, 2, 3, 2, 1 6 12 1, 2, 3, 3, 2, 1 6 13 1, 1, 2, 3, 3, 2,..
https://www.acmicpc.net/problem/1010 조합 문제가 계속 보이네요! 1010번 문제는 단순한 조합의 수 구하기 문제입니다. 아마 고등학교 함수 시간에 X, Y에서의 좌표를 각각 주고 존재할 수 있는 함수의 개수를 찾아라! 라는 문제를 보셨을 것 같은데요, 완전히 동일한 문제입니다. Hint! 단순히 강의 오른쪽의 M개의 사이트들 중에서 N개을 고르시고 왼쪽의 N개의 사이트와 겹치지 않게, N개의 다리를 놓을 수 있는 단 하나의 방법이 나옵니다. 그냥 나란히 연결하는 것이죠. 즉, 핵심은 M개의 사이트 중 N개를 고르는 경우의 수를 구하는 것이고 이전 문제 벡터 매칭에서도 사용했던 조합(combination)의 수를 구하는 문제입니다. 이번에는 조합 공식을 찾아 직접 함수를 만들..
https://www.acmicpc.net/problem/1009 1009번 문제는 비교적 쉬운 문제입니다. 10대의 컴퓨터를 가지고 있는 재용이가 데이터를 분산하여 컴퓨터에 처리하도록 하는데, a^b개의 데이터를 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, ..., 10번 데이터는 10번 컴퓨터가 처리하도록 하고 11번 데이터는 다시 1번 컴퓨터가 처리하도록 하는 규칙을 따릅니다. 문제는 마지막 데이터를 몇번 컴퓨터가 처리를 할 것인지를 알아내는 것이네요. 입력은 테스트 케이스의 수와 각 테스트 케이스마다 a와 b를 입력받습니다. Hint! 아마, a의 일의 숫자 자리와 지수 b만 초점을 두면 풀 수 있다는 것을 쉽게 알 수 있습니다. 그래서 a의 일의 자리 숫자를 10개의 if문으로 감싸..
https://www.acmicpc.net/problem/1008 하하.. 요고는 1000번이랑 1001번이랑 거의 똑같으니 코드만 두고 생략하겠습니다! int1, int2 = map(int, input().split()) print(int1 / int2)
https://www.acmicpc.net/problem/1007 1007번 문제는 벡터와 관련된 문제입니다. N 개의 점(N은 짝수)들이 주어지면, 2개의 점을 각각 연결하여 총 N/2개의 벡터 셋을 만들 때, 그 벡터들의 합의 길이의 최솟값을 구하는 문제입니다. 벡터들의 합의 길이의 최솟값! 이라고 했습니다. 이 때, 벡터의 합이 어떤 성질을 가질까에 대한 생각을 해볼 수 있겠네요. 예를 들어, (x1, y1), (x2, y2), (x3, y3), (x4, y4) 이렇게 네 점이 주어져 있다고 생각해보면, (x1, y1)에서 (x2, y2)를 향하는 벡터 v1, (x3, y3)에서 (x4, y4)를 향하는 벡터 v2 를 생각해볼 수 있습니다. 그리고 각 벡터의 값은 다음과 같이 표현할 수 있습니다. ..
https://www.acmicpc.net/problem/1006 정말... 알고리즘 초심자들을 모두 돌아가게 한다는 1006번 문제가 맞았군요. 구글링해보고 공부도 해서 풀고... 결국엔 점화식을 제시해 준 한 블로그를 참고해서 풀었습니다. 1006번 문제는 원타곤의 습격자 초라기가 자신의 특수 소대를 원타곤의 구역에 배치할 때, 최소 필요한 소대 수를 계산하는 문제입니다. 처음에는 점화식을 생각도 안한채로, 1. 특수소대가 2곳의 구역을 담당할 수 있을 때, 그 2곳 쌍을 모아서 {구역번호: [함께 담당할 수 있는 구역들]} 의 dict 셋으로 모은 다음, 2. [함께 담당할 수 있는 구역들] 의 길이에 따라 sort시킨 다음에, 3. 길이가 짧은 순서대로(왜냐하면, 길이가 짧을 수록 쌍을 이룰 수 ..
https://www.acmicpc.net/problem/1005 읽기 전에! 혹시 시간초과이신가요..? 시간초과로 여러번 실패했던 문제입니다. 첫 제출의 코드 내용은 틀린 내용이 없었는데, 시간초과 때문에 코드도 싹 바꿔보고 했었습니다. 아무리 생각을 해봐도 이렇게 했는데 시간초과인거면 그냥 파이썬으로 못푸는건가...? 라는 이상한 생각도 해봤습니다. 결론만 말씀드리면, 이 문제처럼 input의 양이 많을 경우 input() 대신 sys.stdin.readline()을, print() 대신 sys.stdout.write() 을 대체하여 사용하면 러닝 타임이 매우!! 많이!! 빨라진다고 합니다. 저도 처음 알았는데 기존 python의 input(), print() 함수는 호출이 느리다고 하네요.. 저도 ..
https://www.acmicpc.net/problem/1004 1004번에는 어린 왕자의 여행과 연관하여 문제가 소개되어 있습니다. 어린 왕자가 출발지로부터 도착지까지 행성계 사이를 여행하는데, 제시된 행성계의 경계를 최소 몇번 진입/이탈 할 것인지 구하는 문제입니다. 입력은 어린 왕자의 출발지, 도착지의 좌표와 행성계의 수, 그리고 각 행성계의 중심 좌표와 반지름이 주어집니다. 문제의 그림에서는 총 3번의 진입과 이탈이 발생하게 됩니다. Hint! 문제는, 언제 진입/이탈이 불가피한 지를 파악하는 것입니다. 공책에 아무데나 원을 그리고 출발지와 도착점을 찍어보세요. 그림은 아래 네가지 상황 중 하나일 것입니다. 출발지와 도착지가 모두 원이 포함될 때, 출발지가 원에 포함되고, 도착지는 포함되지 않을..
https://www.acmicpc.net/problem/1003 1003번 문제에는 피보나치 함수가 소개되어 있고, 문제에 대한 설명을 아래와 같이 해두었습니다. 처음에 드는 생각은, 아 그럼 저 코드를 python으로 똑같이 옮긴 다음에 전역 변수로 count0 와 count1 을 선언한 뒤 함수 내에 n == 0을 잡는 if 문이 실행이 되면 count0에 1을 더하고 n == 1의 경우에는 count1에 1을 더해서 출력하면 되지 않을까? 쉽네! 였습니다. 가령, 다음과 같이 말이죠. count0 = 0 count1 = 0 def fibonacci(n): global count0 global count1 if n == 0: print("0") count0 += 1 return 0 elif n ==..
