알고리즘 및 자료구조 검색 결과

해당 글 94건

자바로 HashTable 구현하기

해쉬테이블에 대한 설명은 조대협 블로그를 참고 ! 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104package com.study; import java.util.LinkedList; class HashTable { LinkedList[] data; public HashTable(int size) { this.data = new LinkedList[size]; } int getHashCode(..
알고리즘 및 자료구조/자바로 만드는 자료구조 2018. 10. 10. 23:00

자바로 Queue 구현하기

큐에 대한 설명은 따로 하지 않겠다. 구현 내용 : peek() : Queue에 맨 앞에 있는 데이터를 가져온다 (Queue에서 꺼내진 않음)remove() : Queue에 있는 데이터 꺼낸다.add() : Stack에 데이터를 삽입isEmpty() : Stack 비어있는지 확인 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768import java.util.NoSuchElementException; class Queue { private Node first; private Node last; class Node { private..
알고리즘 및 자료구조/자바로 만드는 자료구조 2018. 10. 10. 19:30

자바로 풀어보는 삽입정렬(InsertSort)

삽입 정렬은 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 정렬 과정 (N개의 정렬을 할 숫자가 있다고 가정)1. 한 개의 값을 포함하는 목록으로 시작한다. 2. 두 개의 값을 비교하고, 적합한 위치에 삽입한다. 3. 세 개의 값을 처음 두 개의 값과 비교하여 위치에 삽입한다. 두 가지의 버전으로 작성하였다. 하나는 재귀를 이용한. 하나는 단순 for문이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051public class InsertSort { private static int[] array; public st..
알고리즘 및 자료구조/정렬 2018. 10. 5. 14:29

빅오 표기법 개념과 예제

Big-O(빅오) 표기법 알고리즘의 성능 및 복잡도를 표현하기 위하여 사용하는 지표 알고리즘의 실행 시간 또는 사용 메모리 공간을 표현 정확한 값이 아닌 어림 값으로, 알고리즘의 대략적인 평가만 가능 시간복잡도, 공간복잡도 시간복잡도 1) 알고리즘의 실행 속도를 측정(CPU) 2) 표기법은 (4.표기법 및 종류) 참고 3) O(n2)포함해서 더 느린 알고리즘은 좋지않다고 판단 - 공간복잡도 1) 알고리즘이 사용한 메모리를 측정(RAM) 2) 크기가 N인 배열이 N*N배열 되었을 경우 공간 복잡도는 N2 아래 사진을 통해 빅오 표기법을 알아보면 대충 이해가 갈 것이다.O(1)쪽으로 갈 수록 속도가 빠른 것이고, O(N2)에 갈 수록 속도가 느려진다. O(1) 인자에 값이 여러개 있더라도 하나에 접근했을 때..
알고리즘 및 자료구조/이론 2018. 10. 1. 19:30

자바로 Tree 구현하기

트리에는 선회방법이 3가지가 있다.중위순회(Inorder) Left -> Root -> Right전위순회(PreOrder) Root -> Left -> Right후위순위(PostOrder) Left -> Right -> Root 외우기 힘들다면 Root를 기준으로 중위면 Root가 가운데이 있고, 전위라면 Root가 앞에, 후위라면 Root가 뒤에 그리고 무조건 Left 다음 Right인 것을 인지한다면 쉽게 외울 수 있을 것 같다. 중위 순회 Inorder = Left -> Root -> Right4 -> 2 -> 5 -> 1 -> 3전위순회 Preorder = Root -> Left -> Right1 -> 2 -> 4 -> 5 -> 3후위순회 Postorder = Left -> Right -> Roo..
알고리즘 및 자료구조/자바로 만드는 자료구조 2018. 9. 18. 22:14

자바로 Stack 구현하기

스택에 대한 설명은 따로 하지 않겠다.스택이나 자료구조는 동영상으로 공부하는 것이 훨씬 좋은 것 같다. 비록 알고 있는 내용이지만 다른 사람이 구현한 것과 내가 구현한 것의 차이를 비교하자면 다른 사람이 구현한 것이 훨씬 코드가 좋은 것을 깨달을 수 있었다. 아는 것과 구현하는 것은 다른 것 같다.. 구현 내용 : peek() : Stack 최상단에 있는 top data 반환(Stack에서 꺼내진 않음)pop() : Stack에 있는 데이터 꺼내기push() : Stack에 데이터를 삽입isEmpty() : Stack 비어있는지 확인empty() : Stack을 초기화size() : Stack Size 반환 123456789101112131415161718192021222324252627282930313..
알고리즘 및 자료구조/자바로 만드는 자료구조 2018. 9. 18. 21:00

백준알고리즘 1010번 다리 놓기

백준알고리즘 2153번 소수 단어문제 링크 문제 푸는데 그렇게 어려운 문제였다....... 방법은 조합을이용한 것 그리고 다이나믹 프로그래밍으로 문제를 풀 수 있다.조합을 간단하게 설명하자면 2 5인 경우 5*4 / 2*1로하면 값이 나온다. 3 6 이라면 6*5*4*3*2*1 / 3*2*1 로하면 값이 나온다.1234567891011121314151617181920212223242526272829303132333435363738import java.math.BigInteger;import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); in..
알고리즘 및 자료구조/문제 2018. 7. 26. 17:23

Algorithm - 브루트 포스

브루트 포스(Brute-Force) Brute는 짐승같은, 난폭한이라는 의미이고, Brute-force는 난폭한 힘, 폭력이라는 뜻이다.암호학에서도 무차별 대입 공격이라고 부르고, 실제로 암호학에서도 쓰이는 방법이다. 간단하게 말해서문제를 해결하기 위해 모든 가능한 경우의 수를 직접 조합 및 대입하여 해보는 방법이라고 할 수 있다. 브루트 포스의 예쉽게 예를 들어 집 비밀번호는 4자리 숫자로 이루어져 있고 비밀번호가 9999라면도둑은 0001 ~ 9999까지 하나하나 비밀번호를 입력해야하는 것이 브루트 포스의 쉬운 예라고 할 수 있다. 브루트 포스의 단점위의 도둑의 예제를 다시 들자면 0001 ~ 9999까지의 비밀번호를 입력하는데 시간은.. 사람마다 다르겠지만 어마어마하게 많은 비용이 발생한다. 브루트..
알고리즘 및 자료구조/이론 2018. 5. 14. 12:19

백준알고리즘 2748번 피보나치 수2

백준알고리즘 https://www.acmicpc.net/problem/2748 2747번(피보나치 수)와 문제는 똑같은데 차이점은 입력받는 범위가 최대였을 때 int 형의 범위를 넘어가 버려서 문제가 된다. long형으로 변경하면 해결import java.util.Scanner; public class Main2 { static long[] array; public static void main(String[] args) { Scanner scan = new Scanner (System.in); int calData = Integer.parseInt(scan.nextLine().trim()); array = new long[calData + 1]; System.out.println(calculate(ca..
알고리즘 및 자료구조/문제 2018. 5. 14. 09:07