이것 저것 올리는 곳

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 식에서 적절하게 괄호를 넣어 가장 작은 숫자를 만들면 되는 문제다. 그리디 문제라 간단한 규칙만 찾으면 되는 문제다. 55-50+40 예시 입력이 이렇게 있을 때, -가 나오기 전에 나왔던 모든 숫자들을 더해서 -가 나온 순간부터 뒤에 있는 모든 숫자들의 합을 빼면 된다. 정답 import re num = input() plus_minus = [] for c in num : if not..

알고리즘 문제풀이 2023. 6. 9. 16:38

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 n을 입력받고 1 빼기 2로 나누기 3으로 나누기 이 3가지를 가장 적게 사용해 1로 만드는 문제이다. DP공부하면서 처음 푼 문제인데 이해하기가 정말 어려웠다. n=5라고 했을 때 (d[1]은 0으로 초기화되어 있다.) d[2] d[2-1] + 1 = 1 d[2/2] + 1 = 2 d[2/3] + 1 = 불가능 초록색 값이 가장 작으므로 d[2]의 값은 1이다. 그럼 지금까지 d는 [0, 0, 1] d[3] d[3-1] + 1 = 2 d[3/2] + 1 = 불가능 d[3/3] + 1 = 1 이것도 가장 ..

알고리즘 문제풀이 2023. 6. 9. 02:27

백트래킹 공부 겸 풀어본 문제 문제 경우의 수 출력 문제다. DFS로 풀었다 처음 짜보는 DFS코드라 어려움이 있었다..ㅎ 정답 def dfs(deepth, n, s) : if deepth == m : print(' '.join(s)) else : for i in range(1, n+1, 1) : if not str(i) in s : s.append(str(i)) dfs(deepth+1, n, s) s.pop() n, m = map(int, input().split()) ans = [] dfs(0, n, ans) 재귀 함수 문제를 풀며 단련된 나의 두뇌 하지만 재귀함수 안에 for문이 들어가니 다시 처음부터 공부하는 느낌이다. 복학할 때까지 알고리즘만 빡시게 파야겠다

알고리즘 문제풀이 2023. 6. 7. 23:16

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 어려웠다. 처음엔 문제 밑에 있는 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. ..

알고리즘 문제풀이 2023. 6. 7. 16:34

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 정답 n = int(input()) num = list(map(int,input().split())) num2 = list(set(num)) num2.sort() num_dict = {} for i in range(len(num2)) : num_dict[num2[i]] = i answer=[] for i in num : answer.append(s..

알고리즘 문제풀이 2023. 6. 6. 21:30

https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 고민만 삼십 분 정도 했던 문제인 거 같다.. 정답 def check_left_wall(idx, world) : for k in range(idx-1, -1, -1) : if world[k] > world[idx] : return True return False def check_right_wall(idx, world) : for k in range(idx+1, len(world..

알고리즘 문제풀이 2023. 6. 6. 20:44

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net N개의 포켓몬 이름을 입력받고 M개의 찾을 포켓몬 이름 혹은 인덱스 번호를 입력하면 인덱스 혹은 이름을 출력해 주면 되는 문제다. 정답 import sys n, m = map(int, input().split()) pokemon_int = {} pokemon_string = {} for i in range(0, n , 1) : pokemon_int[i] = sys.st..

알고리즘 문제풀이 2023. 6. 6. 19:14

오랜만에 백준 문제를 풀었다. https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 낼 수 있는 오류는 다 내고 풀었다 ㅋㅋ 정답 string = input() stack = [] for c in string : stack.append(c) ppap = ['P', 'P', 'A', 'P'] if stack[-4:] == ppap : stack.pop() stack.pop() stack.pop() stack.pop() stack.append("P") string = ''.join(stack) if st..

알고리즘 문제풀이 2023. 6. 2. 15:23