All Good

전체 글 - Table of Contents332

★Greedy Intermediate I - 20 Solved★ 🧍‍♂️ greedy 중급문제는 전형적인 greedy 대표 예제 모음이라고 생각하면 쉽다! greedy 유형은 주어진 상황에서 다양한 선택지가 있을 때 당장의 최적의 선택지를 구한 결과를 연속할 때 그 결과가 곧 최적의 결과가 된다는 내용이다. 이 때 중요한 건, 나올 수 있는 모든 상황을 정해 놓고, 그 상황에서 최적의 상황을 연속해서 구한 상황의 결과 모음이 곧 전체의 최적 상황이어야 한다는 전제가 깔려 있다. ★ 6752 Time on task ★ T = int(input()) C = int(input()) times = [int(input()) for _ in range(C)] n = 0 times.sort() for time in times: T -= time if T < 0: break n +.. BOJ/🥈 2022. 12. 5.
★Greedy Upper-Beginner I - 9 Solved★ ★ 10162 전자레인지 ★ T=int(input())a=T//300flag=0for i in range(a,-1,-1): after_A=T-i*300 b=after_A//60 for j in range(b,-1,-1): after_B=after_A-j*60 if after_B%10==0: flag+=1 k=after_B//10 print(i,j,k) break if flag==1: breakif flag==0:print(-1) 🍇 greedy 관점 분석: 개별 상황) A / B / C 버튼을 누르는 상황: 종합 상황) A / B / C 버튼을 여러 번 눌러 T ti.. BOJ/🥉 2022. 12. 2.
★Implementation&Simulation Intermediate I - 20 Solved★ ★ 2941 크로아티아 알파벳 ★ s=input()for c in ['c=','c-','dz=','d-','lj','nj','s=','z=']: if c in s:s=s.replace(c,'*')print(len(s)) 🌳 replace()★ 1316 그룹 단어 체커 ★ import sysinput=sys.stdin.readlinet=0for _ in range(int(input())): s=input() f=0 for i in range(1,len(s)): if s[i]!=s[i-1]: if s[i] in s[:i]: f+=1 break if f==0:t+=1print(t)★ 1213 팰린.. BOJ/🥈 2022. 11. 28.
★Math & Geometry Intermediate I - 13 Solved★ ★ 1676 팩토리얼 0의 개수 ★ 🧘🏼‍♂️ 뒤에서부터 거꾸로 일일이 0의 개수를 문제대로 찾는 brute-forceN = int(input())fac = 1for i in range(N, 0, -1): fac *= icnt = 0for num in str(fac)[::-1]: if num == '0': cnt += 1 else: breakprint(cnt) 🧘🏼‍♂️ 그러나, 수학적으로 접근해서 brute-force가 아닌 수학 풀이로 시간을 더 단축하자면, 🧘🏼‍♂️ 팩토리얼 결과 끝의 0의 개수 → 10으로 나누어지는 횟수의 개수 → 5와 2의 개수 → 5의 개수① 10으로 나누어떨어진다면 끝에 0이 1개, 100으로 나누어떨어진다면 끝에 .. BOJ/🥈 2022. 11. 22.
★BF Intermediate I - 14 Solved★ ★ 1436 영화감독 숌 ★ N = int(input()) cnt = 0 start = 666 while 1: if '666' in str(start): cnt += 1 if N == cnt: print(start) break start+=1 else: start+=1 🧕🏼 말 그대로 brutal하게 일일이 모든 경우의 수에서 666 포함 여부를 따지는 문제 → 최소한의 시간 단축을 위해 break를 넣었고, 666부터 시작하게 코드 설정 🧕🏼 위의 풀이는 ①cnt 변수를 따로 만들어 1부터 추가하며 체크하는 구조이나, 아래의 풀이는 ②N 자체에서 1씩 감소하며 체크하는 구조 ※ while N 풀이가 신박해서 가져왔음 ※ N = int(input()) cnt = 0 start = 665 while N: .. BOJ/🥈 2022. 11. 21.
★Sorting Intermediate I - 18 Solved★ ★ 1181 단어 정렬 ★ import sysinput = sys.stdin.readlinew = set()for _ in range(int(input())): w.add(input().rstrip())w = list(w)w.sort()w.sort(key=len)#words.sort(key=lambda x:len(x))print('\n'.join(w))#for word in words:# print(word) 🚀 ① 같은 단어 한 번만 출력 - 중복 x - set() 사용② 사전 순 정렬, 짧은 것부터 정렬 - sort() 사용 🚀 ① set() 사용한 뒤, add method를 사용해 중복이 배제된 단어 set() 생성※ 먼저 길이 짧은 것부터 정렬하고, 사전 순 정렬이므로, A → B .. BOJ/🥈 2022. 11. 20.
★Math Beginner III - 30 Solved★ ★ 9366 삼각형 분류 ★ for i in range(int(input())): a,b,c=map(int,input().split()) l = [a,b,c] l.sort() s = set(l) if l[2] < (l[0]+l[1]): if len(s) == 1: print(f'Case #{i+1}: equilateral') elif len(s) == 2: print(f'Case #{i+1}: isosceles') elif len(s) == 3: print(f'Case #{i+1}: scalene') else: print(f'Case #{i+1}: invalid!') 🤴 set()이라는 연산자를 통해서 set() 결과의 길이에 따라 삼각형을 분류! 삼각형의 결정조건: 제일 긴 길이 < (나머지 두 변 길.. BOJ/🥉 2022. 11. 18.
★Sorting Upper-Beginner I - 8 Solved★ ★ 10989 수 정렬하기 3 ★ import sysinput = sys.stdin.readlineN = int(input())l = [0]*10000for _ in range(N): n = int(input()) l[n-1] += 1cnt = 0for x in l: cnt += 1 if x != 0: for _ in range(x): print(cnt) 👯‍♂️ 메모리 8MB, 시간 제한 5초로 메모리 & 시간 모두 신경써야 한다 ① 최대 천만 개의 수를 입력받아야 하므로 대량의 입출력 → 빠른 입출력 해결 - sys.stdin.readline 사용 ② 입력되는 수의 크기가 10,000보다 작거나 같다 → 총 10,000개의 원소가 담긴 자연수별 .. BOJ/🥉 2022. 11. 14.
(useful) Methods 😲 파이썬에는 정말 다양하고 유용한 method가 존재한다. 여러 코딩 문제를 풀면서 다양한 method를 활용해보았는데, 이번 포스팅을 통해 처음 보는, 유용한 method만 골라 간단히 정리하고자 함 :) #rjust 😲 지정한 첫번째 인자 글자 길이만큼 문자열이 오른쪽으로 나열 - 그 앞의 공간은 두번째 인자로 채워짐 print('abcd'.rjust(5,"0")) #'0abcd' #zfill 😲 위 rjust()와 비슷하되, 0이 채워진다고 생각하면 됨 → zfill syntax string.zfill(len) #'Required. A number specifying the desired length of the string'# → len 개수만큼의 문자열이 만들어지고, 기존 문자열이 차지하는 자.. Python/Fundamentals 2022. 11. 13.
★hashing 상급 - 1문제()★ 🥂 hash 정리 포스팅 https://sh-avid-learner.tistory.com/194 🥂 hashing 개념 자체가 고난이도로 상급 이상의 난이도 문제로 많이 구성되어 있다. hashing 기초부터 상급 문제까지 모두 아울러 문제를 풀어보자 ★ 15829 Hashing ★ 🥂 최대한 충돌이 적게 일어나게끔 만든 hash function 구현 유형 → 1) 영어소문자문자열에서 (a부터 시작하는 0번 ~) 31의 알파벳 번호 지수승 → 2) input 길이가 증가할 때마다 0부터 커지는 정수 → 1)과 2)를 곱한 누적합에 1234567891을 나눈 나머지 input() key = input() alphas = 'abcdefghijklmnopqrstuvwxyz' i,ans=0,0 for l in .. BOJ/🥇 2022. 11. 6.
hash table / hashing * hash table 🤗 반드시 알아야 할 자료구조 - 해시(Hash)에 대해서 알아보자! 🤗 파이썬에서 해시 테이블은 dictionary라는 자료구조를 통해 구현할 수 있다. dict() 클래스에 구현되어 있음. ① list의 경우 숫자로만 indexing - 즉 자료 접근이 가능하지만, dictionary의 경우 key라는 특수한 index를 통해 접근 가능 ② dictionary 함수 time complexity는 대부분 O(1) 매우 빠름 ★ list vs. dictionary time complexity ★ operation dictionary list get item O(1) O(1) insert item O(1) O(1) ~ O(N) update item O(1) O(1) delete it.. Computer Science/Data Structures 2022. 11. 6.
★Implementation&Simulation Upper-Beginner I - 25 Solved★ * 2차원 배열 초기화 implementation 주의점 🙋🏻‍♂️ 2차원 배열 표현은 아래와 같이 이중 list의 형태로 표현할 수 있다: m행 n열 배열의 표현 (모든 원소 0으로 초기화)lst = [[0]*n for _ in range(m)] 🙋🏻‍♂️ 여기서 중요한 건, 2차원 배열 초기화할 때, 아래와 같은 코드로 작성해서는 절대 안됨lst = [[0]*n]*n ★ (매우 중요) 위와 같이 초기화해서는 안된다. n개의 [0]*n이 모두 같은 객체로 인식되기 때문. 즉 2차원 배열 안에 배열들을 선언하는 게 아니라 각각의 배열들을 선언. 따라서 2차원 배열에 값을 넣으면 모든 배열에 동시에 값이 바뀌게 된다! ★★ 21665 Миша и негатив ★ m,n=map(int,input().. BOJ/🥉 2022. 11. 3.

티스토리툴바