자료구조, 알고리즘

2. 자료구조 - 선형자료구조 - 큐

프로그래머스 큐 문제 💡 기능 개발 - 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42586 - 문제 요약 : 현재 진행률(progresses)와 일간 작업속도(speeds)가 주어졌다. 개발은 동시에 시작하고 누가 끝나는 지는 순서와 상관이 없다. 다만, 앞선 개발이 완료된 시점에야 다음 개발을 배포할 수 있다. 만약 앞선 개발을 배포할 때 다음 개발도 완료됐다면 동시에 배포한다. 배포일마다 배포되는 개발물의 갯수를 출력하시오. - 입출력 예 : progresses speeds return [93, 30, 55] [1, 30, 5] [2, 1] [95, 90, 99, 99, 80, 99] [1, 1, 1, 1, 1, 1] [1, 3,..

2. 자료구조 - 정의, 선형 자료구조

자료구조 💡 자료구조란? - 자료를 효율적으로 CRUD하기 위한 구조를 말합니다. - 자료구조를 잘 사용하면 시간과 공간을 절약할 수 있습니다. 선형 자료구조 💡 선형 자료구조 특징 : 데이터가 1 : 1 관계로 들어가 있다. 종류 : 배열, 리스트, 스택/큐, 해시테이블 특징 자바 컬렉션 속도 or 차이점 배열 - 인덱스를 통해 바로 접근 가능 - 중간에 데이터를 삽입/삭제하기 어려움 - 배열의 크기를 선언 시 지정 ArrayList - add : O(1)/O(n) - get : O(1) - contains : O(n) - remove : O(1)/O(n) 리스트 - 노드에 데이터와 포인터가 존재 - 인덱스가 없어 head부터 순차 접근 - 중간에 데이터를 삽입/삭제하기 쉬움 - 크기를 선언 시 지정하..

1. 코딩 테스트 준비하기 - 시간 복잡도와 논리 오류 잡기

시간 복잡도 표기법 💡 시간 복잡도의 유형 - 빅 오메가 : 최선의 연산 횟수 - 빅 세타 : 보통의 연산 횟수 - 빅 오 : 최악의 연산 횟수 연산 횟수 계산하기 💡 연산 횟수 계산 방법 - 알고리즘 시간 복잡도 X 데이터의 크기 * 일반적으로 1억 번의 연산이 1초가 걸린다. 시간 복잡도 데이터 크기 속도 N 100,000,000 1초 N^2 10,000 1초 N^3 100 1초 디버깅 💡 나만의 디버깅 방법 갖기 1. 오류 메세지를 읽고 오류 원인을 유추한다. 2. 원인이 되는 곳에 break point를 놓는다. 3. 한줄씩 코드를 실행하며 유추한 원인이 맞는지 파악한다. 4. 수정을 하고 다시 디버깅을 한다. 💡 항상 자료형의 범위와 인덱스 범위를 염두하자 [ 출처 ] - [Do it! 알고리즘..

문자열 알고리즘 - KMP와 Robin-Karp 알고리즘

| 관련 강의 영상 https://www.youtube.com/watch?v=UcjK_k5PLHI - KMP나 Robin-Karp를 사용하면 O(n)의 시간복잡도로 문자열에서 패턴 문자열을 찾을 수 있다. - KMP는 어려워서 일단 Robin-karp 부분만 찾아서 적용해보았다. | Robin-Karp 알고리즘 사용해보기 https://joomn11.tistory.com/111?category=900637 [알고리즘] 라빈 카프(Rabin-Karp)(문자열 탐색)(Rolling Hash) 문자열 탐색 알고리즘 Rabin-Karp는 Hashing을 이용하여 문자열에서 특정 패턴과 일치하는지 찾는 알고리즘이다. 문자열에서 찾고자 하는 패턴의 길이만큼 hash값으로 변환하여, 패턴과 hash값이 같은 joom..

알고리즘 속도 구하기

| 알고리즘 속도 구하는 방법 - 아래와 같은 방법으로 알고리즘 속도를 구할 수 있다. - 예전에 알고 있던 방법이었는데, 금방 잊어버렸기에 생각날 때 노트해두었다. Long start = System.currentTimeMillis(); // 알고리즘 돌리고 Long end = System.currentTimeMillis(); System.out.prinln(end - start + " ms");

[알고리즘] 최소신장트리(MST)

| 최소신장트리 - Mininum Spanning Tree - 그래프의 모든 노드를 연결할 때 가중치 합이 최소가 나오는 트리 - 특징 : (1) 사이클 제외 -- 가중치의 합은 사이클이 포함될 때 최소가 될 수 없다. (2) N개의 노드에 대한 최소신장트리 간선 수는 늘 N - 1개이다. | 종류 크루스칼(Kruskal) 프림(Prim) 핵심 - 최소값의 간선 우선 연결 - 사이클 발생 시 다른 간선 선택 - 임의의 노드에서 시작 - 연결된 간선 중 낮은 가중치 선택 언제? - 간선 수가 비교적 적을 때 - 간선 수가 많을 때 유리 메모리 에지 리스트(or 배열) 유니온 파인드 배열 인접 리스트(or 배열) 방문 배열 속도 O(ElogE) O(ElogV) - 우선순위 큐 사용 시 *O(v2) - 정렬되..

[알고리즘] 최단 경로 구하기 - 3. 플로이드-워셜 알고리즘

| 플로이드-워셜 알고리즘 - 모든 노드의 최단 경로를 구하는 알고리즘으로 전체 간선을 인접 행렬로 표현하고 dp를 통해 최단 경로를 구하는 방식 핵심 : 전체 경로의 최단 경로 = 부분 경로의 최단 경로의 조합 - 기능 : 모든 노드 간에 최단 경로 탐색 - 특징 : 음수 가중치 Ok, 동적 계획법의 원리를 사용 - 시간복잡도 : O(V3) | 플로이드-워셜 구현하기 1 배열을 선언하고 초기화 2 노드의 각 인접 노드 경로 입력 3 점화식으로 배열 업데이트 4 음수사이클 확인 [1] 배열을 선언하고 초기화 - 각각의 노드를 Start지점으로 두고 모든 Start지점에 대한 최단 거리를 구할 예정 1 2 3 4 5 1 0 ∞ ∞ ∞ ∞ 2 ∞ 0 ∞ ∞ ∞ 3 ∞ ∞ 0 ∞ ∞ 4 ∞ ∞ ∞ 0 ∞ 5 ..

[알고리즘] 최단 경로 구하기 - 2. 벨만 - 포드

| 벨만-포드 - 가중치가 양수만 있을 때에 다익스트라를 사용했다면, - 가중치에 음수가 있을 때엔 벨만-포드를 사용한다. - 기능 : 특정 출발 노드에서 도착 노드까지의 최단 경로 탐색 - 특징 : 가중치 음수 OK, 음수 사이클 여부 판단 - 시간 복잡도 : O(VE) | 벨만-포드 구현하기 - 지난번에 구현했던 다익스트라의 우선순위 큐 버전으로 쓰면 음수도 커버가 가능한데 - 벨만-포드를 사용하게 되면 음수 사이클 여부까지 커버할 수 있다. - 구현의 순서 1 에지 배열 & 최단 경로 dp 배열 초기화 2 모든 에지를 하나씩 확인하여 최단 경로 업데이트 3 음수 사이클 여부 확인 [1] 에지 배열(또는 리스트) & 최단 경로 dp 배열 초기화 - 이 부분은 다익스트라의 노드 클래스가 간선 클래스로 ..

[알고리즘] 최단 경로 구하기 - 1. 다익스트라

| 다익스트라 - 가중치가 있는 그래프에서, 최단 경로를 구하는 알고리즘 - 핵심 : 그래프의 인접리스트와 DP를 이용 - 기능 : 출발 노드와 모든 노드 간의 최단 거리 탐색 - 특징 : 간선은 모두 양수 - 시간 복잡도 : O(ElogV) * E : 간선수, V : 정점수 | 다익스트라 구현 - 배열을 사용하는 것도 좋지만 배열 크기가 너무 클 경우를 대비해 인접 리스트를 사용 - (1),(2) 모두 기본적으로 동일하게 아래를 세팅 (1) 간선 정보 리스트 : 인접 리스트에 Node(연결된 노드, 가중치) 타입으로 저장 (2) 임시 거리 배열 : 출발지부터 노드 X까지의 현재 최소 거리를 업데이트할 배열 ㄴ start 위치는 자기 자신이므로 0으로 세팅한다. class Node{ int to; int..

[알고리즘] 백트래킹

| 백트래킹 - 모든 가능한 경우의 수 중에서 유망하지 않은 쪽은 제외하고 최적해를 구하는 방법 - 주로 재귀를 사용해서 구현한다. 유망(Promising) 가능성 있다. 가지치기(Pruning) 가능성 없는 것 제외하기 백트래킹(Backtracking) 유망하지 않은 쪽으로는 가지 않고 Back한다. | N-Queen 을 통한 백트래킹 이해 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net - N x N의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치한다고..