https://www.acmicpc.net/problem/1015 오랜만에 글을 쓰네요... 대학원 생활에 블로깅까지 하기가 힘들다는 것을 9월 초에 알고 허겁지겁 앞에 있는 일을 치우다 11월이 되었습니다 ㅜㅜ.. 최근에는 알고리즘 대회에 놀러가보자 ! 해서 문제를 이어서 풀어보려고 하고 있습니다. 원래 다음 풀 문제가 1014번인데 며칠을 붙잡고 풀어도 해결이 안돼서 우선 접어두었습니다. 찾아본 핵심 테스트 케이스들을 다 돌려 정답이 맞았는데도 accept이 안돼서 어젠 하루종일 좌절하다가 처음으로 "패스하고 다음꺼 풀자... 언젠가 풀리겠지" 하면서 1015번으로 넘어오게 되었네요. 서론이 길었네요! 1015번 문제는 수열 정렬이라는 이름의 문제로 소개되어 있습니다. 문제를 읽으면서 문제 의도가 잘..
1013번 문제는 정규표현식과 관련된 문제입니다. 파이썬의 정규표현식 모듈(re 모듈)을 자주 쓰는 편이라 금방 풀 줄 알았는데, 한 방에 해결해주는 re 모듈의 method를 모르고 있다가 몇 번의 오답 끝에 풀게 됐네요... 왜 틀렸는지도 조금만 서술해 가면서 짧게 다루고 넘어가도록 하겠습니다. 먼저, 정규표현식이라고 하면 컴퓨터가 문자열을 input으로 받았을 때, 사용자가 원하는 문자열만을 매치시켜 줄 수 있도록 해주는 일종의 규칙 혹은 패턴이라고 할 수 있습니다. 문제에서는 실제로 정규표현식에 사용하는 3가지 표현을 이용해 예제를 설명하였습니다. 3가지 표현을 간단히 짚고 넘어가면, + : "+ 바로 앞의 문자가 1번 이상 등장함" 을 의미합니다. 예를 들면, 정규표현식 "100+"는 100, ..
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() 함수는 호출이 느리다고 하네요.. 저도 ..
