[묘공단] 코딩 테스트 합격자 되기 책 정리7 [묘공단] 코딩 테스트 합격자 되기 6주차 이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 12. 백트래킹 백트래킹이란?어떤 가능성이 없는 곳을 알아보고 되돌아가는 것 백트래킹 알고리즘이란? 가능성이 없는 곳에서는 되돌아가고 가능성이 있는 곳을 탐색하는 알고리즘 이다답을 찾는 과정에서 가능성이 없는 곳에서 백트래킹백트래킹을 통해 해가 될 가능성이 없는 탐색 대상을 배제할 수 있으므로 탐색 효율이 단순히 완전 탐색하는 방법보다 백트래킹이 효율적이다 유망 함수란? 백트래킹 알고리즘의 핵심, 해가 될 가능성을 판단하는 것이다가능성은 유망 함수라는 것을 정의하여 판단한다 과정유효한 해의 집합 정의위 단계에서 정의한 집함을 그래프로 표현유망함수를 정의백트래킹 알고리즘을 활용해서 해를 찾음 관련 문제 모음.. 2024. 5. 25. [묘공단] 코딩 테스트 합격자 되기 5주차 이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 집합 개념순서와 중복이 없는 원소들을 갖는 자료구조상호 배타적 집합(교집합이 없는 집합 관계)상호 배타적 집합 특성을 활용하는 분야이미지 분할 : 서로 다른 부분으로 나누는 데 사용도로 네트워크 구성: 각 도로가 교차하지 않도록 설계-> 교차로 혼잡을 줄임최소 신장 트리 알고리즘 구현 -> 간선을 추가할 때마다 사이클을 형성하는지 여부게임 개발: 캐릭터 동작을 자연스럽게 구현 ex) 두 캐릭터가 겹치지 않도록 함클러스터링 작업 -> 각 작업이 서로 겹치지 않도록 구성 할 수 있다 연산 유니온 - 파인드 알고리즘 집합 알고리즘에 주로 쓰이는 연산은 합치기와 탐색이다합치기 -> 유니온 union탐색 -> 파인.. 2024. 5. 22. [묘공단] 코딩 테스트 합격자 되기 4주차 - 트리 이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 트리- 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다- 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤접어 놓은 모양이다- 나무 밑둥 즉, root가 맨 위에 있다- 트리는 부모 - 자식 관계의 노드들로 이루어지며 계층적인 구조를 나타내는 자료구조 트리 구성루트 노드-> 노드 중 가장 위에 있는 노드를 루트 노드라고 한다 에지-> 노드와 노드 사이에는 이어주는 선이 있다 이것을 간선 또는 에지 라고 한다 노드-> 간선으로 연결된 노드들은 서로 부모 - 자식 관계가 있다고 표현한다간선으로 직접 연결된 노드중 상대적으로 위에 있는 노드를 부모노드, 아래에 있는 노드를 자식 노드라고 한다자식이 없는 노.. 2024. 5. 7. [묘공단] 코딩 테스트 합격자 되기 4주차 이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 해시- 해시는 해시 함수를 사용하여 변환한 값을 인덱스로 삼아 키와 값을 저장해서 빠른 데이터 탐색을 제공하는 자료구조 이다- 해시는 키를 이용해서 데이터 탐색에서 빠르다는 장점이 있다 특징 - 키 자체가 해시 함수에 의해 값이 있는 인덱스가 되므로 값을 찾기 위한 탐색 과정이 없다- 단방향으로만 검색할 수 있는 대신 빠르게 원하는 값을 검색 할 수 있다- O(1)으로 동작- 값을 적절하게 변환해야 인덱스로 사용 가능 해시 함수 우선 해시 함수를 구현할 때 고려할 사항 1. 해시 함수가 변환한 값은 인덱스로 활용해야 하므로 해시 테이블의 크기를 넘으면 안된다2. 해시 함수가 변환한 값의 충돌은 최대한 .. 2024. 5. 6. [묘공단] 코딩 테스트 합격자 되기 3주차 이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 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(); -.. 2024. 4. 29. [묘공단] 코딩 테스트 합격자 되기 2주차 이 글은 책 코딩테스트 합격자 되기 - 자바편 (골든래빗 - 김희성저)의 내용이 포함되어있습니다. 06 스택 - 스택의 어원은 쌓는다 이다 - LIFO 구조 이다 (후입 선출) - Vector 클래스를 상속받기에 Thread-Safe하다 - java.util.Stack 클래스를 통해 동작을 제공한다. 스택의 ADT 정의 ADT란? Abstract Data Type(추상자료형)으로 인터페이스만 있고 실제로 구현은 되지 않은 자료형을 말한다. 일종의 '자료형의 설계도'라고 생각하면 된다. ※ 언어에 따라 표준라이브러리에서 스택 제공 여부는 다르다. 자바는 컬렉션 프레임워크에서 Stack 클래스를 제공하기 때문에 Stack클래스의 객체를 생성해서 사용하면 된다. Stack 클래스 사용하기 Push() Stac.. 2024. 4. 21. 이전 1 2 다음
