Persistence

풀이 def accumulator(index, target_DNA, DNA_mapper): for DNA in DNA_mapper: if target_DNA == DNA: DNA_mapper[target_DNA][index + 1] = DNA_mapper[target_DNA][index] + 1 else: DNA_mapper[DNA][index + 1] = DNA_mapper[DNA][index] def get_minumum_impact_factor(start_index, end_index, DNA_mapper): for DNA in DNA_mapper: if DNA_mapper[DNA][end_index + 1] - DNA_mapper[DNA][start_index] > 0: return DNA els..

Prefix Sums array의 어떠한 slice라도 sum을 빠르게 계산할 수 있도록 해주는 방법이다. 예를 들어 어떤 배열의 인덱스 i부터 j까지의 합을 구하려고 할 때 for문을 써서 일일이 접근해서 더하면 O(N)이지만, 이 방법을 사용하면 O(1)이다. def prefix_sums(A): n = len(A) P = [0] * (n + 1) for i in range(1, n + 1): P[i] = P[i - 1] + A[i - 1] return P 점화식: P[i] = P[i - 1] + A[i - 1] A라는 배열이 있을 때, A 배열의 sum의 누적값을 계산해서 P에 넣는 것이다. P[i] = P[i - 1] + A[i - 1]으로 계산되고, P[i]는 A 배열의 i번째 원소(인덱스로는 i..

피보나치 수열 문제: 피보나치 수열에서 n번째 오는 값을 구하시오. e.g. n이 6일 때, 1, 1, 2, 3, 5, 8 ... 이므로 답은 8 재귀로 아래처럼 간단하게 풀 수 있으나, 이 방법은 O(2^n) 시간 복잡도를 가진다. def fib(n): if n == 1 or n == 2: return 1 return fib(n-2) + fib(n-1) 시간 복잡도를 생각하는 방법은, 아래와 같은 예시를 생각해보면 된다. 위의 피보나치 수열을 구하는 재귀와 밑의 코드의 시간복잡도는 비슷하리라 짐작할 수 있다. 하나의 n에서 두 개의 가지를 뻗어서 자기 자신을 재호출하고 있는 구조이기 때문이다. -1씩 깎이는 거나 -2씩 깎이는거는 나중에 가면 상수값이 되어서 빅오표기법에서는 의미가 없다. (이 영상 의..

Rotation point 찾기 문제 문제 a부터 z 순으로 적혀진 사전을 읽다가 모르는 단어가 나오면 단어장에 기입하는 작업을 하려고 한다. 단, 사전의 어느 중간부터 펴서 이 작업을 시작한다. 그래서 뒤로 가면서 이 작업을 수행하다가 사전의 끝에 도달하면 사전의 처음부터 시작해서 처음에 폈던 페이지 전까지 이 작업을 한다. 이 모르는 단어는 배열에 순서대로 저장하여, 예시를 들면 다음과 같은 형태가 된다. ['ptolemaic','retrograde', 'supplant', 'xenoepist', 'asymtote', 'babka'] 알파벳 오름차순으로 진행되다가 사전의 끝까지 찾고 나면 다시 앞에서부터 시작하기 때..

퀵 정렬(Quick sort) 컴퓨터 언어에는 대부분 배열을 정렬하는 내장 정렬 함수가 있는데, 대다수가 내부적으로는 퀵 정렬 방법을 택하고 있다. 그 만큼 퀵정렬이 빠르기 때문이다. 퀵 정렬은 최악의 경우에는 삽입정렬이나 선택정렬 만큼 느리지만 대부분의 경우인 평균 시나리오에서는 훨씬 빠르다. 퀵 정렬은 분할(partition) 에 기반하고 있으며 이 분할이 재귀적으로 일어나는 과정을 통해 정렬된다. 분할 배열을 분할한다는 것은 피벗(기준 원소)를 기준으로, 피벗의 왼쪽에는 피벗보다 작은 수를 두고, 피벗의 오른쪽에는 피벗보다 큰 수를 두는 것을 말한다. [0,5,2,1,6,3] 이라는 배열을 가정하자. 피벗을 정렬되지 않은 배열의 가장 오른쪽 원소라고 정하자. 그러면 맨 오른쪽 위치의 3 이 피벗이 ..

선택 정렬(Selection sort) 단순 정렬(Simple sort) 중 하나로, 속도는 느린 편(평균적으로 O(n^{2}), quadratic time)이지만 최악의 경우를 가정했을 때 버블소트보다 2배 가량 빠르다. 가정 배열(Array) 정렬을 가정한다. 정렬되지 않은 배열을 오름차순으로 정렬한다. 배열의 길이는 n이다. 순서 index 0 원소를 temp라는 변수에 저장한다. 그 다음 index 1부터 index n-1 까지 순회하면서 temp보다 작은 값이 있는지 비교 한다. 만약 비교 결과 temp보다 작은 값이 있으면 그 값을 temp에 재할당한다. 이렇게 한 번 패스 스루(정해진 범위의 배열을 한 번 훑는 것)를 끝내고 나면, temp에는 전체 배열 원소값 중 최소값이 저장되어 있을 것..

버블 정렬(Bubble sort) 단순 정렬(Simple sort) 중 하나로, 속도는 느린 편(평균적으로 O(n^2), quadratic time)이지만 간단하게 구현할 수 있는 장점이 있다. 마치 버블이 이동하듯이 가장 큰 수가 왼쪽에서 오른쪽(배열의 앞에서 뒷쪽)으로 이동한다고 해서 버블 정렬이다. 가정 버블소트는 배열(Array) 정렬을 가정한다. 정렬되지 않은 배열을 오름차순으로 정렬한다. 배열의 길이는 n이다. 순서 배열의 가장 처음부터(index 0부터) 원소 2개씩 비교 한다. 즉 arr[0], arr[1]을 비교해서 arr[0] > arr[1] 이면 순서를 바꾼다. 아니면 그냥 Pass한다. arr[1]과 arr[2]에도 똑같이 한다. arr[n-2]과 arr[n-1]까지 똑같이 한다. ..

컴퓨터 메모리에 뭔가를 저장해야 할 때 컴퓨터에게 저장 공간을 요청한다. 컴퓨터는 뭔가를 저장할 수 있는 주소를 알려준다. 이 때 여러 개의 원소를 저장해야 한다면 여러 개의 주소가 필요할 텐데, 선형적으로 저장한다고 가정하면 배열이나 리스트 중 하나로 저장하게 된다. (선형적이지 않은 저장 방법으로는 트리나 그래프 등이 있다) 배열(Array) 만약 10개의 원소를 배열로 저장해야 한다면, 메모리에 연달아 있는 10개 공간을 할당한다. 배열의 장점 인덱스가 주어지므로 빠르게 접근할 수 있다. 배열의 단점 처음에 3개의 공간만 요청했다가 공간이 1개 더 필요하게 되면, 이 때 공간 4개를 재요청해야 한다. 즉 사전에 할당한 공간 내에서만 저장이 가능하고 이 공간 범위를 벗어날 경우 재요청이 필요하다. 이..

프로그래머스 야근지수(파이썬) 프로그래머스 문제 링크 힙큐를 이용한 풀이 import heapq def solution(n, works): for i in range(len(works)): works[i] *= -1 heapq.heapify(works) for i in range(n): m = heapq.heappop(works) if m >= 0: break m += 1 heapq.heappush(works, m) answer = 0 for i in range(len(works)): answer += pow(works[i]*-1,2) return answer 힙큐 모듈을 사용한다. 이 문제의 솔루션은 주어진 works 리스트에서 가장 큰 값을 찾고, n이 0이상일 동안 1씩 빼나가는 것인데, 매번 가장..

문제 출처 - 프로그래머스 문제(정확한 문제는 위 링크 참조) n개의 노드가 있는 그래프가 있다. 각 노드는 1부터 n까지의 번호가 적혀있다. 최단 경로를 전제했을 때 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 리턴하라. 입출력 예시 - 자바스크립트 버전 노드의 개수 n과 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어진다. (ex) n = 6 vertex = [[3,6],[4,3],[3,2],[1,3],[1,2],[2,4],[5,2]] return 3 (설명) 1번 노드로부터 가장 멀리 떨어진 노드는 4,5,6 이므로 3을 리턴 시간 초과 실패한 코드 1 BFS, queue를 이용 function solution(n, edge){ // 큐의 가장 첫번째 원소를 head로 설정 ..

LinkedList package LinkedList; // 노드는 data와 다음 오브젝트를 가리킬 next variable로 구성됨 public class Node { int data; Node next = null; } public class App { public static void main(String[] args) { // 노드 인스턴스 생성 및 데이터 삽입 Node nodeA = new Node(); nodeA.data = 3; Node nodeB = new Node(); nodeB.data = 5; Node nodeC = new Node(); nodeC.data = 7; Node nodeD = new Node(); nodeD.data = 9; // 노드 인스턴스끼리의 연결 nodeA.ne..

Queue public class Queue { private int maxSize; private long[] queArray; private int front; // 큐의 첫번째 인덱스(포인터 역할) private int rear; // 큐의 마지막 인덱스 private int nItems; // 전체 길이 public Queue(int size) { this.maxSize = size; this.queArray = new long[size]; front = 0; rear = -1; nItems = 0; } public void insert(long j) { if(rear == maxSize -1) { rear = -1; // 다시 앞에서부터 덮어씌움. Circular Queue } rear++; q..

Stack 스택으로 reverseString 구현 package adt; // Stack 클래스 public class Stack { private char [] myStack; private int maxSize; private int top = -1; Stack(int s) { this.maxSize = s; myStack = new char [maxSize]; } public void push(char i) { top++; myStack[top] = i; } public char pop() { int old_top = top; top--; return myStack[old_top]; } public boolean isEmpty() { if(top == -1) { return true; } retur..

문제 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 생성자가 없는 ..

빠른 A+B 문제 3 1 11 // should print 12 2 30 // should print 32 12 1 // should print 13 첫 번째 숫자는 총 입력받을 숫자 줄의 개수. 그리고 나머지 줄 부터는 입력받아서 두 숫자의 합을 출력하면 된다. 단 시간 제한이 있어 Scanner를 사용하면 시간 초과가 나므로 BufferedReader 등을 사용해야 한다. 내가 푼 답 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); Buffere..