All Good

전체 글288

👀 Binary Search 👀 intro 🐧 순차 탐색 - 선형 탐색) 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 (가장 기본적인 형태 - 한 개씩 확인) 🐧 이진 탐색) 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색(시작점, 끝점, 중간점을 이용하여 탐색 범위 설정) ※ 이진 탐색은 순차 탐색에 비해 탐색 범위가 훨씬 줄어들기 때문에 시간 복잡도는 log시간을 보인다. Q. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾기 0 - 2 - 4 - 6 - 8 - 10 - 12 - 14 - 16 - 18 ① 시작점) index 0, 중간점) index 4, 끝점) index 9 → 중간점이 2개 존재한다면, 소수점은 제외한 앞부분을 설정한다 → 4가 중간점 기준 왼쪽에 존재.. Computer Science/Algorithms 2022. 12. 6.
understanding pesudo-code of QuickSort 🦢 백준 퀵 정렬 대표 문제 모음) 추후 🦢 퀵 정렬 concepts 포스팅) 추후 🦢 QuickSort pseudo-code quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p < r) then { q Computer Science/Algorithms 2022. 12. 5.
★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 Beginner I - 9 Solved()★ ★ 10162 전자레인지 ★ T=int(input()) a=T//300 flag=0 for 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: break if flag==0:print(-1) 🍇 greedy 관점 분석 : 개별 상황) A / B / C 버튼을 누르는 상황 : 종합 상황) A / B / C 버튼을 여러 번 눌러 T time에 딱 맞게 요리하기 ★ 최적의 종합 상황은 최적의 개별 상황의 모음으로 만들 수 있고, 개별 상황의 최적 greedy 솔루션.. BOJ/🥉 2022. 12. 2.
★Implementation&Simulation Intermediate I - 15 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 sys input=sys.stdin.readline t=0 for _ 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+=1 print(t) ★ 1213 팰린드롬 만들기 ★ import sys input = sys.stdin.readline name = in.. BOJ/🥈 2022. 11. 28.
★Math & Geometry Intermediate I - 8 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 - 13 Solved★ ★ 1181 단어 정렬 ★ import sys input = sys.stdin.readline w = 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 .. 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 Beginner I - 8 Solved★ ★ 10989 수 정렬하기 3 ★ import sys input = sys.stdin.readline N = int(input()) l = [0]*10000 for _ in range(N): n = int(input()) l[n-1] += 1 cnt = 0 for x in l: cnt += 1 if x != 0: for _ in range(x): print(cnt) 👯‍♂️ 메모리 8MB, 시간 제한 5초로 메모리 & 시간 모두 신경써야 한다 ① 최대 천만 개의 수를 입력받아야 하므로 대량의 입출력 → 빠른 입출력 해결 - sys.stdin.readline 사용 ② 입력되는 수의 크기가 10,000보다 작거나 같다 → 총 10,000개의 원소가 담긴 자연수별 count list를 사용 → 수가 입력될수록.. 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.
★Implementation Beginner III - 39 Solved★ ★ 1267 핸드폰 요금 ★ N=int(input()) l=list(map(int,input().split())) Y,M=0,0 for time in l: Y+=10 M+=15 if time>=30: Y+=(time//30)*10 if time>=60: M+=(time//60)*15 print(f'Y {Y}' if YM else f'Y M {Y}') 🍸 시간 간격에 따라 두 요금제의 각 요금을 계속 부과하면 됨 ★ 27294 몇개고? ★ T,S=map(int,input().split()) if S==1 or T=17:print(280) else: print(320) ★ 27328 三方比較 (Three-Way Comparison) ★ A=int(input()) B=int(input()) print(0 if.. BOJ/🥉 2022. 10. 28.
★시간복잡도 기초 - 7문제()★ * 백준 요약 → 백준 24262 - 함수 한 번에 return문 1번 실행, 배열의 indexing은 O(1) → 백준 24263 - for문 input() N번 실행, O(N) → 백준 23235 - 이미 정렬된 array를 sorting하는 데 필요한 time complexity는 O(1) → 백준 24264 - 중첩 for문 $N^2$번 실행, $O(N^2)$ → 백준 24265 - 중첩 for문 $N^2$번 실행, $O(N^2)$ → 백준 24266 - 중첩 for문 $N^3$번 실행, $O(N^3)$ → 백준 24267 - 중첩 for문 $N^3$번 실행, $O(N^3)$ ★ 24262 알고리즘 수업 - 알고리즘의 수행 시간 1 ★ print(1,0,sep='\n') ☀️ 1) 코드1의 수행횟.. BOJ/Multi-Levels 🍭 2022. 10. 23.
★Basics III - 40 Solved★ ★ 24075 計算 (Calculation) ★ A,B=map(int,input().split()) print(max(A+B,A-B),min(A+B,A-B),sep='\n') ★ 17356 욱 제 ★ A,B=map(int,input().split()) M = (B-A)/400 print(1/(1+10**M)) 🍸 ** 거듭제곱으로 ~승 연산자 이용하면 됨 ★ 20232 Archivist ★ winners = {} winners.update(winners.fromkeys([1995,1998,1999,2001,2002,2003,2004,2005,2009,2010,2011,2012,2014,2015,2016,2017,2019],'ITMO')) winners.update(winners.fromkeys([1996.. BOJ/🥉 2022. 10. 21.
★ 정밀도 연산 - 1문제 () ★ 🤾🏻‍♂️ 컴퓨터는 정수는 완벽히 표현하지만, 실수는 완벽히 표현하지 못함을 항상 주의해야 한다 🤾🏻‍♂️ 따라서, 실수 간의 연산에서 오차가 발생할 수 밖에 없고, 특히 type casting할 때 의도와 다르게 다른 수로 변환이 되기 때문에 정말 특히나 주의! 🤾🏻‍♂️ 매우 까다롭고, 복잡한,, ㅠㅠ 정밀도 연산 관련 유형만 모아놓음. ★ 15128 Congruent Numbers ★ 🤾🏻‍♂️ 문제는 매우 간단, 직각삼각형의 빗변이 아닌 두 변(non-hypotenuse legs) 각각이 분모와 분자로 주어지고, 두 변이 이루는 직각삼각형의 넓이가 정수인지, 아닌지의 여부를 따지는 문제 🤾🏻‍♂️ 틀린문제 분석 🤾🏻‍♂️ ※ 아래에서 구한 area와 int(area) 같은 지 비교 ※ ① area.. BOJ/🥉 2022. 10. 20.
★BF Upper-Beginner I - 16 Solved★ ★ 2798 블랙잭 ★ from itertools import combinations N,M = map(int, input().split()) cards = list(map(int,input().split())) groups = list(combinations(cards,3)) sum_of_group = [] for group in groups: sum_of_group.append(sum(group)) sum_of_group.sort(reverse=True) for sum_of_group_each in sum_of_group: if sum_of_group_each M: continue else: res = max(res,cards[i] + cards[j] + cards[k]) print(res) 🗽 여기.. BOJ/🥉 2022. 10. 19.
DFS / BFS ① DFS(Depth-First Search) ⚡️ 먼저 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 ⚡️ 스택 자료구조(또는 재귀함수)를 이용하며, 구체적인 동작 과정은 아래와 같다 ① 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. ② 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. ③ 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. ⚡️ 동작 예시 ※ 먼저 방문노드 / 방문기준을 정하는 게 중요 → 문제마다, 상황마다 방문노드 정하는 기준은 제각각이다 ex) 예시에서는 방문노드는 1, 방문기준은 번호가 낮은 인접노드.. Computer Science/Algorithms 2022. 10. 14.
★Implementation Beginner II - 50 Solved★ ★ 8958 OX 퀴즈 ★ N = int(input()) for _ in range(N): string = input() score = 0 add = 0 for ch in string: if ch == 'X': add = 0 continue add += 1 score += add print(score) ★ 1259 팰린드롬수 ★ while 1: N = input() if N == '0': break print('yes' if N == N[::-1] else 'no') ★ 1157 단어 공부 ★ word = list(input().lower()) ans = {} for letter in 'abcdefghijklmnopqrstuvwxyz': ans[letter] = word.count(letter) max_.. BOJ/🥉 2022. 10. 10.
★Math & Geometry Upper-Beginner I - 30 Solved★ ★ 1977 완전제곱수 ★ M = int(input()) N = int(input()) ans = [] for i in range(N-M+1): if (M+i)**(1/2) == int((M+i)**(1/2)): ans.append(M+i) if len(ans) > 0: print(sum(ans)) print(min(ans)) else: print(-1) 🤙 1부터 일일이 제곱해서 해당 범위 내에 들어가는 지 아는 방법도 있지만, 《완전제곱수 판별》 🤙 (1) for문 범위 내에서 해당 수가 완전제곱수임을 아는 방법은, 1/2승한 결과와 1/2승한 결과를 int() 취한 것과 같은 지의 여부이다 / (2) 또는 1/2승한 결과를 int() 취한 걸 다시 제곱해서 원래 수와 같은 지의 여부로도 찾을 수 있.. BOJ/🥉 2022. 10. 9.
★정렬 기초1 - 8문제()★ 🤩 정렬 기초 유형은 알려진 여러 정렬 알고리즘을 사용하는 유형이 아닌, 직접 정렬 내장 함수를 사용하거나, 단순히 최대/최소만 물어보는 매우 간단한 유형으로, 가볍게 보고 넘어가면 좋을 듯 하다! ★ 2752 세수정렬 ★ numbers=list(map(int,input().split())) numbers.sort() for number in numbers: print(number,end=' ') #or #print(numbers[0], numbers[1], numbers[2]) 🤩 정렬하면 대표적인 함수 sort()와 sorted() 🤩 또는 map()을 이용해 sorted() 결과를 한번에 string 형태로 바꾼 뒤 join()으로 빈 문자열에 한 번에 붙이는 풀이도 가능! nums = list(m.. BOJ/🥉 2022. 10. 5.
★Recursion Upper-Beginner - 3 Solved★ ★ 10870 피보나치 수 5 ★ def fibo(n): if n in [0,1]: return n else: return fibo(n-1) + fibo(n-2) print(fibo(int(input()))) 🌺 재귀를 이용해서 함수 안에 그 이전 두 동일한 함수를 또 넣어 재귀적으로 계속 함수 결과가 쌓인 최종 합은 곧 피보나치의 수가 됨 ※ 주의! n이 20보다 작거나 같으므로 재귀로 사용 가능하나(재귀의 예시를 보여주기 위해 재귀로 풀었을 뿐), n이 매우 큰 수일경우 recursion 깊이가 너무 깊어 error 발생. 이럴 때는 dp를 해결하거나 추가적인 알고리즘 장치로 해결 해야함. 별도 포스팅 참조 필요 ※ ★ 5956 Symmetry ★ def get_cows(n,m,times,cows):.. BOJ/🥉 2022. 9. 27.
🧭Recursion intro 🍓 재귀함수란, 자기 자신을 다시 호출하는 함수이다. 함수 내에 다시 함수를 불러서, 동일 함수 로직을 반복적으로(재귀적) 진행한다. DFS 구현을 위해 자주 사용되는 개념. 아래 코드 예시 참조. def recursive_function(): print('recursive call') recursive_function() recursive_function() → 무한히 출력되다가 python의 경우 'RecursionError: maximum recursion depth exceeded while calling a Python object'라는 메시지 출력 - 재귀 최대 허용 깊이가 있어 오류 메시지가 끝에 출력되며 종료. 함수를 부를 때 마다 스택 자료 구조에 함수가 계속 쌓이면서 컴퓨터 .. Computer Science/Algorithms 2022. 9. 27.
🍔stack & queue & deque 🧜‍♀️stack / queue / deque 모두 특정 위치에서만 원소를 넣거나 뺄 수 있는 restricted structure 1. stack 🧜‍♀️ 스택이란, 한 쪽으로만 데이터를 빼고 넣을 수 있는 자료구조로, 한 쪽만 구멍이 뚫려 있는 프링글스 통을 생각하면 된다. 먼저 들어온 데이터가 나중에 나가는 형식 - 즉 나중에 들어온 데이터가 먼저 나가는 형식(선입후출 FILO)의 자료구조. 입구와 출구가 동일한 형태로 매우 간단한 두 연산(원소 추가 O(1), 원소 제거 O(1))이 제공된다. 제일 상단의 원소 확인은 O(1), 제일 상단이 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능하다. 항상 스택 상단에만 초점이 되어 있음. 따라서 삽입할 때에도 가장 최근에 삽입한 원소 바로 위에 삽입.. Computer Science/Data Structures 2022. 9. 23.
Implementation 1. intro ★ 코딩의 대부분, 즉 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 ★ 어떤 알고리즘을 사용하더라도, 최종적으로는 구현을 해야 하기 때문에, 사실 모든 문제가 구현 유형이라고 할 수 있다. ★ 흔히 말하는 '구현' 문제는, 풀이를 떠올리는 건 쉽지만 직접 소스 코드로 옮기기 어려운 문제를 지칭 ① 알고리즘은 간단하나, 코드가 지나칠 만큼 길어지는 문제 (프로그래밍 언어 종류에 따라 어려울 수도, 매우 쉬울 수도 있음) ② 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 ③ 문자열을 특정 기준에 따라서 끊어 처리해야 하는 문제 (python으로 매우 쉽게 풀 수 있는 경우 많고, 대표적으로 난이도 하의 1-2번 문제 위주) ④ 적절한 라이브러리를 찾아서 사용해야 하는 문제.. Computer Science/Algorithms 2022. 9. 21.

티스토리툴바