초보 개발자의 기록

동적 계획법(Dynamic Programming)복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법 동적 계획법의 핵심 이론동적 계획법의 원리와 구현 방식큰 문제를 작은 문제로 나눌 수 있어야 한다작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결곽값은 항상 같아야 한다모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 떄는 이 DP 테이블을 이용한다.이를 메모이제이션(memoization)기법이라고 한다동적 계획법은 톱-다운 방식(top-down) 과 바텀-업(bottom-up)방식으로 구현될 수 있다 동적 계획법의 가장 대표적인 문제피보나치 수열 공식D[N] = D[N-1] + D[N-2] // N번때 ..

1. 배열과 리스트배열배열은 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조배열의 값은 인덱스를 통해 참조할 수 잇으며, 선언한 자료형의 값만 저장할 수 있음 배열의 특징인젝스를 사용하여 값에 바로 접근할 수 있다.새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 잇는 값을 이동시키는 과정이 필요하다배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.구조가 간단하르모 코딩테스트에서 많이 사용된다 리스트리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조* 노드는 컴퓨터 과학에서 값, 포인터를 쌍으로 갖는 기초 단위를 말함 리스트의 특징인덱스가 없으므로 값에 접근하려면 Head 포인..

형 변환은 자주 사용하는 기술.형 변환 관련 함수들을 자유롭게 사용할 수 있도록 미리 연습해 두기 String형 -> 숫자형(int, double, float, long, short)String sNum = '1234';int i1 = Integer.parseInt(sNum);int i2 = Integer.parseInt(sNum);double d1 = Double.parseDouble(sNum);double d2 = Double.valueOd(sNum);float f1 = Float.parseFloat(sNum);float f2 = Float.valueOf(sNum);long l1 = Long.parseLong(sNum);long 12 = Long.valueOf(sNum);short s1 = Short..

너비 우선 탐색(BFS, breath-first search)그래프를 완전 탐색하는 방법 중 하나시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘기능특징시간 복잡도(노드 수;V, 에지 수:E)그래프 완전 탐색- FIFO 탐색- Queue 자료구조 이용O(V+E) 너비 우선 탐색은 선입선출 방식으로 탐색하므고 큐를 이용해 구현너비 우선 탐색은 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 떄 최단 경로를 보장 너비 우선 탐색의 핵심 이론1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기BFS도 DFS와 마찬가지로 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열이 필요그래프를 인접 리스..

깊이 우선 탐색(DFS)깊이 우선 탐색DFS (Depth-first search)은 그래프 완전 탐색 기법 주 ㅇ하나그래프의 시작 노드에서 출발하여 탐색한 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 노드 개수:V에지 개수:E기능특징시간 복잡도 (노드 수: V, 에지 수:E)그래프 완전 탐색- 재귀 함수로 구현- 스택 자료구조 이용O(V+E) 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로(stack overflow)에 유의해야 함.깉이 우선 탐색을 응용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상 정렬 등 DFS는 한번 방문한 노드를 다시 방문하면 안되느모 노드 방문 여부를 체크할 배열이 필요..

1. 예상치 못한 음수 결과 해결주어진 조건이나 수식에 오류가 있거나, 변수의 자료형이 적절하지 않아 범위를 초과할 때 자주 발생결과가 예상치 못한 음수로 출력된다면, 먼저 자료향 점검하기int : -2,147,483,648 ~ 2,147,483,647long: -9,223,372,036,854,775,808 ~ 0,223,372,036,854,775,807 2. 시간 초과의 원인을 찾아 해결하기- 입력과 출력 방식부터 최적화할 수 있는지 점검- Scanner와 System.out.print 대신 BufferedReader와 BufferedWriter를 활용하면 처리 속도 크게 향상 풀이 로직의 시간 복잡도가 제한 시간 안에 문제를 해결할 수 있는 수준인지 확인. 시간 복잡도가 너무 높다면 로직 자체를 ..

시간 복잡도주어진 조건에 따라 접근법 유추가 가능시간복잡도를 고려한 설계가 가능 O(1)상수 시간: 문제를 해결하는데 오직 한 단계 처리어떤 값을 찾는데 걸리는 시간은 개수와 상관없이 항상 일정함예) 해시맵 조회// 배열에서 첫 번째 원소를 가져오는 경우int[] arr = {1,2,3,4,5};System.out.println(arr[0]); //항상 한 번에 끝남 O(logN)로그 시간: 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬비유: 전화번호부에서 특정 이름을 찾는 경우, 한 페이지씩 찾는 대신, 중간 페이지를 열어 찾는 이름이 앞쪽인지 뒤쪽인지 확인한 후, 해당 절반만을 다시 탐색. 계속 절반씩 나눠가며 찾기 때문에 전체를 찾는 시간이 훨씬 줄어듬예) 완전 이진 트리 탐색..

시간 복잡도- 입력 크기에 대해 어떠한 알고리즘이 실행되는 데 걸리는 시간- 로직의 반복 횟수를 중점으로 측정- 빅오 표기법으로 나타냄: 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것- 입력 크기가 커질수록 연산량이 가장 많이 커지는 항은 n의 제곱항이고, 다른 것은 그에 비해 미미하기 떄문에 이것만 신경 쓰면 된다는 이론- 효율적인 코드로 개선하는 데 쓰이는 척도 공간 복잡도- 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양- 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함 자료 구조에서의 시간 복잡도자료 구조의 평균 시간 복잡도자료 구조접근탐색삽입삭제배열 (array)O(1)O(n)O(n)O(n)스택(stack)O(n)O..

시간복잡도- 빅 오메가: 최선일 때의 연산 횟수를 나타낸 표기법- 빅 세타: 보통일 때의 연산 횟수를 나타낸 표기법- 빅 오: 최악일 때의 연산 횟수를 나타낸 표기법 * 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다름 * 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측* 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준 * 연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출* 데이터의 크기(N)을 단서로 사용해 알고리즘을 추측할 수 있음 시간 복잡도 도출 기준1. 상수는 시간 복잡도 계산에서 제외2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡..