ALGORITHM37 자료구조 총정리 출처: 윤성우의 열혈 자료구조 Introduction to Data Structures Using C 자료구조는 근본적으로 무엇인가를 '표현'하는 도구. 표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다. 순차 탐색 = 맨 앞에서부터 순서대로 탐색을 진행하는 알고리즘 이진 탐색 = 탐색의 대상을 반복해서 반씩 떨구어 내는 알고리즘 (이진 탐색 조건: 정렬되어 있어야 함) 재귀 = 함수 내에서 자기 자신을 다시 호출하는 함수를 의미 (일련의 과정을 반복한다고? 재귀구나! 그렇다면 그 일련의 과정만 파악하면 되겠네) 시간 복잡도 최악의 경우를 시간 복잡도의 기준으로 삼는다. (평균적인 경우는 각 알고리즘마다 가정을 설정하기 어렵고 객관적인 판단이 어렵기 때문) O(1) < O(logn.. 2019. 5. 12. [Computational Thinking Skills] 프로그래밍과 논리/수학 SW Expert Academy - computational thinking skills 1. 프로그래밍과 논리/수학 문제 1: 사실-카드는 한 면은 알파벳, 다른 한 면은 숫자 주장-D 뒷면에는 숫자 3이 있다 문제-카드 [D, F, 3, 7]이 있을 때 어떤 카드를 뒤집어서 주장을 증명할 것인가? 문제 1 답: D, 7 F뒤에 3 이 있던 없던 주장과 상관 없음 3뒤에 꼭 d가 있어야 한다고 생각하기에 3을 뒤집어봐야한다고 생각하지만, 3뒤에 A가 있더라도 주장이 모순되지 않음 7을 뒤집어서 D가 있으면 주장이 깨지는 것이 증명되는 것이기에 7을 뒤집어봐야 함 문제 2: 규칙-20세 이하 맥주 마실 수 없음 문제-나이 혹은 마시고 있는 것을 표시한 다음 4명 중 확인이 필요한 사람은 몇 명이고 누구인.. 2019. 4. 27. [JAVA] Stack 스택 자바 스택 기본 이론 출처: 스택 특징 java.util 패키지에 있다 벡터를 상속받고 있다 LIFO(Last-In-First-Out) 총 5가지 메소드 = 비어있는지 확인, 안에 특정요소가 잇는지 살펴보기, 요소를 넣고 빼고, 뭐가 있는지 살짝 보기 boolean empty() int search(Object o) int size(Object o) E push(E item) E pop() E peek() 5가지 메소드를 이용한 예제 코드 import java.util.*; public class Main { public static void main(String[] args){ Stack s = new Stack(); int[] num ={17, 5, 123, 252, 12}; System.out.pr.. 2019. 3. 31. [JAVA] HashMap 해쉬 맵 HashMap 출처: 기본 지식 Hashing : 해시함수를 이용해서 데이터를 해시테이블에 저장하고 검색하는 기법을 말한다. HashMap vs TreeMap HashMap: 저장은 느리지만 많은 양의 데이터를 검색하는데 뛰어난 성능을 보인다. TreeMap: HashMap에 비해 저장이 빠르지만 데이터를 가져올 때 약간 느리다. Map 인터페이스 : 키(key)와 값(value)을 하나의 세트로 묶어서 저장하는 컬렉션 클래스를 구현하는 데 사용 키: 중복 가능 값: 중복 불가 아이디는 중복 불가능하나 1234를 비밀번호로 설정하는 것은 가능한 것처럼 또한, Key와 Value값에 null값을 허용하기 때문에 데이터가 빠져있어도 문제되지 않는다. void clear() : Map의 모든 객체를 삭제 bo.. 2019. 3. 31. [JAVA] QUEUE 큐 출처: Queue 특징 : FIFO(First In First Out) 구조의 자료. 배드민턴 공 통을 생각하자 : Queue(큐) 클래스 인스턴스를 생성하기 위해선 아래와 같이 'LinkedList()' 생성자를 호출해야 함. Queue q = new LinkedList(); :push() 메소드만을 이용하여 데이터를 입력하면 스택처럼 동작 가능. 반대로, offer만을 이용하여 데이터를 입력하면 큐로 동작. 데이터 입력할 때 메소드를 잘 선택하여 입력 boolean add(E e) 해당 큐의 맨 뒤에 전달된 요소를 삽입함. 만약 삽입에 성공하면 true를 반환하고, 큐에 여유 공간이 없어 삽입에 실패하면 IllegalStateException을 발생시킴. boolean isEmpty() 큐가 비어있는.. 2019. 3. 31. [JAVA] 백준 8958번 문제 자바 문자열 비교는 EQUALS쓰라고 좀. 왜 맨날 습관처럼 == 쓰고선 뻘짓 최소 30분. 연속되어~같은 문자일 경우를 찾으라는 문제일 때 어떻게 풀어야 하나? 배열에 집어넣고 배열[X+1]하면 인덱스바운드 익셉션이 나기 때문 예제) 연속되면 SCORE값을 올리는 것 변수를 하나 더 설정해줘서 초기값 정해주고 FOR문 돌면서 계속 업데이트 해줘야 함 check=splits[0];//첫 문자를 기억 System.out.println("CHECK 0값은"+check); for(int i=1;i 2019. 3. 9. [JAVA] 백준 1110번 문제이 문제를 풀려면 2가지 필요(1) 각 자리 수를 더하는 방법을 알아야 함(2)수의 제일 오른쪽의 값을 뽑아낼 줄 알아야 함위 2가지 해결 방법(1)-1. -> 아스키 코드를 사용해 결국 해결 -> 각 숫자의 아스키 코드는 0 을 의미하는 48을 빼주면 자신의 수를 가지게 된다고 함. 참고& 그리고 charAt 사용법도 여기 참고import java.util.*; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int x=scan.nextInt(); String a=scan.nextLine(); //문자열로 받아서 int sum=0; for(int i=0;i 2019. 3. 3. [JAVA] 백준 1065번 문제한수 개념 이해가 우선. 한수 목록101도 한수인줄 알았는데 123이 한수임. -1은 안 되나 봄.첫 번째 시도:문제점:999까지는 구해지는데1000은 어떻게 해야할지 모르겠음package till; import java.util.*; public class Main { public static void main(String[] args){ Scanner scan = new Scanner(System.in); int input=scan.nextInt(); int total=0; String input2; int check; //1부터 99는 무조건 한수 if(input 2019. 3. 3. [JAVA] 백준 4344번 문제: https://www.acmicpc.net/problem/4344첫 번째 시도:입력받기->각 줄 평균 구하기->평균 넘는 학생 구하기->평균 넘는 학생 비율 구하기이렇게 크게 4개로 쪼개어 생각 시작. 코딩시작문제점: 각 줄 평균 구하는 것 되는데 각 줄 평균을 넘는 학생을 구하는데 배열 인덱스? 가 꼬여버림. 학생의 점수를 저장하는데 다차원 배열로 저장해야하나? 싶음. package till; import java.util.*; public class Main { private static final int[] Kaprekar = null; public static void main(String[] args){ //입력받기 Scanner scan=new Scanner(System.in); i.. 2019. 2. 27. [JAVA] 백준 4673번 https://www.acmicpc.net/problem/4673첫 번째 시도:문제를 쪼개서 풀고자 일단 d(n)을 구하는 함수는 만듦문제점:d(n)에 들어가지 않는 수를 어떻게 뽑아내야할지 모르겠음//1부터 10000까지 함수의 파라메터에 넣어가며 리턴값이 1~10000중 없는 값을 출력하면 됨. -> 일단 이렇게 생각함. 근데 그러면 for문을 너무 많이 돌고,, 함수를 아예 다시 만들거나 해야하나 생각 중.package till; public class Main { private static final int[] Kaprekar = null; public static void main(String[] args){ //1부터 10000까지 함수의 파라메터에 넣어가며 리턴값이 1~10000중 없.. 2019. 2. 26. [JAVA] 백준 10817번 https://www.acmicpc.net/problem/10817첫 번째 시도:배열에 세 정수를 넣어서 정렬 후 배열에서 두 번째 정수를 출력하기로 함문제점:정렬을 구현 못하겠음package till; import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner scan=new Scanner(System.in); int a=scan.nextInt(); int b=scan.nextInt(); int c=scan.nextInt(); int[] order={a,b,c}; int temp=a; for(int i=0;iorder[i+1]){ temp=order[i+1]; order[i+1]=order[.. 2019. 2. 1. [JAVA] 백준 1924번 https://www.acmicpc.net/problem/1924첫 시도:도무지 감이 안잡혀서 먼저 1월 달력만 해당하게 프로그램을 만들어 보기로 함문제점:나머지가 요일별로 다르다는 건 바로 알게됨 (그나마 다행;) 다른 월도 해당하게 코딩해보기로 함요일은 바뀌는 거니까 요일을 조건으로 잡아야 하나 생각됨. package till; import java.util.*; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int x=scan.nextInt(); int y=scan.nextInt(); //1월만 if(y%7==1){ System.out.print("MON"); } if.. 2019. 1. 31. [JAVA] 백준 11720번 https://www.acmicpc.net/problem/11720각 자리수의 합을 구하기첫 시도:왜케 배열에 쪼개어 저장하는 걸 좋아하는지 모르겠음.문제점:입력받은 정수형을 배열에 쪼개어 저장하는 방법? 메소드?가 있을까 찾아보다가 안나와서 아니 메소드만 찾으려하지 말고 뭔가 수학적인 방법이 있을 것 같아서 다시 생각해봄package till; import java.util.*; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int x=scan.nextInt(); int a=scan.nextInt(); //배열에 쪼개어 저장 //첫번째 input만큼 for문 돌려 배열 안.. 2019. 1. 30. [JAVA] 백준 2839번 문제: https://www.acmicpc.net/problem/2839dp는 메모리는 많이 차지하나, 빨리 푸려고 쓸 때 쓰는 방법dp 문제 풀 때 tip -> 문제에서 제시된 범위 ex( 2 2019. 1. 27. 알고리즘 Pseudo-code 모음 ■ 순차검색 알고리즘 (Pseudo-code) void seqsearch(int n, // 입력(1) const keytype S[], // (2) keytype x, // (3) index& location) { // 출력 location = 1; while (location n) location = 0; } ■ 이분검색 알고리즘 void binsearch(int n, // 입력(1) const keytype S[], // (2) keytype x, // (3) index& location) // 출력 { index low, high, mid; low = 1; high = n; location = 0; while (low 2018. 12. 17. Branch-and-Bound 수업 필기 2. Branch-and-Bound(분기한정법): '최적의 경우'를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다'라는 범위(bound)를 정해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다. branch-and-bound 알고리즘의 원리 - 각 노드를 검색할 때 마다, 그 노드가 promising한지의 여부를 결정하기 위해서 한계값(bound)을 계산한다.- 그 bound는 그 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계를 나타낸다.- 따라서 만약 그 bound가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속할 필요가 없으므로, 그 노드는 non-promising 할 수 있다. 3. O.. 2018. 12. 17. Backtracking 수업 필기 ===================11223.Backtracking알고리즘: 해답이 될 가능성이 있는지를 확인하고, 유망하지 않다면 더 이상 깊게 들어가지 않고 부모 노드로 돌아오는 방식을 취한다. => 해답이 될 가능성이 없으면 배제하고, 부모노드로 되돌아가면서 풀이시간을 단축한다. 효과-> 엄청 효율적이다. The backtrack algorithm has the ability to yield thesame answer with for fewer than m trials. 5.백트래킹 기법? 백트래킹 (Backtracking) 기법은 해를 찾는 도중에 ‘막히면’(즉, 해가 아니면) 되돌아가서 다시 해를 찾아 가는 기법이다? 백트래킹 기법은 최적화 (optimization) 문제와 결정 (decisio.. 2018. 12. 17. Greedy 수업 필기 26.그래프 용어 (참고: https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html)비방향성 그래프->양방향 통행 도로를 생각->엣지를 통해서 양 방향으로 갈 수 있다. ->ex) 정점 a와 정점 b를 연결하는 엣지는 (a,b)와 같이 정점의 쌍으로 표현한다. (a,b)와 (b,a)는 동일 방향 그래프->일방 통행 도로를 생각->엣지에 방향성이 존재하는 그래프 27.신장트리란?->'부분'그래프->&G안에 모든 정점을 포함하며&트리가 되는(임의의 노드에서 다른 노드로 가는 경로가 유일, 회로가 존재하지 않는다, 모든 노드는 서로 연결, 엣지를 하나 자르면 트리가 두 개로 분리, 엣지의 수는 노드의 수에서 1을 뺀 것과 같다)(connected a.. 2018. 12. 17. Prev. 1 2 3 Next.
