알고리즘/백준
[백준 알고리즘] 4948번 베르트랑 공준, 파이썬(python)
[백준 알고리즘] 4948번 베르트랑 공준, 파이썬(python)
2021.08.144948, 베르트랑 공준 📁 문제 출처 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 💡 생각 소수의 판별이니까 123,456 * 2 = 246912까지의 소수를 구해놓고 while문으로 소수 count 하기 🛠 나의 코드 n = 246912 arr = [True for i in range(n + 1)] for i in range(2, int(n // 2) + 1): if arr[i] == True: j = 2 while i * j
[백준 알고리즘] 4949번 균형잡힌 세상, 파이썬(python)
[백준 알고리즘] 4949번 균형잡힌 세상, 파이썬(python)
2021.08.114949, 균형잡힌 세상 📁 문제 출처 https://www.acmicpc.net/problem/4949 💡 생각 스택 사용 스택이 비어있을 때 ], )가 들어오면 no출력 후 break 그 이후는 문제 그대로 하나씩 적어 나가면서 코드 작성. 🛠 나의 코드 while True: data = input() if data == '.': break stk = [] for i in data: if i not in '[]()': continue elif len(stk) == 0: if i in '])': print('no') break stk.append(i) elif i == ']': if stk[-1] == '[': stk.pop() else: print('no') break elif i == ')': if..
[백준 알고리즘] 1021번 회전하는 큐, 파이썬(python)
[백준 알고리즘] 1021번 회전하는 큐, 파이썬(python)
2021.08.111021, 회전하는 큐 📁 문제 출처 https://www.acmicpc.net/problem/1021 💡 생각 queue.index(i)
[백준 알고리즘] 5430번 AC, 파이썬(python)
[백준 알고리즘] 5430번 AC, 파이썬(python)
2021.08.105430, AC 📁 문제 출처 https://www.acmicpc.net/problem/5430 💡 생각 일단 문제 그대로 하나씩 풀어나갔지만 시간 초과가 발생했다. 시간 초과 코드 t = int(input()) for i in range(t): p = input() n = int(input()) arr = list(map(int,input()[1:-1].replace(',', ''))) for i in p: if i == 'R': arr = arr[::-1] elif i == "D": if len(arr) == 0: break else: arr.pop(0) if arr == []: print('error') else: print(arr) deque 사용 - 시간 초과 from collections im..
[백준 알고리즘] 2164번 카드2, 파이썬(python)
[백준 알고리즘] 2164번 카드2, 파이썬(python)
2021.08.102164, 카드2 📁 문제 출처 https://www.acmicpc.net/problem/2164 💡 생각 deque 사용 🛠 나의 코드 from collections import deque n = int(input()) queue = deque() for i in range(1,n+1): queue.append(i) while True: if len(queue) == 1: print(queue[0]) break queue.popleft() queue.append(queue.popleft())
[백준 알고리즘] 18258번 큐 2, 파이썬(python)
[백준 알고리즘] 18258번 큐 2, 파이썬(python)
2021.08.1018258, 큐 2 📁 문제 출처 https://www.acmicpc.net/problem/18258 💡 생각 deque 사용 🛠 나의 코드 from collections import deque import sys input = sys.stdin.readline n = int(input()) queue = deque() for i in range(n): data = input().split() if data[0] == 'push': queue.append(data[1]) elif data[0] == 'pop': if queue: print(queue.popleft()) else: print(-1) elif data[0] == 'size': print(len(queue)) elif data[0] == 'e..
[백준 알고리즘] 6198번 옥상 정원 꾸미기, 파이썬(python)
[백준 알고리즘] 6198번 옥상 정원 꾸미기, 파이썬(python)
2021.08.106198, 옥상 정원 꾸미기 📁 문제 출처 https://www.acmicpc.net/problem/6198 💡 생각 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그다음에 있는 모든 빌딩의 옥상은 보지 못한다. 자신의 오른쪽 빌딩만 볼 수 있다. 2493과 비슷한 문제이다. 스택을 이용하지 않으면 시간 초과가 발생할 것을 알면서도 2중 for문으로 일단 풀어보았다. 시간 초과 n = int(input()) ans = 0 arr = [] for i in range(n): arr.append([i, int(input())]) for i in range(n-1): for j in range(i+1, n): if arr[i][1] > arr[j][1]: ans += 1 elif arr[i][0] < arr..
[백준 알고리즘] 1699번 제곱수의 합, 파이썬(python)
[백준 알고리즘] 1699번 제곱수의 합, 파이썬(python)
2021.08.031699, 제곱수의 합 📁 문제 출처 https://www.acmicpc.net/problem/1699 💡 생각 그 항의 최소 개수를 구하는 문제이다. n=11이라면 3^2밖에 사용하지 못한다. 그러면 dp에는 [0, 1, 4, 9] 이렇게 제곱수를 저장해주고 [::-1]해준 뒤 n -= arr[i]해주면서 결괏값을 +=1해 주는 아이디어를 떠올렸지만 틀렸다. 틀린 코드 n = int(input()) arr = [0] for i in range(1, n): if i ** 2 = a..
[백준 알고리즘] 1463번 1로 만들기, 파이썬(python)
[백준 알고리즘] 1463번 1로 만들기, 파이썬(python)
2021.08.031463, 1로 만들기 📁 문제 출처 https://www.acmicpc.net/problem/1463 💡 생각 n을 3으로 나누기 -> 안 나눠지면 -1 해주고 3으로 나누기 -> 이것도 안되면 2로 나눠주기 -> 안되면 -1 진행 오답 n = int(input()) count = 0 while n != 1: if n % 3 == 0: n //= 3 count += 1 elif (n-1) % 3 == 0: n //= 3 count += 2 elif n % 2 == 0: n //= 2 count += 1 else: n -= 1 count += 1 print(count) 위와 같은 아이디어를 세웠지만 틀렸다. 이 문제는 DP로 접근해야 한다. bottom-up방식과 dp에는 연산 횟수를 저장해줘야 하는 힌..
[백준 알고리즘] 1406번 에디터, 파이썬(python)
[백준 알고리즘] 1406번 에디터, 파이썬(python)
2021.07.311406, 에디터 📁 문제 출처 https://www.acmicpc.net/problem/1406 💡 생각 index를 사용해서 커서의 위치를 컨트롤하여 작업을 수행해야겠다는 아이디어를 떠올림 시간 초과가 발생 도저히 생각이 안 나서 스택 2개를 가지고 풀이한 것을 참고. s2은 deque를 사용하여 왼쪽에서 원소를 넣었다 뺄 수 있게 하였다. ❌ 틀린 코드 import sys words = list(sys.stdin.readline().strip()) n = int(sys.stdin.readline()) index = len(words) for i in range(n): order = sys.stdin.readline().strip().split() if order[0] == "P": words.ins..
[백준 알고리즘] 1373번 2진수 8진수, 파이썬(python)
[백준 알고리즘] 1373번 2진수 8진수, 파이썬(python)
2021.07.311373, 2진수 8진수 📁 문제 출처 https://www.acmicpc.net/problem/1373 💡 생각 내장 함수를 안 쓰고 단순 계산으로 풀기로 결심 2진수 -> 8진수 2진수의 숫자를 3자리씩 묶기(앞쪽 부분 모자라면 0으로 채우기) 3자리씩 묶은 숫자에 2진수의 자리값을 곱하기 곱한 값을 더하면 8진수 위 방법으로 코드로 구현했지만 자꾸 틀린다... 뭘까..ㅋㅋㅋ 무튼 내장 함수 짱.. 🛠 나의 코드 n = int(input(), 2) # 10진법으로 변경 print(format(n, 'o')) # oct 8진법으로 변경 ✔️ 배운 점 및 주의할 점 다른 방식으로 풀어도 시간 초과가 발생했다. 내장 함수로만 풀어야지 통과가 되는 것일까...? 결론은 내장 함수의 편리함을 깨달았다. 121..