https://www.acmicpc.net/problem/1024 1024번 문제는 수열의 합이라는 이름으로 소개되어 있습니다. 여기서 수열은 연속된 음의 정수가 아닌 수로 이루어진 수열로 한정되어 있고, 수열의 합이 되어야 하는 값과 최소한으로 가져야 하는 수열의 길이가 주어집니다. 문제 설명은 여기까지 하고 풀이 설명 들어갈게요! Hint! 고등 수학 과정에서 등차 수열이라는 개념이 있습니다. 연속된 수로 이루어진 수열은 대표적인 등차 수열이고, 그래서 이 문제에서는 등차 수열의 성질을 이용해서 문제를 풀 수가 있습니다. 등차 수열에 대한 개념은 여기서 다루지 않을 테니 만약 모르신다면 검색을 통해 간단히 공부를 하고 오시면 될 것 같습니다! 여기서 사용된 연속된 수열의 성질은 두 가지 케이스로 구분..
https://www.acmicpc.net/problem/1022 1022번은 소용돌이 예쁘게 출력하기 입니다. 아! 이제부터 문제 설명은 위 페이지에 있으니 생략하려고요...ㅎㅎ 풀이 위주로 설명할게요! Hint! 자잘하게 생각할거리가 많아서 차근차근 보도록 하겠습니다. 먼저 소용돌이는 문제에서 알려준 것처럼 중앙에서 출발해 숫자를 늘리며 나선형으로 배열되어 만들어집니다. 이해하는데 크게 어렵지는 않으나, 제 풀이에는 이 소용돌이를 어떻게 바라보느냐가 중요합니다. 행 번호는 r로, 열 번호는 c로 표현할 때, 아래는 -10 < r < 10, -10 < c < 10 까지 출력한 소용돌이의 모습입니다. 저는 level이라는 것을 먼저 정의하려고 합니다. level은 현재 소용돌이가 중심으로 부터 얼마나 떨..
https://www.acmicpc.net/problem/1021 * 1020번은... 생각보다 어렵네요 ㅠㅠ 공부를 좀 더 해보고 기회가 되면 다시 풀어보려 합니다. 1021번은 회전하는 큐라는 이름의 문제로 소개되어 있습니다. N개의 원소를 포함하고 있는 양방향 순환 큐에서 원하는 원소를 정해진 연산 법칙에 맞게 뽑아내는 데요, 그 연산 법칙은 다음과 같습니다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ..
https://www.acmicpc.net/problem/1019 1019번 문제는 설명이 짧아서 간단할 것 같았는데 정답률(이 글을 쓸 땐 36%네요.)을 보고 뭔가 있군... 했던 문제입니다. 문제는 첫 페이지가 1쪽이고 마지막 페이지가 N쪽인 책에서 0~9까지 각 숫자가 몇번 등장할 것인지 출력하는 것입니다. 간단하지만... 간단하진 않습니다. 입력받을 수 있는 수가 최대 10억이기 때문이죠. 입력받은 수를 그대로 반복문을 돌려 각 자리 숫자를 센다면, 꼼짝 못하고 시간초과를 받을 수 있는 문제입니다. 문제에서는 11이 예시로 들어져 있는데요, 11쪽까지 있는 책의 페이지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 이렇게 이루어져있고, 1은 총 4번, 나머지 숫자들은 모두 1번씩..
https://www.acmicpc.net/problem/1018 1018번 문제는 체스판 다시 칠하기 문제입니다. 엄청 어렵지는 않지만, 차근차근 코드를 짜는 것이 중요한 문제라고 생각합니다. 문제를 간단히 설명하자면, 지민이가 흰색이나 검정색으로 색칠되어 있는 단위 정사각형으로 이루어진 N * M 크기의 보드를 찾았고, 이 보드를 8 * 8 크기로 잘랐을 때 체스판이 되기 위해 추가적으로 칠해야할 부분의 최소 개수를 구하는 문제입니다. 체스판의 정의는 우리가 잘 알고 있는 체스판처럼 흰색과 검정색으로 번갈아져 색칠되어 있으면 되어져 있는 보드를 의미합니다. 이 때, 체스판은 제일 왼쪽 상단 정사각형의 색이 흰색 혹은 검정색으로 칠해져 있는 총 두가지의 종류로 이루어질 수 있습니다. 저는 이 점을 힌트..
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, ..
