전체 글
-
[백준 / Python] 1697번 숨바꼭질 | 초코더알고리즘/백준 2020. 2. 6. 13:37
https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 접근법 기존의 bfs방식에서 이동할 수 있는 방법인 (x+1,x-1,x*2)에서 고려해주는것이 포인트입니다. 그리고 옮긴 좌표에 해당하는 ..
-
[백준 / Python] 10973번 이전 순열 | 초코더알고리즘/백준 2020. 2. 6. 13:32
https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 나의 풀이 n = int(input()) a = list(map(int, input().split())) def next_permutation(a): n=len(a)-1 i = n while i>0 and a[i-1]
-
[백준 / Python] 10972번 다음순열 | 초코더알고리즘/백준 2020. 2. 6. 13:31
https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 나의풀이 n = int(input()) a = list(map(int, input().split())) def next_permutation(a): n=len(a)-1 i = n while i>0 and a[i-1]>=a[i]: i-=1 #만약 i가 0이라면 리스트가 완벽한 내림차순이므로 False리턴 if i==0: return False #값을 swap j = n while a[i-1]>=a[j]: j-=1 a[i-1],a[j]=a[j],a[i-1] #..
-
[백준 / Python] 1918번 후위 표기식 | 초코더알고리즘/백준 2020. 1. 30. 15:02
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식은 주어지지 않는다. 표기식은 알파벳 대문자와 +, -, *, /, (, )로만 이루어져 있으며, 길이는 100을 넘지 않는다. www.acmicpc.net 접근법 피연산자를 만나는 경우는 바로 출력해주었습니다. 연산자의 우선순위를 지정해주는 것이 핵심이었습니다. 스택에 들어있는 연산자의 우선순위가 비교하려는 연산자의 우선순위보다 같거나 높은경우가 있으면 모두 pop()해주고난후 비교하려는 연산자를 마지막에 추가해줍니..
-
[백준 / Python] 1935번 후위 표기식2 | 초코더알고리즘/백준 2020. 1. 30. 14:58
https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이는 100을 넘지 않는다) 그리고 셋째 줄부터 N+2번째 줄까지는 각 피연산자에 대응하는 값이 주어진다. (3번째 줄에는 A에 해당하는 값, 4번째 줄에는 B에 해당하는값 , 5번째 줄에는 C ...이 주어진다, 그리고 피연산자에 대응 하는 값은 정수이다) www.acmicpc.net 나의 풀이 import sys n=int(input()) str=input() nums=[0]*n for i in range(n): ..
-
[백준 / Python] 17298번 오큰수 | 초코더알고리즘/백준 2020. 1. 30. 14:57
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 나의풀이 n = int(input()) nums = list(map(int, input().split())) stack = [] ans = [-1 for _ in range(n)] for i in range(len(nums)): #스택이 비지 않았으면서, 다음수가 해당수보다 크면 while len(stack)!=0 and nums[stack[-1]] < nums[i]: #ans[(stack.pop()=현재 수에..
-
[백준 / Python] 10799번 쇠막대기 | 초코더알고리즘/백준 2020. 1. 30. 14:54
https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다. 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다. 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다. 레이저는 어떤 쇠막대기의 양 끝점과 www.acmicpc.net 코드에 각 줄마다 세세히 주석을 달아놓았습니다! 저는 이문제를 풀때 막대기의 괄호와 레이저의 괄호가 헷갈려서 레이저괄호를 그냥 다른 ..
-
[백준 / Python] 10866번 덱 | 초코더알고리즘/백준 2020. 1. 30. 14:51
https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 나의풀이 import sys n=int(input()) do=[] deque=[] for _ in range(n): do.append(sys.stdin.readline().split()) for i in range(len(do)): if do[i][0]== 'push_front': deque.insert(0,do[i][1]) elif do[i][..