본문 바로가기

알고리즘/백준알고리즘

[백준 알고리즘/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..
알고리즘/백준알고리즘 2021. 12. 18. [백준 알고리즘/Python3] 9093 단어 뒤집기 문제 이해 문자열을 " " 기준으로 자르고 자른 문자열을 거꾸로 돌리면 됩니다. 코드 test_case = int(input()) while(test_case): list = [] sentence = input().split() for i in sentence: for j in range(1, len(i)+1): print(i[-j],end='') print(end=' ') test_case -= 1 다른 사람 코드 T=int(input()) for i in range(T): sentence= list(input().split()) for j in sentence: print(j[::-1],end=" ") 좀 더 파이썬 스럽습니다. arr[A:B:C]의 의미는, index A 부터 index B 까지 C..
[백준 알고리즘/Python3] 15649 N과 M(1)
알고리즘/백준알고리즘 2021. 12. 10. [백준 알고리즘/Python3] 15649 N과 M(1) 문제이해 처음 문제를 이해하는대 어려웠습니다. DFS의 계념만 이해하고 있었지 실제로 구현해보지 않아서 다른 사람의 DFS 코드를 보고 공부한 후 문제를 풀었습니다 백트레킹을 DFS를 이용해 풉니다. 1부터 중복된 숫자 없이 m번 수열을 만들면 됩니다. n, m = map(int, input().split()) base = [] # 재귀함수를 이용하여 m개의 수열을 저장하기 위한 리스트 def dfs(): #리스트에 들어간 수열들이 m개가 되면 #리스트에 들어있는 숫자들을 모두 출력하고 함수를 나온다. if(len(base) == m): print(' '.join(map(str,base))) return for i in range(1, n+1): if i not in base: # 리스트 s 중복여부 확..
[백준 알고리즘/Python3] 2164 카드뽑기
알고리즘/백준알고리즘 2021. 12. 8. [백준 알고리즘/Python3] 2164 카드뽑기 문제이해 deque를 만들어서 한쪽으로 버리고, 뒤로 넣는 과정을 deque의 길이만큼 반복해야 한다고 생각 했습니다. 파이썬의 deque 라이브러리를 사용하고 popleft()와 rotate(-1)를 써서 한번은 왼쪽으로 나가게 하고 한번은 오른쪽으로 삽입을 해주었습니다. 코드 from collections import deque input_num = int(input()) #deque 만들기 def make_deq(num): deq = deque() for i in range(1, num+1): deq.append(i) return deq #카드 하나를 버리고 하나는 뒤로 넣기 def mix_card(deq): for _ in range(len(deq)): result = deq.popleft() d..
알고리즘/백준알고리즘 2021. 12. 6. [백준 알고리즘/Python3] 1085 직사각형에서 탈출 문제 이해 3개의 점 중에 2개는 무조건 평행으로 주어집니다. 그래서 중복된 2개를 제외하면 나머지 하나가 좌표값이 됩니다. 코드 x1, y1 = map(int, input().split()) x2, y2 = map(int, input().split()) x3, y3 = map(int, input().split()) x4, y4 = 0,0 if(x1 - x2 == 0): x4 = x3 elif(x2 - x3 ==0): x4 = x1 else: x4 = x2 if(y1 - y2 == 0): y4 = y3 elif(y2 - y3 ==0): y4 = y1 else: y4 = y2 print(x4, y4)
알고리즘/백준알고리즘 2021. 12. 5. [백준 알고리즘/Python3] 1085 직사각형에서 탈출 문제이해 x,y 좌표에서 (0,0)과의 최소길이 (w,h)에서 최소길이를 구하면 된다. 0 -> x 까지의 거리와 x -> w 까지의 거리중 가장 짧은 값을 고르면된다. 0 -> y 까지의 거리와 y -> w 까지의 거리중 가장 짧은 값을 고르면된다. 코드 x,y,w,h = map(int, input().split()) #x의 최소값 if(w - x > x): width = x else: width = w-x #y의 최소값 if(h - y > y): height = y else: height = h-y #x축, y축 중 가장 짧은 것 if(width > height): print(height) else: print(width)

티스토리툴바