Embedded Files
# 기본 알고리즘 1/2 (Basic Algorithm 1/2, 201, 203 ,300) 후기 (2023.12.13)
stack 을 활용 > 자료 구조의 이해
Eratosthenes Sieve for Prime Numbers 활용 > 시간 단축
간단한 수식에 대한 이해로 factorial 0 의 갯수, nCm 0의 갯수 > 시간 단축.
몇몇 Gold Stage 문제 스스로 해결 =)
Baekjoon 1918 후위 표기식의 경우, 인터넷에 없는 아이디어로 재귀적으로 해결. stack를 활용한 것과 소요 시간도 동일. =)
2023.12.12 - Baekjoon 2004, 정답률 28.699%, 이전에 factorial code로 생각하여 5에 관해서만 생각했더니 15C12 = 455로 0이 0개인데 1개로 나오는 오류 발생. 수식으로 생각해보니, 5와 2의 갯수로 따로 생각하여 그중에 최솟값이 0 의 갯수.
2023.12.12 - 203 자료구조1, 300 수학1 & Purdue 1st Semester 완료 =)
2023.12.10 - Baekjoon 6588, 에라토스테네스의 체로 접근. 기준이 0.5초. 시간초과를 해결하기 위해서,
num을 받을 때마다 prime_sieve 를 얻지않고,
최대 입력값인 1000000을 입력하여 전체 prime_sieve 를 얻은 후에
모든 입력 num 들에 대해 사용.
2023.12.10 - 203 자료구조, 300 수학 1 진행 중. 팩토리얼 0의 개수의 실제로 문자열로 접근안하고, 수학적으로 5와 2의 배수로 생각하면 된다고 생각하여, 다른 답들도 찾아봄. 인상적인 것은 one-line code.
N = int(input())
print(N//5 + N//25 + N//125)
N < 500 이하인 상황에서,
5 는 0을 1개
5^2 은 0을 2개
5^3은 0을 3개
추가한다는 개념. 5에서 0을 만들기 위한 짝수는 factorial 특성상, 항상 5의 갯수에 대응되어 존재하므로 5의 배수만 세어주면 됨.
2023.12.12 - Baekjoon 1918, 후위 표기식. 40ms
내 방식) 재귀적 방법, 40ms
()가 없는 경우 +,-,*,/ 를 표시해주는 postfix() 함수를 정의해주고,
괄호 () 한쌍을 만나면 그 안에 postfix()를 적용하고 새로운 문자열을 반환. 새로운 문자열에 해당 과정을 반복하는 것으로 적용.
백분 풀이) Stack 활용, 40ms
https://www.youtube.com/watch?v=vXPL6UavUeA
나는 스택을 사용하지는 않았지만, 1918 후위표기식이 Gold2 로 이때까지 푼 문제 중에 가장 어려운 난이도였음. 2023.12.06- 2023.12.12 총 7일 시도하여 풂.
2023.12.09 - Baekjoon 17299 오등큰수 1460ms. 처음부터 시작하는 방식, 내 방식으로 푼 후에 인터넷에 오큰수의 풀이를 한번 참고해봄. 짧은 코드에 많은 내용이 담겨있음. 오큰수와 오등큰수는 내 수준에 꽤 어려웠다고 생각함. 실제 난이도도 Gold3로 꽤 어려운 것이 맞는 듯.
최근 기말 시험기간으로, Baekjoon 17299 오등큰수는 5일에 걸쳐서 여유를 가지고, 토요일 아침-점심 사이에 본격적으로 고민해보고 풀었음. 풀고나서 다른방향의 인터넷 해답을 이해하고, 시간을 비교해본 것도 의미있는 과정이었음. 한문제에 대해 다양한 풀이, stack에 대한 고민, stack을 1개 쓸까 2개 쓸까에 대한 고민 등 다양한 시도를 해볼 수 있었음.
2023.12.09 - 자료구조 마지막 한문제 후위표기식 진행 중.
2023.12.08 - 자료구조/수학 1 진행 중
2023.12.09 - 오등큰수 시간초과, 뒤에서 부터 시작. F를 구할 때, 모든 index 에 count() 함수를 호출하여 갯수를 센 것이 시간초과 이유. 알고리즘은 명료하며 오큰수 확장. 배열 원소값(A)과, 원소의 갯수값(F)를 위한 stack 2개를 사용.
2023.12.09 - 오등큰수 2124ms 통과. 뒤에서 부터 시작. A 원수의 갯수 F를 구할 때, +1씩 카운팅하는 방식으로 접근하여 통과.
2023.12.06 - 알파벳 개수는 간단하게 해결. 알파벳 찾기는 초기에 해결했던 문제였음.
2023.12.07 - 자료구조 진행중, 자료구조1 쇠막대기 해결.
2023.12.07 - Baekjoon 48257: 쇠막대기
'()' 의 끝 ')'이면, 레이저이므로 겹친 막대 갯수만큼 더함.
'))'의 끝 ')' 이면, 막대의 끝이므로 막대가 끝나면서 생기는 조각 1개만 더함.
2023.12.05 - Baekjoon1935 후위표기식2
2023.12.05 - Baekjoon1935 후위표기식2, 31120KB, 40ms 로 통과. 사칙연산 문자가 등장할 때 까지 stack에 쌓다가, 사칙연산이 등장하면 쌓아진 stack 제일 위의 3가지를 연산하고 추가하는 방식으로 접근.
다른 해답을 보니, if 문에 'A' <= i <= 'Z' 사용하거나 (처음 알았음)
operator는 stack.append()하지 않고 pop() 두번 사용하는 방식
기본적으로 stack을 사용한다는 접근 방식은 동일하여, 내 코드가 꽤 잘 짜여졌음.
2023.12.04 - 쇠막대기 idea를 잘 모르겠음.
2023.12.04 - Baekjoon 17298 오큰수, 151812KB, 1908ms, 다를 풀이를 보니 idx=0에서 시작하되, {오큰수, index} 까지 stack에 쌓아서 복잡도를 낮추기도 함.
2023.12.04 - Baekjoon 17298 오큰수, 뒤쪽에서 부터 오큰수(NGE)를 찾고 stack에 넣 방식으로 접근. "-1"을 처음에 넣는 이유가 Ai 가 1보다 크기 때문에, 자연스럽게 시작하기 위해서 라는 것으로 이해 됨.
2023.12.04 - Baekjoon 17298 오큰수, 처음에는 N, N-1, ... 1 개의 배열로 O(N^2)으로 접근했더니 시간초과. stack을 활용해서 복잡도를 낮춤. 내 풀이는 minmax algorithm과 어느정도 유사하다고 생각되었음.
2023.12.03 - Basic Algorithm 1/2 - 201 - 단어뒤집기 2, stack 으로 접근.
2023.12.02 - Achieve Purdue Top 10
2023.12.02 - 알고리즘 기초 1/2 "200- 자료구조 1" 완료
2023.12.02 - baekjoon 1874 스택수열 260ms로 통과
2023.12.02 - baekjoon 1406 444ms로 통과, O(N) 복잡도를 가지는 insert 대신, cursor를 기준으로 양옆의 문자열을 stack으로 보고 접근하여 O(1)의 복잡도를 가지는 pop(), append() 가지고만 구현. 마지막에 reverse() 대신 queue, deque를 사용해도 되었을 것 같음.
2023.12.01 - 단어 뒤집기 완료, 괄호는 이미 했었음.
2023.12.01 - 큐, 조세피스, 덱 완료. 나머지 두문제 {스택 수열, 에디터}는 좀 생각이 필요함.
(1) 스택 수열의 경우 inverse function 관점으로 접근했더니, 시간초과.
(2) 에디터의 경우 단순히 list로 접근했더니, 시간초과.
2023.11.30 - Stack. One Try, One Complie =)
2023.11.30 - Start to solve Basic Algorithm 1/2! Without the paid lecture, Just solve the well-organized problems =)
Page updated
Google Sites
Report abuse