IT Hyeon's study IT Hyeon's study

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 12. 백트래킹 백트래킹이란?어떤 가능성이 없는 곳을 알아보고 되돌아가는 것  백트래킹 알고리즘이란? 가능성이 없는 곳에서는 되돌아가고 가능성이 있는 곳을 탐색하는 알고리즘 이다답을 찾는 과정에서 가능성이 없는 곳에서 백트래킹백트래킹을 통해 해가 될 가능성이 없는 탐색 대상을 배제할 수 있으므로 탐색 효율이 단순히 완전 탐색하는 방법보다 백트래킹이 효율적이다 유망 함수란? 백트래킹 알고리즘의 핵심, 해가 될 가능성을 판단하는 것이다가능성은 유망 함수라는 것을 정의하여 판단한다 과정유효한 해의 집합 정의위 단계에서 정의한 집함을 그래프로 표현유망함수를 정의백트래킹 알고리즘을 활용해서 해를 찾음 관련 문제 모음..

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 집합 개념순서와 중복이 없는 원소들을 갖는 자료구조상호 배타적 집합(교집합이 없는 집합 관계)상호 배타적 집합 특성을 활용하는 분야이미지 분할 : 서로 다른 부분으로 나누는 데 사용도로 네트워크 구성: 각 도로가 교차하지 않도록 설계-> 교차로 혼잡을 줄임최소 신장 트리 알고리즘 구현 -> 간선을 추가할 때마다 사이클을 형성하는지 여부게임 개발: 캐릭터 동작을 자연스럽게 구현 ex) 두 캐릭터가 겹치지 않도록 함클러스터링 작업 -> 각 작업이 서로 겹치지 않도록 구성 할 수 있다  연산 유니온 - 파인드 알고리즘 집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다합치기 -> 유니온 union탐색 -> 파인..

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 트리- 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다- 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤접어 놓은 모양이다- 나무 밑둥 즉, root가 맨 위에 있다- 트리는 부모 - 자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조  트리 구성루트 노드-> 노드 중 가장 위에 있는 노드를 루트 노드라고 한다 에지-> 노드와 노드 사이에는 이어주는 선이 있다 이것을 간선 또는 에지 라고 한다 노드-> 간선으로 연결된 노드들은 서로 부모 - 자식 관계가 있다고 표현한다간선으로 직접 연결된 노드중 상대적으로 위에 있는 노드를 부모노드, 아래에 있는 노드를 자식 노드라고 한다자식이 없는 노..

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 해시- 해시는 해시 함수를 사용하여 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 이다- 해시는 키를 이용해서 데이터 탐색에서 빠르다는 장점이 있다  특징 - 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 없다- 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색 할 수 있다- O(1)으로 동작- 값을 적절하게 변환해야 인덱스로 사용 가능   해시 함수 우선 해시 함수를 구현할 때 고려할 사항 1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안된다2. 해시 함수가 변환한 값의 충돌은 최대한 ..

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다.  1. 큐1) 개념큐는 줄을 서다 라는 뜻을 가지고 있다선입 선출 즉, 먼저 들어간 데이터가 먼저 나오는 자료구조 이다 - FIFO- 삽입하는 연산은 Enqueue, 꺼내는 연산을 Dequeue 라고 한다- 큐의 동작방식은 작업 대기열, 이벤트 처리 등등 많이 활용한다 2) 과정 1. 빈 큐 하나 선언Queue queue = new LinkedList(); 2. 데이터 삽입 queue.add(3);queue.add(2);queue.add(4);queue.add(1); -삽입을 하면 3부터 순서대로 삽입을 한다.- 위 코드 처럼 순서는 3, 2, 4, 1 이 되겠다 3. 데이터 삭제queue.poll(); -..

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 06 스택 - 스택의 어원은 쌓는다 이다 - LIFO 구조 이다 (후입 선출) - Vector 클래스를 상속받기에 Thread-Safe하다 - java.util.Stack 클래스를 통해 동작을 제공한다. 스택의 ADT 정의 ADT란? Abstract Data Type(추상자료형)으로 인터페이스만 있고 실제로 구현은 되지 않은 자료형을 말한다. 일종의 '자료형의 설계도'라고 생각하면 된다. ※ 언어에 따라 표준라이브러리에서 스택 제공 여부는 다르다. 자바는 컬렉션 프레임워크에서 Stack 클래스를 제공하기 때문에 Stack클래스의 객체를 생성해서 사용하면 된다. Stack 클래스 사용하기 Push() Stac..

이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 00 코딩 테스트를 준비하기 전에 효과적인 전략 1. 첫번째 기록하라 2. 시험 보듯 공부하라 3. 짧은 시간 공부해서는 절대 코딩 테스트를 통과할 수 없다. 4. 나만의 언어로 요약하라 01 코딩 테스트 효율적으로 준비하기 문제 분석 연습하기 1. 문제를 쪼개서 분석하라 2. 제약 사항을 파악하고 테스트 케이스를 추가하라 3. 입력값을 분석하라 4. 그리디하게 접근할 때는 근거를 명확히 해라 5. 데이터 흐름이나 구성을 파악하라 의사 코드로 설계하는 연습 원칙 1 : 프로그래밍 언어로 작성하면 안됨 원칙 2 : 일반인도 이해할 수 있는 자연어로 작성해야 함 원칙 3 : 일정한 형식이 없음 -> 자유롭게 방..