본문 바로가기

알고리즘/알고리즘 설명61

기초 문자열 구현 🧑‍💻 기초 문자열 구현 멀티잇 코딩테스트 러닝클래스'Python 5월반 대소문자 바꾸기 단어가 주어지면, 대문자는 소문자로, 소문자는 대문자로 바꿔서 출력하는 것이다 예) input : JeJoon output : jEjOON N = int(input()) word = input() answer = '' for letter in word: if letter.isupper(): answer += letter.lower() else: answer += letter.upper() print(answer) 간단한 풀이 법 N = int(input()) word = input() print(word.swapcase()) .swapcase() 는 대문자를 소문자로, 소문자를 대문자로 바꿔주는 메서드다 단어 필터 .. 2023. 5. 4.
Udemy : 동적 계획법 (DP) Udemy : 동적 계획법 (DP) udemy 알고리즘 코딩 테스트 Dynamic Programming 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복 분할정복과 비슷한 느낌 배열 또는 딕셔너리를 만들어서, 작은 문제의 답을 넣는다 메모이제이션 (Memoization) 구현 : 재귀 | 저장방식 : 메모이제이션 (Top-down) cache 방식이라고 할 수 있고, 중복연산을 방지한다 직관적이라 코드 가독성이 좋다 재귀함수 호출이 많이 해서 느릴 수 있다 타뷸레이션 (Tabulation) 구현 : 반복 | 저장방식 : 타뷸레이션 (Bottom-up) 테이블을 채워나가는 것 필요 없는 부분 문제까지 전부 구하는 것 시간과 메모리를 좀 더 아낄 수 있다 DP 테이블 채워.. 2023. 3. 23.
Udemy : 알고리즘 이분 탐색 Udemy : 알고리즘 이분 탐색 udemy 알고리즘 코딩 테스트 이분 탐색 하나 하나 다 찾는 것이 아닌다 (완전 탐색으로 매우 오래 걸린다) Up & Down 게임이라고 생각하면 된다 정답을 기준으로, 무작위로 고른 숫자가 정답 숫자가 무작위로 고른 숫자 기준으로 더 작은지, 또는 큰지 말해주는 것이다 예) 정답 7 10을 말하면 Down 5를 말하면 Up 즉 값들을 정렬하고, 정렬한 값들 중에 중간 값을 기준으로 탐색을 하는 것이다 예) 1,2,3,4,5,6,7,8,9,10 중 8 찾기 먼저 5를 탐색한다, 7은 5보다 크기 때문에 6~10 중 숫자들을 찾는다 6~10 의 중간값은 8 from bisect import bisect_left, bisect_right array = [0, 1, 2, 3.. 2023. 3. 14.
Udemy : 알고리즘 DFS, BFS, 백트래킹 Udemy : 알고리즘 DFS, BFS, 백트래킹 udemy 알고리즘 코딩 테스트 그래프 자료구조 그래프는 노드와 링크로 이루어진 자료구조다 노드는 점들이고, 노드를 이어주는 링크, Edge 또는 간선이라고 한다 SNS / 메신저 관계도를 그래프로 만들 수 있다 지도 / 네비게이션 같이 그래프를 실생활에 사용될 수 있다 무방향 또는 방향 그래프로 만들 수 있다 무방향이나 양방향 그래프는 동일한 개념이다 트리 자료구조 순환성이 없는 무방향 그래프다 코드를 그래프로 나타날 때에는 인접 리스트와 행열을 만들 수 있다 연결 행 연결 리스트 DFS (Depth First Search) 깊이 우선 탐색 스택 또는 재귀를 사용해서 구현을 한다 DFS는 완전 탐색이다 BFS (Breadth First Search) 너.. 2023. 3. 13.
Udemy : 알고리즘 탐욕법 탐욕법 매 순간마다 최선의 경우만 골라간다 다른 경우는 고려하지 않는다. 나중은 생각하지 않는다 모든 것을 보지 않기 때문에 완전탐색보다 빠르다 무엇이 최선인지 찾는게 포인트다 규칙을 찾는게 제일 좋다 시간 초과가 안 뜨게 되면 완전 탐색으로 문제를 풀어도 된다 하지만 시간 초과가 나면, 더 효율적인 알고리즘을 찾아야 한다 2023. 3. 10.
Udemy : 알고리즘 완전탐색 Udemy : 알고리즘 완전탐색 udemy 알고리즘 코딩 테스트 완전탐색 존재하는 모든 경우의 수를 탐색을 하며 결과를 도출해 낸다 장점 모든 경우의 수를 탐색하는 것이라서 반드시 답을 찾을 수 있다 단점 모든 경우의 수를 탐색하는 것이라서, 계산하는 시간이 느리다 브루트포스 완전 탐색 방법론을 사용하는 알고리즘이다 무차별 대입이라고도 한다 시간이 오래 걸려도, 답을 구할 수 있는 방법이라서, 많이 사용이 된다 순열 itertools from itertools import permutations from itertools import combinations 모든 경우의 수를 순서대로 살펴볼 때 용이하다 from itertools import permutations v = [0, 1, 2, 3] for i.. 2023. 3. 7.
Udemy : 알고리즘 자료구조 Udemy : 알고리즘 자료구조 udemy 알고리즘 코딩 테스트 배열 파이썬은 리스트를 사용한다 arr = [10, 11, 12, 13] arr[2] = 5 # output : [10, 11, 5, 13] 탐색 : O(1) 삽입/삭제 : O(N) 스택/ 큐 Stack = LIFO (Last In First Out) 리스트 안에 제일 마지막에 추가된 요소를, 제일 먼저 뺀다 즉 append를 통해서, 리스트 제일 마지막에 값을 넣는다 pop을 통해서 리스트 제일 마지막 요소를 빼낸다 맨 마지막에 요소를 추가하거나, 맨 마지막의 요소를 빼는 것이라서 삽입/삭제가 O(1) 이다 Queue = FIFO (First In First Out) 리스트 안에 제일 처음에 추가된 요소를, 제일 먼저 빼는 것 deque를.. 2023. 3. 2.

티스토리툴바