본문 바로가기

알고리즘 삽질장

 (228)
[BOJ] 1676번 - 팩토리얼 0의 개수 문제설명 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 사고과정 문제를 보면 "N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수"라고 되어 있는데, 처음에 이 말이 무슨말인지 이해를 잘 못했다. 질문에서 찾아보니 똑같은 질문을 한 게 있었고 보니까 이해할 수 있었다.(좀 더 부연설명이 되어 있으면 좋았을 듯 하다) 예를 들어, 10! = 3628800 이다. 이 때 362800에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수니까 2개가 된다. for loop를 이용해서 인덱스를 감소시키는 방식으로 ..
[BOJ] 6588번 - 골드바흐의 추측 문제설명 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 사고과정 우선 n = a + b 가 되는 경우의 수를 모두 살펴보지 않아도 된다. 이 때, b - a 가 가장 큰 것만 출력하면 되므로 a = (n // 2)가 될 때까지의 n = a + b 연산만 되는 경우를 확인하면 된다. 그리고 가장 먼저 n = a + b가 되는 조건이 만족했을 때가 b - a가 가장 클 때의 연산이다. 따라서 최초에 n = a + b가 되게..
[BOJ] 1978번 - 소수 찾기 문제설명 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 사고과정 다수의 소수를 찾는 알고리즘인 에라토스테네스의 체를 활용하면 된다. 주어지는 데이터의 최댓값이 1000이라고 했으므로 array 크기를 1001개로 초기화시켜준 후 한 번에 0부터 1000까지의 소수를 판별하고 난 후 주어진 nums를 하나씩 돌면서 해당 nums 인덱스에있는 array의 값이 True면 소수임을 의미한다.(0과 1은 소수가 아님을 잊지말자!) 또한 array 크기를 초기화시켜줄 때, 어차피 주어진 nums의 최댓값 + 1 의 길이..
[BOJ] 11656번 - 접미사 배열 문제설명 https://www.acmicpc.net/problem/11656 11656번: 접미사 배열 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000보다 작거나 같다. www.acmicpc.net 사고과정 문제는 쉽지만 기록하는 이유는 시간 복잡도에 익숙해지기 위함이다. 우선 문제에서는 문자열의 길이가 최대 1000이라고 했으므로 모든 접미사를 탐색하는 선형탐색 1000번 , 그리고 정렬시킬 때 파이썬 정렬 라이브러리를 이용했으므로 $(1000log1000)$이므로 10,000번, 마지막에 결과값을 출력할 때, 또 1000번 해서 총 12,000번의 연산을 수행한다. 파이썬에서는 1초에 천만번 연산을 수행하므로 시간초과 에러를 받지 않고 통과할 수 있다. 풀이..
[BOJ] 10824번 - 네 수 문제설명 https://www.acmicpc.net/problem/10824 10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net 사고과정 쉬운 문제였지만 최대한 간결하게 작성하려 했다. 어차피 4개 수가 주어지니까 for loop로 돌리는데 step = 2로 두어서 2번만의 탐색으로 답을 구할 수 있도록 했다. 풀이 import sys input = sys.stdin.readline array = list(map(str, input().split())) result = 0 for i in range(0, len(array), 2): result += int(array[i] + array[i+1]) pr..
[BOJ] 11655번 - ROT13 문제설명 https://www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 사고과정 처음에 아스키 코드로 13번째 뒤 문자를 의미하는 줄 알았으나 입력 예시를 쳐보고 그게 아니고 알파벳 대문자 ,소문자 상에서 각각 13번째 뒤를 의미하는 것을 깨달았다. 그래서 A~Z, a~z 별로 아스키 문자를 활용해 각 대문자, 소문자 리스트를 만들어주었다. 문자열 하나씩 돌면서 알파벳 대문자 또는 소문자 일때, 각각의 대문자, 소문자 리스트를 참조하는데, 이 때 13번째 증가한 인덱스의 값으로 대체해주면 된다. 단, 13번째 인덱스를 더했을 때..
[BOJ] 10820번 - 문자열 분석 문제설명 https://www.acmicpc.net/problem/10820 10820번: 문자열 분석 문자열 N개가 주어진다. 이때, 문자열에 포함되어 있는 소문자, 대문자, 숫자, 공백의 개수를 구하는 프로그램을 작성하시오. 각 문자열은 알파벳 소문자, 대문자, 숫자, 공백으로만 이루어져 있 www.acmicpc.net 사고과정 구현 내용은 쉬웠지만 다른 부분에서 자꾸 에러가 발생했다. 1번째는 아무것도 입력이 안되면 종료되는 EOF Error 예외처리 구문을 입력해주는 것이었고, 2번째는 EOF Error 외에 애초에 맨처음부터 아무것도 입력되지 않았을 때 while문을 빠져나가게 해줬어야 했고, 3번째는 string을 입력받을 때, 줄 바꿈(개행)으로 해서 입력을 받기 때문에 끝에 \n 이 입력된..
[BOJ] 10809번 - 알파벳 찾기 문제설명 https://www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net 사고과정 처음에 이진 탐색 라이브러리를 사용할까 했지만 a가 b앞에 나오는 경우도 인덱스 0으로 출력되기 때문에, 그리고 문자열 길이가 최대 100이고 알파벳은 총 26개니까 선형탐색을 해도 최악의 시간복잡도 $O(100 x 26)$이 나오기 때문에 이중 Loop로 선형 탐색을 진행했다. 단, 바로 첫번째 글자가 나오면 중첩 loop를 빠져나오도록 했고 선형탐색 하기 이전에 ..
[BOJ] 10808번 - 알파벳 개수 문제설명 https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 사고과정 쉬운 문제인 것 같아도 방심하지 않고 풀려고 노력했다..! 그래도 이거는 맞았다! 우선 소문자 알파벳으로만 이루어졌다고 했기 때문에 소문자 알파벳 a ~ z까지 26개이기 때문에 0부터 26까지 loop를 돌면서 해당 숫자의 값과 ord('a') 값과 더한 int 값에 chr() 를 씌우면 a ~ z까지 중 하나가 나오게 된다. 그리고 해당 알파벳을 문자열에서 count 함수를 사용해 찾았다! 풀이 import sys input = sys.stdin.readline stri..
[BOJ] 1935번 - 후위 표기식2 문제설명 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 사고과정 피연산자 문자열을 숫자로 대응시킬 때 ord를 사용했어야 한다.. 이번엔 피연산자를 스택에 넣고 연산자를 만날 때마다 스택에서 2개의 숫자를 pop해서 연산한 결과값을 다시 스택에 넣어준다. 단, 빼기, 나누기를 만났을 때는 먼저 pop해준 것을 뒤에놓고 두 번째 pop해준 것을 앞에 놓아야 한다. 예를 들어 stack = [1, 2] 가 있었을 때, 빼기, 나누기 연..
[BOJ] 1918번 - 후위 표기식 문제설명 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 사고과정 스택에 무엇을 넣어야 할지 매우 고민했다. 괄호만? 연산만? 문자열도? 결국 괄호랑 연산을 하나의 스택에, 문자열을 또 하나의 스택에 넣으려고 했다. 나름 풀려고 노력했지만 못 풀었다.. 다른 분의 풀이를 보니 괄호, 연산을 하나의 스택에 넣는 건 맞았지만 문자열은 그냥 바로 결과값에 붙이면 되었다. 해당 문제를 풀이하는 과정을 단계화해보면 아래와같다. 1. 스택에는 무..
[BOJ] 17299번 - 오등큰수 문제설명 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 사고과정 저번 오큰수 문제로 스택을 활용해서 풀려고 했는데 어려웠다.. 단어의 개수가 추가된 것이 조금 응용된 것인데 이거를 잘 해결해내지 못했다.. 구글링을 해보니 핵심 풀이는 각 수열 원소에다가 수열에 존재하는 단어 개수를 추가하면 된다. 예를 들어, 수열이 [1, 1, 2, 3, 4, 2, 1] 이 주어졌다면 (원소 개수, 원소) 로 해서 [(3, 1), (3, 1), (2, 2), (1, 3)..
[BOJ] 17298번 - 오큰수 문제설명 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 사고과정 처음에 이중 for 문으로 구현하려 했다가 바로 시간초과가 발생하는 것을 인지했다.. 그래서 어떻게든 자료구조 스택이나 큐를 활용해서 해결해야 할 것 같은데.. 큐를 활용해보려고 했으나 큐도 어쨌거나 한 번의 선형 루프를 또 활용하는 아이디어 밖에 떠오르지 않았다.. 스택은 어떻게 활용할지 감이 오지 않았다 풀이를 보니 스택을 활용했는데, n개의 수열 하나씩 도는데, 안에다가 while ..
[BOJ] 10799번 - 쇠막대기 문제설명 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 사고과정 또 괄호 문제였는데 이번엔 풀지 못했다.. 스택을 활용하는 문제였는데, ( 가 등장할 때마다 스택에 넣고 )가 등장할 때는 )가 등장하기 이전에 (가 등장했으면 레이저용 괄호로 간주하고 스택의 마지막 (를 pop해주고 남은 스택의 길이 만큼이 해당 레이저로 의해 잘려지는 막대 개수이다. 만약 이전에 ) 가 또 등장했다면 연속적인 쇠막대기의 등장인 것이므로 스택의 마지막 (를 pop해주되 잘..
[BOJ] 17413번 - 단어 뒤집기 2 문제설명 https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 사고과정 먼저 태그가 있는 인덱스만 따로 빼내서 태그가 있는 문자열 추출까지는 했는데, 이렇게 따로 빼낸 태그가 있는 인덱스를 가지고 일반 문자열이 있는 인덱싱으로 가는 데 막혀서 해결하지 못했다.. 구글링을 해보니 주어진 문자열을 입력받아서 while 문을 하나씩 돌면서 태그 안의 내용은 그냥 그대로 두고 문자열만 마주쳤을 때 뒤집는 선형방식으로 ..
[BOJ] 1158번 - 요세푸스 문제 문제설명 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 사고과정 처음에 while 무한 루프로 구현했지만 시간초과 케이스가 발생.. 그래서 index가 배열 범위를 넘어갈 때 다시 0번 인덱스로 돌아가게 하기 위해서 %연산을 쓰긴 해야할 것 같다는 아이디어는 생각했지만 코드로 구현해내지 못했다.. 구글링해 보니 명쾌하게 이해가 되었는데, 예를 들어 index = 7 이고 len(array) = 5다 라고하면은, 7 % 5 가 의미하는 바는 길이가 5인 배열에서 7번 인덱스를 찾아야 하는데 길이 범위를 넘으니 7을 5로 나눈 나머지인 ..
[BOJ] 10845번 - 큐 문제설명 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 사고과정 데큐 라이브러리를 활용해 큐를 구현했다. if 문을 좀 더 간결하게 작성해 보았다. 처음에 front, back을 입력받으면 출력만 해주고 원소를 빼내지 않아야 하는데 pop 까지 해버려서 실수하긴 했다..! 시간 초과를 막기 위해서 sys 라이브러리를 사용했다(sys 사용안하면 시간초과 남!) 풀이 from collections import deque impor..
[BOJ] 1406번 - 에디터 문제설명 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 사고과정 처음에 전형적으로 커서를 인덱싱으로 나타낸 후, 명령어가 들어올 때마다 파이썬 문법 중 del list[index] 또는 list.insert(index, value) 를 사용했지만 시간초과 에러가 발생했다. 그래서 구글링해보니 2개의 스택을 활용하는 것이 핵심 아이디어 였다. 최초에 커서가 가장 오른쪽이니 오른쪽 용 스택은 비어놓고 주어진 문자열을 모두 왼쪽 스택에 담아놓는다. ..
[BOJ] 1874번 - 스택 수열 문제설명 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 사고과정 문제 이해하는 데 시간이 걸렸다. 그리고 스택을 이용해야 하는데, 1부터 수열의 원소 하나하나까지 push하고 그 원소값에 해당하면 pop해야 하는 건 알겠는데 코드로 구현하지는 못했다.. 구글링을 해보았고 핵심 포인트는 특정 숫자를 입력받을 때마다 그 숫자가 같아질 때까지 1부터~그 숫자를 스택에..
[BOJ] 9012번 - 괄호 문제설명 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 사고과정 예전에 풀어본 괄호관련 문제를 풀어본 게 도움이 되었다. 핵심 풀이법은 다음과 같다. 1. ( 가 먼저나와야 함을 인지! ( 가 나올 땐 +1 하고 ) 가 나오면 -1을 한다. 이 때, )가 나오고 -1을 하기 전에 count 값이 이미 0이 된 상태라면 올바른 괄호 문자열 상태가 아니다. 예를 들면 " ( ) ) " 이런 경우! ) 가 나오고 연속..

티스토리툴바