본문 바로가기

전체 글

 (23)
[스택심화]17298-오큰수 오큰수? 육큰수는요? 깔깔깔~ 1. 아이디어 스택 관련하여 유형을 익힐 수 있는 오큰수 문제이다. 오큰수 문제는 간단한 아이디어로 시작된다. 느낌상으로만 보자면 동적 계획법과 비슷한 느낌도 존재한다. 뒤쪽부터 시작하여 스택에 추가한 뒤, pop()해주면서 가장 오른쪽에 있는 값을 찾으면 되지 않을까? 2. 정리 3. 코드 import sys input = sys.stdin.readline print = sys.stdout.write n = int(input().rstrip()) num = list(map(int, input().rstrip().split())) stack = [] value = [-1]*(n+1) for i in range(n-1, -1, -1): while True: if len(sta..
[스택 심화]9935-문자열 폭발 단계별로 풀어보기 스택 2에 있는 문자열 폭발이다. 문제 조건에서 알 수 있듯이, 폭발 문자열이 사라질 때까지 폭발 문자열을 삭제해주면 된다. 1. 아이디어 python replace를 쓰니까 광탈... 직접 replace를 구현해줄 방법이 있을까? ->스택사용! 파이썬은 문자열 합치기 기능(join)이 있으므로 구현하기 간단하다. 2. 코드 s = input() boom = input() stack = [] m = len(boom) for i in s: stack.append(i) while stack and "".join(stack[-1*m:]) == boom: if "".join(stack[-1*m:]) == boom: for j in range(m): stack.pop() if stack: pri..
그 유명한 N-queen Is this the real life? Is this just fantasy? Caught in a landside, No escape from reality Open your eyes, Look up to the skies and see, I'm just a poor boy, I need no sympathy, Because I'm easy come, easy go, Little high, little low, Any way the wind blows doesn't really matter to Me, to me Mamaaa, Just killed a man, Put a gun against his head, pulled my trigger, Now he's dead Mamaaa, life had j..
과학고등학교 생활 2022년 12월에 과학고등학교 합격이 확정되었다. 합격의 기쁨이 채 가시지도 않을 무렵, 수업이 시작되었고 수업은 속도가 빠르고 어려웠다. 특히 수학이 그랬던 것 같은데 나는 과학과 정보에 비해 수학을 별로 안했기 때문에역시 처음 시험에서 가장 망한 것은 수학이었다. 여지껏 내 공부 습관은 필기를 위주로 하고, 계획을 위주로 하는 습관이 아니었다. 그래서인지 당연하게도 많은 수업 내용을 내 머릿속에 담을 수 없었고 시험 준비에도 어려움을 겪었다. 첫 번째 시험은 내가 원하던 결과를 얻지 못하였다. 결과는 처참했고, '나는 이 학교에서 살아남을 수 있을까?' 라는 생각이 들기도 하였다. 그렇지만 두 번째 시험은 마음을 고쳐먹고 첫 번째 시험보다는 약간 등급이 올랐다. 하지만, 수학은 별로 오른 것 같지 ..
백준 1300-K번째수 알고리즘 분류: 파라메트릭 서치, 이분 탐색 설명하기 전에, 파라메트릭 서치(매개 변수 탐색)에 대해 알아볼 필요가 있다. 파라메트릭 서치는 "...한 값을 찾으라" 하는 문제를 "이 값은 ...인가?" 하는 예/아니오를 판별하는 간단한 문제로 바꾸어서 탐색하는 것이다. 그렇다면 파라메트릭 서치는 이분 탐색과 연계되기 매우 좋은 조건을 가지고 있다. 이 문제에서도 "...한 값을 찾으라" 형태의 문제 형식을 따르고 있다. 따라서 이 문제를 풀기 위해 예/아니오를 판별하는 문제로 바꾸는 것이 중요하다. 다음 아이디어를 생각해보자. 어떤 리스트를 오름차순으로 "정렬"한다는 것은 크기가 작은 순서부터 큰 순서대로 배열한다는 것이다. 그렇다면 정렬 리스트에서 제일 마지막 값은 최댓값이고 제일 첫 번째 값은 최솟..
가장 긴 증가하는 부분 수열-2 O(N log N) 알고리즘 이 문제는 풀면서 고민을 많이 했던 문제이다. N의 범위가 1000000 미만인데, 이렇게 되면 O(N^2)알고리즘으로는 택도 없다. 먼저 O(N^2)알고리즘을 연구해보자. n = int(input()) a = list(map(int, input().split())) dp = [1 for i in range(n+1)] for i in range(n): for j in range(i): if a[j] < a[i]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) 여기에서 시간을 잡아먹는 요인은 무엇일까? 바로 a[j] < a[i]인 부분을 판별하기 위해 반복문을 돌리는 것이다. 만약 a[j] < a[i]인 것을 어떤 형식으로 기록해 놓는다면 어떨까? 이 아이디어를 통해 LIS ..
냅색 연습-2293 동전1, 1535 안녕 먼저, 오랜만에 올리는 PS 일지인 만큼 초심으로 돌아가고자 하여 동적계획법을 연습해보았다. 그리고 언어를 python으로 하였는데, 이전에는 C++로 하였지만 다니는 학교에서 python을 사용하여 python으로 문제를 풀게 되었다. 문법상 구조는 거의 비슷하니 C++에서 python으로 넘어가는 것은 C언어를 처음 배울 때 보다는 어렵지 않았다고 느꼈다. 문제를 분석해보자 n가지 동전이 있다. 각 n가지 동전은 서로 다른 가치를 가지고 있다. 이 동전들을 여러 번 사용하여 k라는 가치를 만드는 방법의 수를 구하는 문제이다. 냅색이라고 하기엔 애매하지만, 냅색이랑 거의 비슷한 구조를 지닌다고 느꼈다. 문제를 분해하여 생각하면 좋을 것 같다. dp[k] += dp[k-coin[i]]가 핵심적인 문제 분..
[일상]어이어이 페놀 처신잘하라고 허 nypc끝나고 티스토리 올립니다(얼마만이냐 ㄹㅇ) 어떻게 됬냐고요? 예선특별상입니다. 음 원래 풀이 올리려고했는데 귀차니즘이 발동했고 너무 삽질을 많이한게 있어서 그리고 요즘 안쓴이유가 nypc 끝나고 나서 PS는 잠시 내비두고 과학을 공부하고 있었습니다. 무슨 대회 준비 때문에...(현재진행형) 어쨌든 복귀입니다 하하하 아니 그것보다 과학하는 동안 PS 감 떨어진거 아니야? 뭐 골3따리라서 떨어질 것도 없긴한데요 쨌든 그렇습니다. ㅎㅎ + 광기의 니체님 블로그 구독해주세요! + 여카기님 팬이예요!

티스토리툴바