본문 바로가기

규칙성 찾기6

[Programmers] n^2 배열 자르기 https://school.programmers.co.kr/learn/courses/30/lessons/87390 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 $n \times n$ 크기의 행렬 matrix[][]는 한 행에 $n$ 개의 요소를 가지므로, 각각의 행을 이어붙여 1차원 배열로 만들었을 때의 $k$ $(1 \le k \le n^2)$ 번째 요소는 $k$ 를 $n$으로 나눈 몫을 $q$, 나머지를 $r$ 이라고 했을 때 matrix[$q$][$r$] 이다. 한편, 문제에서 주어진 규칙에 따라 $n \times n$ 크기의.. 2024. 1. 2.
[Baekjoon] 1436번: 영화감독 숌 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 문제 해결 과정 착안 $N$ 번째 종말의 수를 찾을 때까지 반복문을 통해 666부터 시작하여, 숫자를 문자열로 바꾸었을 때 666이라는 문자열을 포함하는지의 여부를 확인하여 카운팅하고 숫자를 1씩 증가시킨다(브루트 포스(brute-force) 방법). 또는, $N (1 \le N \le 10000)$ 번째 종말의 수가 가지는 규칙성을 파악하여 이를 활용해 문제를 해결한다. 구현 1) 숫자를 1씩.. 2023. 12. 22.
[Baekjoon] 1019번: 책 페이지 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 해결 과정 착안 각 자릿수마다 숫자 0부터 9까지 등장하는 규칙성을 찾아 이를 이용해 계산한다. 책의 마지막 페이지가 5425 페이지라고 가정하여 아래와 같이 규칙성을 파악해보자. 위의 그림과 같이 1부터 5425까지 모든 숫자를 자릿수 별로 확인하기 편하게 나열해보면, 일의 자리가 0인 숫자: 0, 10, 20, $\cdots$, 5420 $\Rightarrow$ (543 - 1) 개 (첫 페이지가 1부터 시작하므로) 일의 자리가 1인 숫자: 1, 11, .. 2023. 12. 20.
[Baekjoon] 2164번: 카드2 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 해결 과정 착안 문제의 의도는 큐(queue)나 덱(dequeue) 등의 자료구조를 활용하여 카드를 버리거나 뒤로 넣는 과정을 반복하는 것을 의도한 것 같았지만 문제 내의 규칙성을 찾아 더 효율적으로 해결을 해보고자 하였다. 문제를 처음 봤을 때, 문제를 간단히 해결할 수 있는 규칙성이 존재할 것이라고 추론할 수 있었던 부분은 작은 수의 $N$에 대하여 문제에서 주어진 과정을 수행하면서 대략.. 2023. 5. 23.
[Baekjoon] 1193번: 분수찾기 https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 직전의 포스트와 마찬가지로, 이번 문제도 규칙성을 찾으면 쉽게 해결 가능한 문제이다. 본인은 처음 이 문제를 풀 때 너무 단순하게 생각해서 실제로 지그재그로 움직여서 구하는 코드를 짰었는데, 실행 시간이 생각보다 길게 나와서 다른 사람의 코드를 분석해보다가 깨달음을 얻고 눈물을 흘려버리고 말았다. 문제 해결 과정 착안 실제로 지그재그로 움직여서 구한다(분자 또는 분모가 1이 될 때 방향을 전환하는 원리). 아래와 같이 분수들을 그룹화 하고, 각 그룹의 규칙성을 찾아 해결한다(아래 그림 참고). 그림과 같이 분수들을 묶으면, \(.. 2023. 5. 6.
[Baekjoon] 2292번: 벌집 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 이번 문제를 보고서는 규칙을 금방 찾아낸 사람에게는 아주 쉬운 문제이지만 규칙을 잘 발견하지 못한 사람에게는 엄청나게 어려운 문제가 될 수도 있을 것 같다는 생각이 들었다(물론 전혀 아닐 수도 있다 ㅎㅎ 반박 시에는 항상 제가 죄송합니다). 문제 해결 과정 착안 아래의 그림과 같이 구획을 나누어 규칙성에 따라 문제를 해결한다. 벌집의 중앙 1에서 \(N\)번 방까지 최소 개수의 방을 지나서 갈 때 지나는 .. 2023. 5. 6.

티스토리툴바