SSAFY21 20220210 트리, BFS, DFS 트리 트리의 개념 비선형 구조 원소들간에 1:n 관례를 가지는 자료구조 트리의 정의 노드 - 트리의 원소 한개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족 노드 중 최 상위 노드를 루트(root)라고 한다. 나머지 노드들은 n(≥0)개의 분리 집합으로 분리될 수 있다. 분리된 집합들을 각각 하나의 트리가 되며, 루트의 부 트리(subtree)라고 한다. 간선 - 노드와 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결 형제 노드(sibling node) - 같은 부모 노드의 자식 노드들 조상 노드(ancestor node) - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리 자손 노드(deceden.. 2022. 2. 10. 20220208 LinkedList 리스트 순서를 가진 데이터의 집합을 가리키는 추상자료형 순차리스트 : 배열을 기반으로 구현된 리스트 연결리스트 : 메모리의 동적할당을 기반으로 구현된 리스트 순차리스트 삽입/삭제 연산 관정에서 연속적인 메모리 배열을 위해 원소들을 이동해야함 원소의 개수가 많고 삽입/삭제 연산이 빈번할수록 소용시간 증가 배열의 크기가 정해진경우 실제로 사용될 메모리 보다 크게 할당하여 메모리 낭비 혹은 할당된 메모리보다 많은 자료를 사용하여 새롭게 배열을 구성해야함 연결리스트 자료의 논리적인 순서와 메모리상의 물리적인 순서가 일치하지 않음 개별적으로 위치한 각 원소를 연결하여 하나의 전체적인 자료구조를 생성 링크를 통해 원소에 접근 자료구조의 크기를 동적으로 조정가능해, 메모리의 효율적인 사용이 가능 노드 연결 리스트에서.. 2022. 2. 10. 20220207 APS 기본 순열(Permutation) 선택한 결정의 순서가 의미 있는 경우 nPr = n * (n-1) * (n-2) * ... * (n-r+1) 조합 순서가 필요없고 선택한 결정만 중요한 경우 $nCr = {n!\over (n-r)! r!}$ nCr = n-1Cr-1 + n-1Cr → 재귀적 표현 nC0 = 1 부분집합 순열과 조합을 이용하여 전체 집합에 대한 부분을 찾는 것 스택 스택의 특성 : 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 스택에 저장된 자료는 선형구조 선형구조 : 자료 간의 관계가 1:1의 관계 비선형구조 : 가료 간의 관계가 1:N의 관계(ex : tree) 후입선출구조(LIFO) top : 저장된 원소 중 마지막 원소 주요 연산 push : 삽입 pop : 자료 삭제 peek :.. 2022. 2. 10. 20220203 Algo 표준 입출력 System.in : InputStream (byte 단위 입력) System.out System.err java.util.Scanner : 파일, 입력 스트림등에서 데이털르 일겅 구분자로 토큰화하고 다양한 타입으로 형변환하여 리턴해주는 클래스 데이터 형변환으로 인한 편리함 대량의 데이터 처리 시 수행시간이 비효율적 BufferedReader : 라인 단위로 입력을 받아 수행시간이 효율적임 next → 공백으로 문자를 split함 구분자이전까지 커서를 이용해서 값을 읽어들임. nextLine → Enter에서 개행문자로 공백인 엔터만 반환하므로 nextLine을 하나 더 추가해서 개행을 flush해줌 Enter까지 커서를 이용해서 값을 읽어들임. java.io.BufferedReader : .. 2022. 2. 4. 20220127 JAVA 공공데이터 XML SWING 공공데이터 공공데이터란? 공공기관이 만들어내는 모든 공적인 정보 데이터의 형태 CSV : Comma Separated Value xml : 태그를 통해 데이터 형식 정의 json : JavaScript Object Notation을 통해 데이터 형식 정의 파싱 문서에서 필요한 정보를 얻기 위해 태그를 구별하고 내용을 추출하는 과정 전문적인 parser 활용 SAX parser : Simple API for XML parser 문서를 읽으면서 태그의 시작, 종료 등 이벤트 기반으로 처리하는 방식 DOM parser : Document Object Model 문서를 다 읽고 난 후 문서 구조 천체를 자료구조에 저장하여 탐색하는 방식 SAX : 빠름, 한번에 처리하기에 다양한 탐색이 어려움 DOM : 느림, .. 2022. 2. 4. 20220126 JAVA I/O & Stream I/O 와 Stream 데이터는 한쪽에서 주고 한쪽에서 받는 구조 입력과 출력의 끝단 : Node 두 노드를 연결하고 데이터를 전송할 수 있는 개념 : Stream (단방향 통신만 가능) XXStream(Byte 처리), XXer(Char 처리) InputStream의 주요 메서드 Byte 한개씩 읽음 Buffer 만큼씩 읽음 Reader의 주요 메서드 Buffer 만큼씩 읽음 File : 파일과 디렉토리를 다루는 클래스 String name 대신 File 객체 사용 가능 노드 스트림 활용 FileReader, FileWriter 보조 스트림 보조 스트림 : Filter Stream, Processing Stream 다른 스트림에 부가적인 기능을 제공하는 스트림 스트림 체이닝 (Stream Chainin.. 2022. 2. 4. 20220125 JAVA 예외처리 에러와 예외 어떤 원인에 의해 오동작하거나 비정상적으로 종료되는 경우 Error : 프로그램의 비 정상적 종료를 막을 수 없음 → 디버깅필요 Exception : 프로그램 코드에 의해 수습될 수 있는 상황 try ~ catch 구문 try 밑에 예외가 발생할 수 있는 코드 catch 밑에 예외가 발생했을때 처리할 코드 JVM이 해당 Exception 클래스의 객체 생성 후 던짐(throw) 적절한 try-catch 구문을 만들어 예외 처리가 완성되야함 다중 exception handling try 블록에서 여러 종류의 예외가 발생할 경우 하나의 try 블록에 여러 개의 catch 블록 추가 가능!! Checked exception : 대처 코드가 없으면 컴파일 하지 않음 finally : 예외 발생 여부.. 2022. 2. 4. 20220124 JAVA 추상클래스 추상 클래스 정의 자손 클래스에서 반드시 재정의해서 사용되기 떄문에 조상의 구현이 무의미한 매서드 abstract 클래스는 상속 전용의 클래스 클래스의 구현부가 없는 메서드가 있으므로 객체를 생성할 수 없음 하지만 상위 클래스 타입으로써 자식을 참조할 수는 있다. Vehicle v = new Vehicle( ); // 불가능 Vehicle v = new DieselSUV( ); // 자식을 참조하는 것은 문제 없음 abstract 메소드가 있는 클래스는 abstract class가 되어야함 abstract class로는 객체 생성 불가능, 자식을 참조하는 것은 가능 abstract 메소드는 무조건 재정의 되야함 구현의 강제를 통해 프로그램의 안정성 향상 인터페이스 모든 메서드가 abstract 형태 클래.. 2022. 2. 4. 20220120 JAVA 생성자 및 상속 상속 기존 클래스의 자산(멤버)을 자식 클래스에서 재사용하기 위한 것 ( 부모의 생성자와 초기화 블록은 상속 X) 코드의 절감 → 부모의 코드 변경시 모든 자식들에게도 적용 → 유지 보수성 향상 상속의 적용 : extends 키워드 사용 항상 모든 클래스는 extends명령어를 사용하지 않으면 default로 Object를 상속한다. 상속의 관계 Person is a Object ( 상속의 관계는 is a 관계라고 함) 단일 상속 (Single Inheritance) 다중 상속의 경우 여러 클래스의 기능을 물려받을 수 있으나 관계가 매우 복잡해짐(다이아몬드 상속), 자바는 단일 상속만 지원 포함 관계 상속 이외에 클래스를 재활용 하는 방법 2개 이상의 클래스에서 특성을 가져 올 때 하나는 상속, 나머지는.. 2022. 1. 20. 이전 1 2 3 다음 728x90 728x90