본문 바로가기

알고리즘

알고리즘/백준알고리즘 2022. 1. 1. [백준 알고리즘/Python3] 1918 후위 표기식 문제이해 후위 표기식은 중위 표기식에서 문자,숫자를 제외한 문자를 후위에 두는 것 입니다. 이 때 각 연산자는 우선순위가 있습니다. *,/ 는 1순위 +,-는 2순위 (,)는 3순위 문자는 그대로 출력하고 스택에 연산자만 들어가게끔 합니다. 스택 연산자가 들어갈 때 스택 최상위 것의 우선순위가 현제 들어갈 문자보다 크다면 pop()을 합니다. ex) 스택에 [+,*] 이 들어가 있을 때 '-'가 들어갈 차례가 됐습니다. '*'의 우선순위는 1순위 이고, '-'의 우선순위는 2순위 이니 *를 pop()합니다. 다음 '+'와 '-' 우선순위를 비교하는데 순위가 같으니 push만 합니다. '('이 들어가면 연산의 우선순위가 높은 것이니 ')'이 나올 때까지 연산자를 pop()합니다. 코드 #연산자의 우선순위 ..
[백준 알고리즘/Python3] 1935 후위 표기식2
알고리즘/백준알고리즘 2021. 12. 31. [백준 알고리즘/Python3] 1935 후위 표기식2 문제이해 먼저 들어온 문자열에 'A'~'Z'까지 들어온 숫자로 변환해서 새로운 식을 만들었습니다. 그 다음 숫자가 들어오면 스택에 push, 문자가 들어오면 pop 해서 이전에 들어왔던 값을 계산하고 다시 스택에 push 하는 것을 만들었습니다. 그런데 체점을 하니 런타임 에러가 났습니다. 코드 import string test_num = int(input()) calculation = input() english = list(string.ascii_uppercase) stack = [] #후위 표기식에 숫자 넣기 for i in range(test_num): word = input() #replace는 변환된 문자열을 반환함 calculation = calculation.replace(english[i..
[백준 알고리즘/Python3] 17299 오등큰수
알고리즘/백준알고리즘 2021. 12. 30. [백준 알고리즘/Python3] 17299 오등큰수 문제 이해 저번에 푼 오큰수와 비슷한 양상일거라 생각했습니다. 좀 더 복잡하게 생각해봤는데... 스택에 값을 넣습니다. 스택에 값을 넣는 기준은 바로 전에 들어간 수(스택에 있는 수)가 다른 값이어야 합니다. 같은 값이면 그냥 스택에 넣습니다. 하나 넣을 때마다 스택에 같은 값이 있는지 확인합니다. 만약 같은 값이 있다면 값에 있는 인덱스까지 현재 값을 넣습니다. 이렇게 하니 틀렸다고 나왔습니다. 너무 오래 걸린 거 같습니다. 그래서 다른 풀이를 찾아봤습니다. 코드 from collections import Counter list_size = int(input()) list = list(map(int,input().split())) #수열들의 등장 횟수 체크 count = Counter(list) sta..
[백준 알고리즘/Python3] 17298 오큰수
알고리즘/백준알고리즘 2021. 12. 29. [백준 알고리즘/Python3] 17298 오큰수 문제 이해 수열에서 하나를 집고 오른쪽으로 차례대로 돌면서 큰 수가 나오면 정지하는 식으로 생각했습니다. 하지만 시간초과가 나왔습니다. 코드 list_size = input() list = input().split() result = '' for i in range(len(list_size)): stack = [] #오른쪽만 스택에 담는다. for j in range(len(list)): stack.extend(list[j+1:]) # 들어온 수의 한칸 앞부터 스택에 넣는다. if(stack == []): #스택이 끝났다면 result += '-1 ' break for k in stack: if(list[j] < k): #스택에 있는 값이 수열 j보다 작으면 오큰수 result += k + ' ' bre..
[백준 알고리즘/Python3] 10799 쇠막대기
알고리즘/백준알고리즘 2021. 12. 28. [백준 알고리즘/Python3] 10799 쇠막대기 문제이해 '()'은 레이저 '('은 쇠파이프 시작 ')' 은 쇠파이프 종료, 처음 봤을 때 스택을 이용해서 풀면 되겠다 생각했습니다. (은 모조리 스택에 넣고 ) 가 들어오면 pop을 해서 스택에 남아있는 ( 개수를 찾으면 될거라고 생각 했죠. 문제는 )) 처럼 )가 2개 나오는 경우 입니다. 만약 앞에 (가 온다면 레이저를 쏘는 것이고 )가 오는 것이라면 파이프의 끝이라는 의미입니다. 1개의 파이프가 들어와서 레이저를 맞고 끝나면 2개의 파이프가 됩니다. 레이저를 맞은 파이프는 끝날 때 +1이 된다는 것 입니다. 코드 input = list(input()) stack = [] result = 0 for i in range(len(input)): if(input[i] == '(' ): stack.appe..
[백준 알고리즘/Python3] 17413 단어 뒤집기 2
알고리즘/백준알고리즘 2021. 12. 27. [백준 알고리즘/Python3] 17413 단어 뒤집기 2 문제 이해 스택을 사용할 수 있고 문자열 자르기로 해결할 수 있습니다. 문자열 자르기로 해결해보려하다 코드가 너무 길어져서 다른 방법을 찾아봤습니다. 스택을 사용하는 방법도 있는데 파이썬으로 스택==리스트 라는 고정관념이 박혀있어서 너무 돌아가서 생각을 했습니다. 다른 분들의 풀이를 보니 문자열로 편하게 하는방법이 있었습니다😥 코드 import sys text = list(sys.stdin.readline().rstrip()) flag = False # 정상 출력은 True result = '' stack = '' # 만나면 스택이랑 합치면 된다. for i in text: #뒤집어서 출력 if flag == ..
[백준 알고리즘/Python3] 1158 요세푸스 문제
알고리즘/백준알고리즘 2021. 12. 24. [백준 알고리즘/Python3] 1158 요세푸스 문제 문제이해 리스트 하나를 만들어 두고 원형태를 생각해서 k의 값에 따라 증가하면서 리스트를 pop()하는 형태로 만들었습니다. k의 값이 초과하면 남아있는 리스트 개수의 나머지로 계산했습니다. 코드 n, k = map(int, input().split()) li = [i for i in range(1,n+1)] point = li.index(k) numerical = [] #li가 빌 때까지 한다. while(len(li)): #해당 값을 꺼낸다. result = li.pop(point) numerical.append(str(result)) #li가 비어있다면 탈출 if(len(li) == 0): break else: #k-1은 인덱스가 0부터 시작하기 때문 point = (point + (k-1)) % ..
[백준 알고리즘/Python3] 1406 에디터
알고리즘/백준알고리즘 2021. 12. 21. [백준 알고리즘/Python3] 1406 에디터 문제 이해 백준에서 파이썬으로 하면 시간 초과가 잘걸리는거 같습니다. 처음에 cursor를 구현해서 list를 통해서 pop(), insert()연산을 했더니 시간초과가 떳습니다. 왜이러지 하고 검색해본 결과 O(n)시간이 걸려서 초과가 된거였습니다. 해결방법을 알아보니 2개의 스택을 이용하는 것입니다. "왼쪽스택", "오른쪽스택" 이라고 하겠습니다. 먼저 주어진 문장을 왼쪽스택에 넣습니다. 왼쪽으로 커서를 옮긴다면 왼쪽스택에 있는것이 오른쪽 스택으로 갑니다. 오른쪽으로 커서를 옮긴다면 오른쪽스택에 있는것이 왼쪽 스택으로 갑니다. 문자를 지우려면 왼쪽 스택에 있는 top을 지우면 커서 왼쪽에 있는 것을 지우는 것과 같습니다. 커서 왼쪽에 문자를 추가하려면 왼쪽스택 top에 추가하는 것과 같습니다. 왼쪽,..
[백준 알고리즘/Python3] 1874 스택 수열
알고리즘/백준알고리즘 2021. 12. 20. [백준 알고리즘/Python3] 1874 스택 수열 문제 이해 4를 출력시킬려면 1,2,3를 스택에 미리 넣어넣고 4 push하고 다시 pop 해야 합니다. 제가 생각했던건 4를 입력 -> + + + - 가 출력 3을 입력 -> - 가 출력 한 줄에 한 개씩 출력한다 해서 이렇게 생각했는데 아니였습니다. 43687521을 입력하면 +++--++-++-----가 출력되는 형태로 만들어야 합니다. import sys test_case = int(sys.stdin.readline()) list = [] value = 1 result = [] for i in range(1,test_case+1): num = int(sys.stdin.readline()) for j in range(value ,num+1): list.append(j) print("+") value..

티스토리툴바