깃헙 자료를 긁어와서 목차 링크가 안먹습니다. https://github.com/SeoJaeyeon/study/tree/master/study/DataStructure%26Algorithm 참고
자료구조
알고리즘
Array
Array 란?
"연속적인 메모리 영역을 가지는 선형 리스트"
특징
<value, index> 집합
index만 알고 있다면 random access 가능(O(1))
단, 삽입과 삭제가 이루어질 시 메모리의 연속성을 유지하기 위해 shift 필요(O(n))
sorted array/ unsorted array
Linked List
Linked List란?
"임의의 메모리 영역을 가지는 연속적인 데이터들의 집합"
특징
각각의 element는 다음 element를 가리키는 포인터를 가짐
data + link -> node
Singly linked list/ doubly linked list
삽입과 삭제는 link만 변경하면 됨(O(1))
Search는 첫 번째 노드부터 링크를 따라가야 함(O(n))
Stack
Stack이란?
"Top이라는 한 쪽 끝에서 삽입, 삭제가 모두 일어나는 LIFO의 자료구조"
기본연산
push() - Top위치에 데이터 삽입
pop() - Top-1 위치의 데이터 삭제 + return
peek() - Top-1 위치의 데이터 return
자바에서 Stack 클래스
List 인터페이스를 구현
Stack<String> stack=new Stack<String>();
stack.push("1");
stack.push("2");
System.out.println("pop: "+stack.pop()); // pop: 2 출력
System.out.println("peek: "+stack.peek()); // peek: 1 출력
System.out.println("search 1: "+stack.search("1")); // search 1: 1 출력
System.out.println("search 2: "+stack.search("2")); // search 2: -1 출력
LinkedList 클래스를 이용하면 더 빠르다(단 스레드 안전 보장x)
LinkedList<String> dequeue=new LinkedList<String>();
dequeue.add("1");
dequeue.add("2");
System.out.println("pop: "+dequeue.removeLast()); // 후입선출
System.out.println("peek: "+dequeue.getLast());
System.out.println("search 1: "+dequeue.indexOf("1"));
System.out.println("search 1: "+dequeue.indexOf("2"));백준 알고리즘 9012 괄호매칭
문제
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.
import java.util.Scanner;
import java.util.Stack;
public class Main {
/*
* 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다.
* 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.
* 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다.
* 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int t=scan.nextInt();//테스트케이스 수
scan.nextLine();
for(int i=0; i<t; i++) {
String input=scan.nextLine();
Stack stack= new Stack();
for(int k=0; k<input.length(); k++) {
if(stack.isEmpty()) {//스택이 비어있으면
stack.push(input.charAt(k));
continue;
}
//하기 전에 stack top 위치의 괄호와 매칭되는지 확인 => 현재 괄호가 )이고 top 위치의 괄호가 ( 여야 함
if((char)stack.peek()=='(' && input.charAt(k)==')') {
//괄호 짝이 맞음 -> pop
stack.pop();
}
//매칭이 되지 않으면 스택에 추가
else {
stack.push(input.charAt(k));
}
}
if(stack.empty()) System.out.println("YES"); else System.out.println("NO");;
}
}
}Queue
Queue란?
"Rear라는 한 끝에서 삽입이, Front라는 한 끝에서 삭제가 일어나는 FIFO의 자료구조"
기본연산
add() - rear에 데이터 삽입
remove() - front의 데이터 삭제
special queue
Circular queue
선형 List 구조의 Queue에서 앞 쪽에 공간이 있음에도 rear에만 삽입해야하는 특성 때문에 공간이 낭비되는 현상을 해결하기 위해 List의 양 끝을 연결하여 사용하는 구조
- Full Queue의 조건: Rear==Front && element 수!=0
DEQ(Doubly-Ended Queue)
삽입과 삭제가 양 끝 모두에서 일어날 수 있는 구조
- AddQ_Front(), AddQ_Rear(), DeleteQ_Front(), DeleteQ_Rear()
Priority Queue(Heap)
데이터 삭제가 "우선순위"에 따라 이루어지는 구조
백준 알고리즘 7662 이중우선순위큐
문제
이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하나는 데이터를 삭제하는 연산이다. 데이터를 삭제하는 연산은 또 두 가지로 구분되는데 하나는 우선순위가 가장 높은 것을 삭제하기 위한 것이고 다른 하나는 우선순위가 가장 낮은 것을 삭제하기 위한 것이다.
정수만 저장하는 이중 우선순위 큐 Q가 있다고 가정하자. Q에 저장된 각 정수의 값 자체를 우선순위라고 간주하자.
Q에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 Q에 저장된 데이터 중 최대값과 최솟값을 출력하는 프로그램을 작성하라.
import java.util.Scanner;
import java.util.Comparator;
import java.util.PriorityQueue;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int T=scan.nextInt();
for(int i=0; i<T; i++) {
int command=scan.nextInt();
//우선순위 큐 라이브러리 사용
//maxheap
PriorityQueue<Element> maxHeap= new PriorityQueue<Element>(command, new Comparator<Element>() {
public int compare(Element m1, Element m2)
{
return m1.n>=m2.n? -1 : 1;
}
});
//minheap
PriorityQueue<Element> minHeap= new PriorityQueue<Element>(command, new Comparator<Element>() {
public int compare(Element m1, Element m2)
{
return m1.n>=m2.n? 1 : -1;
}
});
scan.nextLine();
for(int j=0; j<command; j++) {
String com=scan.nextLine();
String qCommand=com.split(" ")[0]; int n=Integer.parseInt(com.split(" ")[1]);
//삽입 명령 시, minheap과 maxheap 모두에 삽입
if(qCommand.equals("I")) {
Element ele=new Element(n);
minHeap.add(ele);maxHeap.add(ele);
}
else if(qCommand.equals("D")) {
//삭제 명령 시 minHeap과 maxHeap 모두 visted된 Element를 삭제하고 명령 수행함
while(maxHeap.isEmpty()==false && maxHeap.peek().visited!=false) {
//masHeap이 비어있지 않고 동시에 element가 이미 방문 된 경우
maxHeap.poll();//poll
}
while(minHeap.isEmpty()==false && minHeap.peek().visited!=false) {
minHeap.poll();
}
if(maxHeap.isEmpty() || minHeap.isEmpty()) {
//비어있는 경우 아무 것도 수행하지 않음
continue;
}
else if(n==1) {
//우선순위 높은 것 삭제하면서 해당 Element.visited=true (동기화 위함)
maxHeap.poll().visited=true;
}
else if(n==-1) {
//우선순위 낮은 것 삭제
minHeap.poll().visited=true;
}
}
}
while(maxHeap.isEmpty()==false && maxHeap.peek().visited!=false) {
maxHeap.poll();
}
while(minHeap.isEmpty()==false && minHeap.peek().visited!=false) {
minHeap.poll();
}
if(minHeap.isEmpty()||maxHeap.isEmpty())
System.out.println("EMPTY");
else {
System.out.println(maxHeap.peek().n+" "+minHeap.peek().n);
}
}
}
}
class Element{
int n;
boolean visited=false;
public Element(int n) {
this.n=n;
}
}Tree
Tree 란?
"계층적 자료구조로 루트라는 노드가 있고 각 연결된 노드는 부모-자식 관계이며 노드간 사이클이 존재하지 않는 자료구조"
Binary tree
typedef class node* nptr;
class node{
data_type data;
nptr lchild, rchild;
}Full Binary tree/ Complete binary tree
parent(i)= i/2
left_child(i)=i*2
right_child(i)=i*2 +1Binary Search Tree
각 노드는 유일한 키 값을 가진다.
루트 노드의 키가 왼쪽 서브트리를 구성하는 모든 노드의 키보다 크다.
루트 노드의 키가 오른쪽 서브트리를 구성하는 모든 노드의 키보다 작다.
왼쪽과 오른쪽의 서브트리도 이진탐색트리이다.
Binary Heap
배열에 기반한 Complete Binary Tree으로 Max Heap, Min Heap으로 나누어진다.
Max Heap의 경우 모든 노드는 자신의 자식노드의 값보다 크거나 같고, Min Heap은 모든 자식 노드의 값보다 작거나 같다. 노드가 삽입/삭제될 때 Heapify를 수행하여 Heap을 유지해야 하며 O(log n)의 시간복잡도를 가진다.
Graph
그래프란?
Vertex와 Vertex 사이를 연결하는 Edge로 구성된 자료구조
Undirected Graph vs Directed Graph
Undirected Graph : (u,v) = (v,u)
Directed Graph: <u,v> != <v,u>
Complete Graph
모든 Vertex들이 서로 연결되어있는 그래프
-> edge 수 : n(n-1)/2
Sparse Graph
Edge의 수가 N개로 일정한 그래프
Connected Graph
Vertex 사이에 끊어짐 없이 모두 연결되어 있는 그래프
strongly connected component
directed graph에서 양방향으로 연결된 구성요소
Spanning tree
그래프의 모든 cycle 을 제거한 tree 구조
Weighted Graph
간선에 가중치가 부여되어 있는 그래프
Adjacency matrix vs Adjacency List
| Adjacency matrix | Adjacency List | |
|---|---|---|
| Complete Graph | O(N^2) | O(N^2) |
| Sparse Graph | O(N^2) | O(N) |
DFS
DFS란?
"Stack을 활용하여 Graph에서 시작 노드에서부터 인접한 노드 중 하나를 방문하고 방문한 노드에서 DFS를 수행하는 기법(recursive call)"
pseudocode
void dfs(Graph G,Vertex v){
visit[v]=true;//해당 노드 방문 표시
for(w =G[v]; w; w=w->link){
//해당 v의 인접한 노드 w
if(visit[w]!=true){
//아직 방문하지 않았다면
dfs(G, w);//인접 노드부터 dfs 수행
}
}
}BFS
BFS란?
"queue를 활용하여 Graph의시작 노드의 인접한 노드를 모두 방문하고 전부 방문한 후 인접 노드 중 한 노드에서부터 다시 인접 노드를 방문하며 Search하는 기법"
pseudocode
void bfs(Graph G, Vertex v){
visit[v]=true;
addq(v);
while(all vertex is visited){
v=deleteq();
for(w = G[v]; w; w = w->link){
if(visit[w]!=true){
visit[w]=true;
addq(w->vertex);
}
}
}
}Single source shortest path
한 출발지에서 모든 노드까지의 최단 경로를 구하는 알고리즘
Dijkstra's algorithm(다익스트라 알고리즘)
Directed graph/ Non-negative edge
procedure Dijkstra(G, s)
for all u in V
dist[u]= maximum;
prev[u]=null;
dist[s]=0;
queue = makequeue();
queue.add(s);
while(queue is not empty){
u=queue.pop();
for all edges (u, v) in E
if(dist[v]>dist[u]+cost(u,v))
dist[v]=dist[u]+cost(u,v);
prev[v]=dist[u];
queue.add(v);
}All pairs shortest path
각각의 모든 노드 사이의 최단 경로를 구하는 알고리즘
Floyd's algorithm
Negative weighted is allowed/ Negative cycle is not allowed
void Floyd(){
for(i=0; i<n; i++)
for(j=0; j<n; j++)
dist[i][j]=cost[i][j];//edge가 존재하는 경우의 cost
for(k=0; k<n; k++)//k는 거쳐가는 노드
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(dist[i][j]>dist[i][k]+dist[k][j])
dist[i][j]=dist[i][k]+dist[k][j];
}백준-알고리즘-2178
문제
N×M크기의 배열로 표현되는 미로가 있다.
| 1 | 0 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|
| 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 |
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int N=scan.nextInt(); int M=scan.nextInt();
int[][] matrix=new int[N][M]; //미로를 담을 2차원 배열 생성
Vertex[][] vertex=new Vertex[N][M];
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) {
vertex[i][j]=new Vertex();
vertex[i][j].dist=N*M; //모든 Vertex를 생성, dist는 최댓값으로 초기회
}
scan.nextLine();
for(int i=0; i<N; i++){
String line=scan.nextLine();//입력 한줄씩 하고
for(int j=0; j<M; j++){
matrix[i][j]=Integer.parseInt(line.substring(j,j+1));// 미로 배열에 넣음
vertex[i][j].x=i; vertex[i][j].y=j;//vertex 각각도 초기화
}
}
Queue<Vertex> queue=new LinkedList<Vertex>();//넓이 우선 탐색 수행하기 위한 큐
vertex[0][0].dist=1;//시작지점은 거리 1
queue.add(vertex[0][0]);//(0,0)부터 탐색 시작 -> 큐에 삽입
while(queue.peek()!=null) {
//더이상 방문할 노드가 없다면
if(queue.peek()==null) break;
if(queue.peek().visited==true) {
//이미 방문한 노드라면 넘어감
queue.poll();
continue;
}
else {
//처음 방문했다면 방문 체크하고 연산 수행
queue.peek().visited=true;
}
int nx=queue.peek().x; int ny=queue.peek().y;
//위쪽 길 존재
if(nx!=0 && matrix[nx-1][ny]==1) {
if(vertex[nx-1][ny].dist>queue.peek().dist+1)
vertex[nx-1][ny].dist=queue.peek().dist+1;
queue.add(vertex[nx-1][ny]);
}
//오른쪽 길 존재
if(ny!=M-1 && matrix[nx][ny+1]==1) {
if(vertex[nx][ny+1].dist>queue.peek().dist+1)
vertex[nx][ny+1].dist=queue.peek().dist+1;
queue.add(vertex[nx][ny+1]);
}
//왼쪽 길 존재
if(ny!=0 && matrix[nx][ny-1]==1) {
if(vertex[nx][ny-1].dist>queue.peek().dist+1)
vertex[nx][ny-1].dist=queue.peek().dist+1;
queue.add(vertex[nx][ny-1]);
}
//아래쪽 길 존재
if(nx!=N-1 && matrix[nx+1][ny]==1)
{
if(vertex[nx+1][ny].dist>queue.peek().dist+1)
vertex[nx+1][ny].dist=queue.peek().dist+1;
queue.add(vertex[nx+1][ny]);
}
queue.poll();
}
System.out.println(vertex[N-1][M-1].dist);
}
}
class Vertex{
//초기 인덱스
int x=-1; int y=-1;
//연결 Vertex
LinkedList<Vertex> linkedList=new LinkedList<Vertex>();
int dist=-1;
boolean visited=false;//방문 여부를 알기 위한 visted 변수
}백준 알고리즘 4963
문제
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다.
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan=new Scanner(System.in);
int w, h;
while(true) {
w= scan.nextInt();//너비
h=scan.nextInt();//높이
if(w==0 && h==0) return;//입력 종료 조건
Area[][] matrix=new Area[h][w];
Queue<Area> areaData=new LinkedList<>();//모든 land 를 담을 queue
for(int i=0; i<h; i++)
for(int j=0; j<w;j++)
{
int n=scan.nextInt();
matrix[i][j]=new Area();
if(n==1) {
matrix[i][j].isMoveable=true;
areaData.add(matrix[i][j]);//모든 이동 가능한 land를 담는 변수
}else {
matrix[i][j].isMoveable=false;
}
matrix[i][j].x=i;
matrix[i][j].y=j;
}
int count=0;//섬의 개수를 세는 변수
Queue<Area> queue=new LinkedList<>();//방문 할 land를 담는 queue
queue.add(areaData.poll());//첫 번째 land 위치 queue에 삽입
while(queue.peek()!=null) {//방문할 land가 남아있다면
int x= queue.peek().x;
int y=queue.peek().y;
//1. 모든 상하좌우, 대각선이 checked 되어있다면, 현재 land 또한 그 섬의 일부
if(queue.peek().checked==false) {//아직 check 안되어있는 land 라면
//위쪽 land가 이미 방문 되어있는지
if(x-1 >=0 && matrix[x-1][y].isMoveable==true && matrix[x-1][y].checked==true){}
//위 왼쪽 대각선 land가 이미 방문 되어있는지
else if(x-1 >=0 && y-1 >=0 && matrix[x-1][y-1].isMoveable==true && matrix[x-1][y-1].checked==true){}
//위 오른쪽 대각선 land가 이미 방문 되어있는지
else if(x-1 >=0 && y+1 < w && matrix[x-1][y+1].isMoveable==true && matrix[x-1][y+1].checked==true){}
//왼쪽 land가 이미 방문 되어있는지
else if(y-1 >= 0 && matrix[x][y-1].isMoveable==true && matrix[x][y-1].checked==true ) {}
//오른쪽 land가 이미 방문 되어있는지
else if(y+1<w && matrix[x][y+1].isMoveable==true && matrix[x][y+1].checked==true) {}
//왼쪽 아래 대각선 land가 이미 방문 되어있는지
else if(y-1>=0 && x+1<h && matrix[x+1][y-1].isMoveable==true && matrix[x+1][y-1].checked==true){}
//아래쪽 land가 이미 방문 되어있는지
else if(x+1<h && matrix[x+1][y].isMoveable==true && matrix[x+1][y].checked==true) {}
//오른쪽 아래 대각선 land가 이미 방문 되어있는지
else if(y+1 < w && x+1 <h && matrix[x+1][y+1].isMoveable==true && matrix[x+1][y+1].checked==true) {}
else //주변 모든 land가 방문되어있지 않고, 현재 자신도 방문되어있지 않다면 섬의 시작
count++;//섬의 개수 카운트
queue.peek().checked=true; //방문 표시하고
}
//현재 위치에서 방문 가능한 land 체크
//위쪽으로 방문 가능한지
if(x-1 >=0 && matrix[x-1][y].isMoveable==true && matrix[x-1][y].checked==false)
{
matrix[x-1][y].checked=true;//위쪽 land check
queue.add(matrix[x-1][y]);//다음에 이동하기 위해 queue에 삽입
}
else if(y-1 >= 0 && matrix[x][y-1].isMoveable==true && matrix[x][y-1].checked==false ) {
matrix[x][y-1].checked=true;
queue.add(matrix[x][y-1]);
}
//위 왼쪽 대각선으로 방문 가능한지
if(x-1 >=0 && y-1 >=0 && matrix[x-1][y-1].isMoveable==true && matrix[x-1][y-1].checked==false)
{
matrix[x-1][y-1].checked=true;
queue.add(matrix[x-1][y-1]);
}
//위 오른쪽 대각선으로 방문 가능한지
if(x-1 >=0 && y+1 < w && matrix[x-1][y+1].isMoveable==true && matrix[x-1][y+1].checked==false)
{
matrix[x-1][y+1].checked=true;
queue.add(matrix[x-1][y+1]);
}
//오른쪽으로 방문 가능한지
if(y+1<w && matrix[x][y+1].isMoveable==true && matrix[x][y+1].checked==false) {
matrix[x][y+1].checked=true;//방문 표시
queue.add(matrix[x][y+1]);
}
//왼쪽 아래 대각선으로 방문 가능한지
if(y-1>=0 && x+1<h && matrix[x+1][y-1].isMoveable==true && matrix[x+1][y-1].checked==false) {
matrix[x+1][y-1].checked=true;
queue.add(matrix[x+1][y-1]);
}
//아래쪽으로 방문 가능한지
if(x+1<h && matrix[x+1][y].isMoveable==true && matrix[x+1][y].checked==false) {
matrix[x+1][y].checked=true;
queue.add(matrix[x+1][y]);
}
//오른쪽 아래 대각선으로 방문 가능한지
if(y+1 < w && x+1 <h && matrix[x+1][y+1].isMoveable==true && matrix[x+1][y+1].checked==false) {
matrix[x+1][y+1].checked=true;
queue.add(matrix[x+1][y+1]);
}
//모든 처리 마치고 해당 area 제거
queue.poll();
if(queue.peek()==null) {//떨어져있는 land를 체크하기 위해 areaData에서 다음 위치를 꺼내옴
while(areaData.peek()!=null && areaData.peek().checked==true)//단 이미 방문한 애들 제외
areaData.poll();
queue.add(areaData.poll());
}
}
System.out.println(count);
}
}
}
class Area{
int x,y;
boolean isMoveable;
boolean checked=false;
}Sorting
sorting이란?
"데이터를 크기순에 따라 정해진 순서로 배열하는 것"
Bubble Sort
기본과정
1) 배열의 가장 뒷자리부터 앞의 데이터와 비교하여 첫 번째 자리에 최솟값을 옮김
2) 배열의 가장 뒷자리부터 앞의 데이터와 비교하여 두 번쨰 자리에 두 번째 최솟값을 옮김
3) 이 과정을 n번 반복함
void bubble_sort(){
//오름차순 정렬
for(i=0; i<n-1; i++)
for(j=n-1; j>=i+1; j--)
if(arr[j]>arr[j-1])
swap(arr[j],arr[j-1]);
}시간복잡도: O(n^2)
Insertion Sort
기본과정
1) 주어진 배열과 같은 사이즈의 배열을 생성한다.
2) 주어진 배열의 첫 번째 원소부터 새로운 배열에 삽입한다.
3) 삽입할 때 새로운 배열은 정렬된 상태를 유지한다.
4) 주어진 배열의 마지막 원소를 삽입할 때까지 반복한다.
void insertionSort(){
//오름차순 정렬
int[] originArr;int[] newArr;
for(i=0; i<originArr.length; i++)//주어진 배열의 첫 번째 원소부터 끝까지
for(j=0; j<i; j++)//새로운 배열의 처음부터 현재까지 삽입된 원소의 위치까지
if(originArr[i]<newArr[j])//지금 넣는 원소의 값이 현재 체크하고 있는 새로운 배열보다 작으면
for(k=i; k>j; k--)//새로운 배열의 현재 체크 위치부터 삽입된 원소의 위치까지 한칸씩 뒤로 미루기
newArr[k]=newArr[k-1];
newArr[j]=originArr[i];//빈 공간에 원소 삽입
}시간복잡도: O(n^2)
Selection Sort
기본과정
1) 배열의 첫 번째 자리부터 끝까지 중 가장 작은 값을 찾아 첫 번째 원소와 교환
2) 배열의 두 번째 자리부터 끝까지 중 가장 작은 값을 찾아 두 번째 원소와 교환
3) 배열의 끝에서 두 번째 원소까지 반복
void selectionSort(){
int[] arr;
for(i=0; i<arr.length-1; i++)
for(j=i; j<arr.length; j++)
if(min > arr[j])
min=arr[j];
swap(arr[i],min);
}시간복잡도: O(n^2)
Merge Sort
기본과정
1) 정렬하고자 하는 배열을 더이상 쪼갤 수 없을 때까지 쪼갠다
2) 원소가 하나 남았으면 정렬된 것으로 간주(Degenerate case)
3) 분할된 배열들을 합병하면서 정렬
void merge_sort(int s, int e, int[] a){
if(s==e)
return;
int m=(s+e)/2;
merge_sort(s,m,a);
merge_sort(m+1,e,a);
merge(s,m,m+1,e,a);
}
int[] merge(int ss, int se, int es, int ee, int[] a){
int s=ss;
int e= es;
int[] sortArray={}; int i=0;
while(s<e){
if(s>e)
sortArray[i++]=a[e++];
else
sortArray[i++]=a[s++];
}
if(s<e){
for(int i=s; i<e; i++)
sortArray[i++]=a[i];
}else{
for(int i=e; i<ee; i++)
sortArray[i++]=a[i];
}
return sortArray;
}시간복잡도: O(nlogn)
Quick Sort
기본과정
1) pivot을 정한다.
2) 배열에서 pivot을 제외한 모든 원소드를 대상으로 pivot 보다 작으면 왼쪽, 크면 오른쪽으로 옮긴다.
3) pivot의 왼쪽 배열, 오른쪽 배열을 대상으로 같은 작업을 수행한다.
4) 수행하는 배열의 크기가 1일 때 종료한다.
void swap(int[] array, int s, int e){
int newe=array[s];
array[s]=array[e];
array[e]=newe;
}
void quick_sort(int s, int e, int[] array){
if(s>=e)
return;
int pivot=partition(s,e,array);
quick_sort(s,pivot-1,array);
quick_sort(pivot+1,e,array);
}
int partition(int s, int e, int[] array){
int pivot=e;//pivot을 배열의 제일 마지막 원소로 정함
int left=s; int right=e-1;
//0부터 left까지는 pivot보다 작은 수만 위치한다.
//right부터 e까지는 pivot보다 큰 수만 위치한다.
while(left<right) {
while(array[left]<array[pivot] && left<right)
{
//올바른 위치에 있음
left++; //다음 원소 탐색
}
while(array[right]>array[pivot] && right>left ){
//올바른 위치에 있음
right--; //다음 원소 탐색
}
if(left<right)//아직 더 탐색할게 남았다면
{
swap(array,left,right);
left++; right--;
}
}
if(array[right]>array[pivot]) {//array[right]가 피봇의 오른쪽에 가야한다면
swap(array,right,pivot);
pivot=right;
}
else {
swap(array,right+1,pivot);
pivot=right+1;
}
return pivot;
}
시간복잡도: 최악의 경우 O(n^2) 이지만 평균적으로 O(nlogn)이고, 실생활에서 같은 복잡도의 병합 정렬보다 성능이 좋음
Dynamic Programming
Dynamic Programming 이란?
"전체 문제를 작은 문제로 나누어 해결하는 방식. 이때, 시간/메모리 낭비를 줄이기 위해 값들을 저장해두었다가 재활용"
0/1 Knapsack Problem
무게(w1, w2, w3, ~, wn) , 가치 (p1, p2, p3, ~, pn) 일 때, 배낭의 수용 가능한 무게 W를 넘지 않는 선에서 최대의 이익을 가지도록 물건을 골라 담아라.(단, 물건 각각은 쪼개서 담을 수 없다)
Greedy Solution
물건을 가치/무게 순으로 정렬하여 높은 순으로 담음
문제점: w(20, 10, 30) /p(40, 10, 15)/ W-50 의 경우 가치/무게 순으로 정렬할 때 (2, 1, 0.5) 이므로 앞의 두 물건을 선택하게 된다. 이때 전체 이익은 50이 되며, 남는 용량은 20이다. 하지만 1, 3번째 물건을 담으면 전체 이익은 55가 되고 무게는 딱 50이 되는 것을 확인할 수 있다. 즉, 이 문제는 Greedy하게 풀어서는 안되고 모든 경우의 수를 계산하고 비교하여 최적의 결과를 찾아야 한다.
Dynamic Solution
1) Recursive Call
간단하지만 시간복잡도가 매우 큼
int knapsack(int i, int n, int capacity)//i: 물건 번호, n: 담으면 1 안담으면 0, capacity: 남는 공간{
if(capacity<min_w(i,n)){
//capacity가 남아있는 물건 중 가장 가벼운 물건보다 작다면
return 0;
}
if(capacity>=sum_w(i,n)){
//capacity가 남아있는 물건을 다 담을 수 있다면
return sum_p(i,n);
}
return min(knapsack(i-1, 1, capacity-w[i])+p[i], knapsack(i-1, 0, capacity));
}2) Memorization
void knapsack(){
for(i is 1 to item.sizes){
for(w is 1 to capacity){
if(w[i] > w )
K[i,w]=k[i-1,w];
k[i,w]=max(k[i-1,w-w[i]]+p[i], k[i-1,w]);
}
}
return k[n,capacity];
}백준 알고리즘 9095
문제
정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int T=scan.nextInt();
for(int i=0; i<T; i++) {
int n=scan.nextInt();
int[] Dp=new int[n+1];
//DP[index] -> index를 나타내는 방법의 수
for(int k=0;k<=n;k++)
Dp[k]=0;
Dp[0]=1; Dp[1]=1;
for(int j=2; j<=n; j++) {
if(j>=3)
Dp[j]=Dp[j-3] + Dp[j-2]+Dp[j-1];
else if(j>=2)
Dp[j]=Dp[j-2]+Dp[j-1];
else
Dp[j]=Dp[j-1];
}
System.out.println(Dp[n]);
}
}
}백준-알고리즘-1463
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 출력하시오.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
int n=scan.nextInt();
int[] Dp=new int[n+1];
for(int i=0; i<=n; i++)Dp[i]=0;
Dp[0]=0; Dp[1]=0;
for(int i=2; i<=n; i++) {
//Dp[index] -> index를 1로 만드는 최소 횟수
if(i%3==0 && i%2==0) {
Dp[i]=Math.min(Dp[i-1], Math.min(Dp[i/3], Dp[i/2]))+1;
}
else if(i%2==0) {
Dp[i]=Math.min(Dp[i-1], Dp[i/2])+1;
}
else if(i%3==0) {
Dp[i]=Math.min(Dp[i-1], Dp[i/3])+1;
}
else
Dp[i]=Dp[i-1]+1;
}
System.out.println(Dp[n]);
}
}
'이론 > 알고리즘&자료구조&Java' 카테고리의 다른 글
| [알고리즘] 순열 - java(백준 10972/10973/10974/1722) (0) | 2018.08.21 |
|---|---|
| [백준알고리즘] 11723: 집합 -Java (0) | 2018.08.16 |
| [Java] String.format 에 대해 알아보자(백준 알고리즘 2439) (0) | 2018.08.16 |
| [Algorithm] Dynamic Programming vs Memoization (0) | 2018.08.01 |
| [자료구조/Java Collection] Set (0) | 2018.07.30 |
