https://www.acmicpc.net/problem/1017 1017번 문제는 소수 쌍 문제입니다. 수의 리스트를 입력 받았을 때, 이를 짝지어 만들 수 있는 각 쌍의 합이 모두 소수가 되게 하는 경우, 첫번째 숫자와 짝지어진 숫자를 답으로 출력하는 문제입니다. 문제의 예시에는 만약 {1, 4, 7, 10, 11, 12} 의 숫자 리스트를 받았다면, 1 + 4 = 5, 7 + 10 = 17, 11 + 12 = 23 또는 1 + 10 = 11, 4 + 7 = 11, 11 + 12 = 23 의 경우가 가능합니다. 즉, 각 경우에서 첫번째 숫자(1)와 짝지어진 4, 10이 답이 됩니다. Hint! 이 문제도 역시 DFS로 접근이 가능합니다. 답에서 중요한 점은 모든 쌍들의 합이 소수가 되었을 때, 첫번째..
https://www.acmicpc.net/problem/1014 오랜만에 알고리즘 글을 올리게 되네요. 저번 학기가 너무 여유가 없었어서 꾸준히 올리고 싶었는데... 풀 때까지 하루종일 잡을거 생각하니 바빠서 손에서 잘 안잡히더라고요. 방학이기도 하고 충분히 쉬었다 싶어서 다시 시작해보려고 합니다. 이번 문제는 제가 이전에 점프하고 넘어갔던 1014번 컨닝입니다. 이 문제는 제가 여러번 시도를 했는데 실패했고 도저히 반례도 찾을 수가 없어서 포기한 문제입니다. 1016번까지 풀고 그래도 마저 풀고 싶다는 생각에, 이래저래 검색도 해보고 공부도 하다가 겨우겨우 풀어냈네요. 그 과정을 다 서술하고 싶지만, 그 내용이 꽤 많아서 저는 최대한 간단히 적고 개념 이해에 도움이 많이 되었던 사이트들을 링크하도록 ..
https://www.acmicpc.net/problem/1016 1016번 문제는 제곱 ㄴㄴ수라는 이름으로 소개되어 있습니다. 최소와 최댓값을 입력받았을 때, 최솟값과 최댓값을 포함한 사이의 값들 중 제곱 ㄴㄴ수의 개수를 찾는 문제입니다. 문제에 의하면 제곱 ㄴㄴ수는 "어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때의 X"를 의미합니다. 일반적으로, 제곱수는 자연수의 제곱을 의미합니다. 문제만 봤을 때, 구현 자체는 생각보다 간단할 수 있습니다. min부터 max까지 숫자를 순서대로 나열한 list에서 max보다 작거나 같은 제곱수의 배수들을 모두 제외하면 된다고 생각할 수 있지요. 하지만, min의 범위가 1,000,000,000,000 까지 허용되기 때문에 이 방법은 다시 생각해 봐야합니..
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)
