빠르고 꾸준하게

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 2023(파이썬) - 신기한 소수

https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 이 문제는 먼저 소수를 판별해야 하기 때문에 에라토스테네스의 체로 소수인지 아닌지 확인하는 함수를 하나 만들었다. 그다음에 계속 삽질을 했던 부분인데, 나는 숫자를 하나씩 소수 판별을 해주기 위해 10으로 나눠 주고, 그 숫자들이 소수인지 아닌지를 확인했는데 이렇게 되면, 어떤 숫자들을 판별해줄 것인가?라는 생각을 하게 된다. 예시를 보면 4일 때 4자리 수 들 중 다음 조건과 같은 수..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 10830(파이썬) - 행렬 제곱

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 읽으면 먼저 어마어마한 입력값의 범위를 확인하고 시간 초과를 해결해야겠다고 생각이 들것이다. 그럼 어떻게 생각을 해야할까 를 고민하던 도중 시간 복잡도 O(N)을 절반씩 계산하면 O(logN) 이 될 거라고 생각했고 예를 들어 10번을 곱해야 한다면 5번 5번 곱한 값을 더해주면 되고 5번이면 2번 3번으로 나눌 수 있고 이렇게 아토믹하게 쪼개서 생각을 했다. (이 방법을 분할 정복 알고리즘이라고 부..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 1062(파이썬) - 가르침

https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 이 문제는 처음에 풀었을 때 시간 초과가 계속해서 발생했던 문제이다. anta와 tica를 만들수있는 알파벳 a, n, t, i, c를 제외한 알파벳 소문자 중에서 주어진 k 개수에서 5를 제외해서 경우의 수를 모두 구한 다음, 경우의 수로 나머지 알파벳을 만들 수 있는지에 대한 문제인데 이 부분을 구현할 때 시간 초과가 계속 발생했다. 해결방법은 0으로 초기화한 알파벳 체크리스트를 만들어..

자료구조 & 알고리즘/백준(Baekjoon)

[백준] 11559(파이썬) - Puyo Puyo

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 이 문제는 구현 문제로 문제에서 주어진 대로 하나하나 차근차근 풀면 해결되는 문제였다. 어려운 알고리즘이나 논리는 생각하지 않아도 됐던 거 같다. 나는 4칸 이상일 때 뿌요들을 지워주는 함수 하나, 그리고 뿌요가 4개 이상이 뭉쳐서 사라진 뒤 중력에 의해 아래로 뿌요들을 내려주는 함수 하나, 그리고 뿌요들을 4개 이상인지 확인하기 위해 BFS를 사용한 함수 하나 이렇게 만..