알고리즘11
[알고리즘] 인덱스 트리란? (IndexedTree ) / 코딩테스트 인덱스 트리 /Java 구현/
⭐ 인덱스트리란? ⭐ 리프 노드에 내가 쓸 값들을 저장해놓고, 부모들에는 해당 노드의 합들로 된 노드들을 만들어 구현해둔 트리입니다. 쉽게 말하자면 제일 밑 노드들은 값들, 그 위에 부모 노드들에는 값들의 정보(보통 노드의 부분합)를 모아둔 트리! 예시를 보시는게 좋을 것입니다. 언제 쓰이는가? 👀 인덱스 트리는 언제 쓰일까요? 1. 부분합을 계속해서 구해야할 때, 2. 특정 인덱스의 변경 또한 계속 일어날 수 있을 때 이 두 조건이 만족할 때 주로 쓰입니다! * left - right = N 이라 가정 보통 구간 left ~ right 부분합을 구한다는 것은 left 부터 right 까지를 전부 더해야 하기에 O(N) 의 시간복잡도를 가집니다. 그래서 우리는 누적합 배열을 쓰죠! 누적합 배열에서 누적합..
[백준✨] 3344번 < N-Queen > / Python 문제풀이 /
해답) N = int(input()) ''' 알고리즘의 출처 : https://en.wikipedia.org/wiki/Eight_queens_puzzle 위키 설명 읽고 그대로 코드로 옮겼습니다. The examples above can be obtained with the following formulas.[3] Let (i, j) be the square in column i and row j on the n × n chessboard, k an integer. One approach[3] is 1. If the remainder from dividing n by 6 is not 2 or 3 then the list is simply all even numbers followed by all odd ..
[알고리즘🔑] Iterative deepening Search와 Iterative lengthening Search
들어가기 앞서 BFS/DFS 에 대해 숙지하셔야 합니다. Blind Search 의 기본 원리를 알고 계셔야 합니다. Iterative Deepening Search란 iterative : 반복적인 즉, 한국 말로 '번역하자면 반복적인 깊이 탐색' 정도가 되겠네요. DFS 와, BFS 의 단점들을 보완하기 위해 고안된 search 방법입니다! 그러면 어떤 점들을 보완시켰는지 알기 전에, 먼저 DFS와 BFS의 특징들을 간단하게 알아볼까요? DFS의 특징 장점 : BFS 에 비해 메모리 소요가 적다. (BFS는 frontier 큐에 하위 노드들 전부 넣어야함) 목표해가 깊은 단계에 있을 경우, BFS 보다 훨씬 빠르다. 단점 : DFS 는 탐색트리에서 깊이가 아주 큰, 하지만 해가 해당 깊이에 없는 경우를..
[프로그래머스💯] 코딩테스트 연습 > 이분탐색 > 징검다리
해답) def solution(distance, rocks, n): rocks.sort() rocks.append(distance) answer = 0 l, r = 0, distance while l rocks[i] - prevRock: removeRock += 1 # print("removeRock") else: cand = min(cand, rocks[i] - prevRock) prevRock = rocks[i] if removeRock n: r = minDistance-1 return answer 풀이) 처음 겪는사람에겐 너무나도 어려울 수 있는 이분탐색 문제입니다.. 하지만 한 번만 이해하고 나면 나중에 나오는 문제들에는 큰 어려움 없이 수월해 질 수 있습니다! 화이팅! 키 포인트 보통 문제를 처..
[AlgoSpot] 알고스팟 > WILDCARD(와일드카드) - Python 문제풀이 👀
해답) import sys def readline(): return sys.stdin.readline() def solution(w_str, i_strs): answer = [] for i_str in i_strs: if isMatched(w_str, i_str): answer.append(i_str) for answerStr in sorted(answer): print(answerStr) return 0 def isMatched(w_str, i_str): if len(i_str) == 0 and len(w_str) == 0: return True if len(w_str) == 0: return False if w_str[0] == '*': if len(i_str) == 0: return isMatche..
[알고리즘] Approximation Algorithm 이란 / NP 문제 알고리즘
Approximation Algorithm 이란 세상에는 무수한 문제들이 있고, 그 만큼 어려운 문제도 무수히 많다. (ex. NP문제) 알고리즘적으로 보통 어려운 문제는 polynomial 시간 안에 풀 수 없는 문제들을 말한다. 이들을 프로그래밍 적으로 사용하기에는 과부하가 너무 크다. 따라서, 완벽한 답을 구하는 것에는 살짝 내려놓고, 조금은 틀릴 수 있는 가능성이 있더라 하더라도 근접한 답을 구해낼 수 있는 빠른 알고리즘(polynomial 시간안에 해결이 가능한)을 택하는 것이다. 예를들자면, 우리가 인터넷으로 성능대비 가격이 좋은 컴퓨터를 사려고한다. 가장 좋은 방법은 온라인 상에 있는 모든 웹 사이트에 판매중인 컴퓨터 제품들을 하나하나 다 비교하고, 최고 가성비의 제품을 사는 것이다. 하지만..