[백준/6236] 용돈 관리 | 이진 탐색 트리 | 분할 | 파이썬
·
PS/BOJ&Programmers
https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 이진 탐색 / 이진 탐색 트리를 공부하고 첫 활용 문제를 풀어봤다. 이 문제가 왜 이진 탐색이냐면 N일 동안 사용하려고 계획한 금액에 맞게 최소 K 값을 구해야 하는데, 이때 K원은 M번에 맞춰서 출력이 해야 하기 때문에 분할 개념으로 최소 K가 나올 때까지 탐색을 하기 때문이다. 분할(partition) 분할은 말 그대로 여러 개로 나눈다는 뜻인데, 이산수학에서의 분할은 보통 집합의 분할을 뜻한다. ..
[백준/5430] AC | deque의 reverse() | reverse를 여러 번?
·
PS/BOJ&Programmers
괜히 난이도가 높은 게 아닌 듯한 문제 자료구조를 정확하게 이해하고, 효율적으로 사용할 줄 아는지 체크하기 좋다. 처음 작성한 코드 t = int(input()) for _ in range(t): p = input() n = int(input()) li = list(map(int, input()[1:-1].replace(',', ''))) for p_i in p : # R : 순서 뒤집기 if p_i == 'R': li = sorted(li, reverse= True) elif p_i == 'D': if len(li) == 0 : print('error') else: li.pop(0) print(li) 문제 1. replace는 단순히 변환해주는 함수라서 그대로 문자열임. split은 리스트 반환. 문제..
[백준/1021] 회전하는 큐 | python deque | dequed의 rotate()
·
PS/BOJ&Programmers
파이썬 deque deque는 문제풀이에서 종종 사용했었지만 주요 내용을 다시 한번 정리해보았다. 알고리즘 파이썬 deque 자료구조를 알고있다면 어렵지 않게 해결할 수 있다. 최종코드 from collections import deque n,m = map(int, input().split()) que = deque(range(1,n+1)) idx = list(map(int, input().split())) cnt = 0 for i in idx: # 다 찾을 때까지 수행 while True: # 찾고자 하는 값의 위치가 중간보다 왼쪽인 경우 if que.index(i)
[백준/15821] 낚이고 낚아라 | 배열 2칸씩 묶기 _ range()의 활용
·
PS/BOJ&Programmers
알고리즘.. 나의 생각 🐤 이 문제 내용 자체가 흥미로워서 비행기에서도 계속 아이패드로 풀이를 생각해봤다. 내가 생각한 첫 번째 알고리즘은 원 둘레를 이용하는 것이었다. 하지만 계산을 해보니, 엉터리 풀이라서 깔끔하게 안녕.. 그 다음엔 원 넓이를 이용한 알고리즘을 생각했다. 1, 2, 3, 4분면에 입력 받은 점 중 최댓값을 골라서 그만큼의 길이를 반지름으로 만들어주면 되겠다!가 결론이었다. 그럼 내 메모에서 빨간 점들과 원점 사이의 거리가 가장 큰 값이 낚시 거리가 되겠다. 알고리즘 생각은 잘 했는데 구현을 스스로 하지 못했다. 그 이유는 1. 연속적으로 입력되는 값들의 좌표 표현 x y 좌표가 연속적으로 들어오는데 이걸 좌표로 어떻게 표현을 해야할 지 몰랐다. 홀수 번째에 있는 건 y 좌표, 짝수 ..
[백준/10819] 차이를 최대로 | 모든 순서를 고려한 배열.. permutation | 리스트 갱신법이 항상 효율적일까?
·
PS/BOJ&Programmers
알고리즘 1. 모든 배열 케이스를 확인해주기 위해서 permutarion으로 배열 케이스를 모두 생성해준다. 2. 생성된 배열 케이스의 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|를 확인해준다. 최종코드 from itertools import permutations n = int(input()) li = list(map(int,input().split())) per = permutations(li) ans = 0 for i in per: case = 0 for j in range(1, len(i)): case += abs(i[j-1] - i[j]) if case > ans: ans = case print(ans) 알게된 점 1. 모든 순서를 고려한 ..
[백준/3029] 경고 | 파이썬
·
PS/BOJ&Programmers
📝 3029 경고 파이썬 알고리즘 시간 계산을 할 때 주의할 점은 24시간이 넘어갔냐 아니냐를 컴퓨터가 판단하도록 지시해야 하는 것이다. 20시와 4시는 숫자만 봤을 때 당연히 20이 더 크지만, 만약 다음날 4시를 뜻하는 거라면 4시가 더 늦은 시간이기 때문에, 이를 컴퓨터가 알아차리도록 해야 한다. 이 문제의 예시에는 두 가지 케이스가 잘 나와있다. 첫 번째 케이스는 다음날 새벽 4시를 뜻하므로 이미 24시간이 넘어간 경우이기 때문에 이를 계산할 때 주의해야 한다. 두 번째 케이스는 같은 날 오후를 뜻하므로 그냥 계산해도 상관없다. 🕰 넘어간 24시간은 어떻게 표현할 수 있을까 만약 24(시) * 60(분) * 60(초) = 86400을 넘어간다면 00:00:00 ~ 23:59:59 로 표현할 수 있..
[백준/15656] N과 M(7)
·
PS/BOJ&Programmers
(1,3) (3,1)같은 경우도 모두 출력(중복 순열)을 해주어야 하기 때문에 파이썬 itertools의 product를 사용했다. 1번 코드 from itertools import product as p n,m = map(int,input().split()) num = list(map(int,input().split())) num.sort() num = map(str, num) ans = map(' '.join, p(num, repeat=m)) print('\n'.join(ans)) 2번 코드 from itertools import product as p n,m = map(int,input().split()) num = sorted(list(map(int,input().split()))) for i i..
[백준/11383] 뚊 | 2차원 이미지 | 행렬 한줄씩 걷어내기(?)
·
PS/BOJ&Programmers
📝 알고리즘 처음에 문자열로만 생각해서 못 풀었는데 문제를 정확하게 읽어야 한다. N x M 크기의 '이미지'와 N x 2M 크기의 '이미지'가 주어지는 거라서 행렬로 생각하는 게 더 수월하다. 처음에 헷갈렸던 점은 일단 큰 for문 안에서 비교를 해야 하는데 입력이 NxM크기의 이미지가 먼저 들어온 다는 거다. 그러면 for _ in range(n): img1 = input() img2 = input() 이런식으로도 받을 수 없기 때문에..(리스트인 경우도 마찬가지) n,m = map(int,input().split()) img1 = [input() for _ in range(n)] img2 = [input() for _ in range(n)] 이렇게 한 줄 for문으로 입력을 받아주었다. 또한, im..
[백준/1942] 디지털시계 | 1초씩 증가 => while t += 1
·
PS/BOJ&Programmers
🤓 시간 표현(시,분,초) 시/분/초를 나눠서 구현해야 하는 문제는 알고리즘을 모르면 꽤 돌고 돌아서 구현을 하는 경우가 생긴다. (유경험자) 이 문제에서는 3으로 나누어 떨어지는 시계 정수의 개수를 구해야 하지만, 시간 문제를 푸는 방법에 집중하여 포스팅하려 한다. (복습용으로..🤓) 시: 0부터 24까지의 숫자로 나타낼 수 있음. 60분에 1시간이므로 분값이 60으로 증가되었을 때, 분 변수는 0으로 초기화되고 시 변수는 +1 분: 0부터 60까지의 숫자로 나타낼 수 있음. 60초에 1분이므로 60초가 되었을 때 초 변수는 0으로, 분 변수에는 +1 추가 초: 0부터 60까지의 숫자로 나타낼 수 있음. # 표현 방법 if s1 == 60 : m1 += 1; s1 = 0 if m1 == 60 : h1 ..
[백준/2309] 일곱 난쟁이 | sorted()를 반복문의 대상으로
·
PS/BOJ&Programmers
📝 알고리즘 들어오는 순서에 상관없이 숫자 7개의 합을 100으로 맞춰야 하기 때문에 파이썬 itertools의 combinations를 사용했다. 알고리즘은 잘 생각했는데 출력물이 깔끔하지 않아서 아쉬웠다. 당장 생각나는 게 이 코드여서 제출을 하고, 다른 사람의 코드를 보니 sorted를 for문의 반복횟수로 지정해주었다. 파이썬 for문은 어떤 시퀀스(sequence)를 반복하는 문법이므로 sorted가 반복횟수가 될 수 있는 것이다. 💻 최종 코드 from itertools import combinations as comb t = [] h = 0 for _ in range(9): t.append(int(input())) for i in comb(t,7): if sum(i) == 100: i = l..
[백준/10809] 알파벳 찾기 | find() 찾고자 하는 문자의 인덱스를 반환
·
PS/BOJ&Programmers
📝 알고리즘 파이썬 내장함수 find와 아스키코드를 활용하여 문제를 풀 수 있다. find 함수는 해당 문자열에서 괄호 안의 문자가 몇 번째에 나타나는지 인덱스를 반환한다. 만약, 해당 문자가 없다면 -1을 반환한다. 소문자 a부터 z까지의 아스키 코드 넘버는 97부터 122까지다. (대문자 A to Z는 65 ~ 90이다.) 💻 전체 코드 s = input() alpha = list(range(97,123)) # a ~ z for i in alpha: print(s.find(chr(i))) 소문자 알파벳 전체를 아스키 코드로 (97번부터 122번까지) 리스트에 저장한다. 저장된 소문자 알파벳 아스키 코드를 for문으로 돌면서 포함되었는지, 아닌지 확인해주면 된다!
[백준/1436] 영화감독 숌
·
PS/BOJ&Programmers
처음 작성한 코드 처음에 숫자를 while 문에서 계속 +1 해주고 idx를 설정해서 n번째가 나오면 break를 해주는 코드를 작성했다. n = int(input()) i = 0 num = 665 while True: num += 1 s_num = str(num) i += 1 if '666' in s_num and i == n: print(s_num) break 근데 이렇게 하니까 무한 루프에 걸려서 동작을 제대로 안한다. 코드를 보면 검사할 필요가 없는 idx 번호까지 즉, 종말의 숫자가 아닌 것까지 카운트를 하기 때문에 잘못된 구현이기 때문이다. 최종코드 n = int(input()) i = 0 num = 665 while True: num += 1 s_num = str(num) i += 1 if ..
[백준/4949] 균형잡힌 세상 ( 파이썬 )
·
PS/BOJ&Programmers
📝 알고리즘 전형적인 스택 문제다. 우선 괄호의 여는 부분이 왼쪽으로 와야 하기 때문에, 문자열을 돌면서 ( 나 [ 일 때 스택에 넣어준다. 만약 스택에 값이 들어있는데 )나 ]가 들어오면 ( or [ 와 짝이 맞아야 하므로, 스택의 탑(stack[-1])을 통해 쌍이 맞는지 확인하고, 쌍이 맞다면 스택에서 여는 괄호를 팝해서 스택을 비워준다. 쌍이 아니라면 스택에 닫힌 괄호를 넣어준다. 이 알고리즘을 입력 받은 문자열을 모두 검사할 때까지 반복한다. 💻 최종 코드 while True: s = input() if s == '.': break stack = [] for i in range(len(s)): if s[i] == '(' or s[i] == '[': stack.append(s[i]) elif s[..
[백준/1181] 단어 정렬 (파이썬)
·
PS/BOJ&Programmers
아주 기본적인 것들을 충실하게 물어본 문제다. 이런 컴팩트한 문제..! 너무 좋음 정렬을 하는데 조건이 2개 이상이면 이중 for 문이나 if 문을 사용해도 되지만, lambda 함수를 사용하여 깔끔하게 정리할 수 있다. 이 문제를 풀기 위해 알아야 하는 파이썬 기초 개념 lambda(익명함수) set 자료형은 중복을 제거할 수 있으나, 순서가 없기 때문에 list(set(arr)) 형식으로 종종 사용된다. (정렬이 필요할 때) set 자료형은 순서가 없기 때문에 정렬이 불가능하기 때문이다. python sort와 sorted 차이 [Python] 파이썬 정렬 심화, lambda(익명함수) 함수 -파이썬 정렬 정렬 메소드인 sort()와 함수 sorted()는 디폴트 값이 오름차순이고, 내림차순으로 정렬..
[백준/14592] 2017 아주대학교 프로그래밍 경시대회(small) - 파이썬
·
PS/BOJ&Programmers
📝 알고리즘 그냥... 완전 탐색으로 풀었다.. N의 크기가 1= n: print(t.index(min(t))+1) break else: print(cnt.index(min(cnt))+1) break else: print(total.index(max(total))+1) break count 함수는 문자열이나 list에만 사용할 수 있다. 처음에 문자열에만 사용 가능하다 생각하고 map(str, list)랑 map(int,list)를 번갈아 가며 해주었다. 똥코드 😆. 코테였다고 생각하니까 끔찍하다. 매일매일 배우는 게 중요하지.. 코테까지만 잘 하면 된다!! 하나씩 구현하면서 코드를 정확하게 구현하는 법을 익혀야겠다. 내가 쓴 코드도 계속 보니 고칠 점이 많았다.. 더 많이 공부해서 잘하고싶다 흑
sebinChu
'PS/BOJ&Programmers' 카테고리의 글 목록 (4 Page)
상단으로

티스토리툴바