본문 바로가기

묘공단6

[묘공단] 완전 탐색이란? 알고리즘 기법 중 완전 탐색(Exhaustive Search)이란 것이 있다.이름만 들어도 '전부 다 보는 기법' 뭐 이런 것이겠거니 유추가 되지 않는가? 그런데 완전 탐색에도 종류가 있다.1. 브루트 포스(Brute Force): 가능한 모든 경우를 시도하는 방법이다. 비밀번호 해킹 같은 주제에서 듣기 쉽다.2. 백트래킹(Backtracking): 가능한 모든 경우를 시도하되, 불필요한 경우를 미리 제거해 효율을 높이는 방법이다. 주로 재귀적으로 사용되며 유망하지 않은 경로는 더 이상 탐색하지 않는 식이다.3. 재귀(Recursion): 문제를 여러 작은 문제로 나누어 푸는 방식이다. 재귀적으로 모든 가능한 경우를 시도한다.4. 순열과 조합(Permutations and Combinations): 가능.. 2024. 5. 20.
[묘공단] 다이나믹 프로그래밍을 배워야 하는 이유 다이나믹 프로그래밍.동적 계획법.내가 지금 이걸 왜 배워야 하는데? 대표적인 알고리즘 설계 기법이 그리디, 디바이드앤컹쿼(ㅋ), 다이나믹 프로그래밍이다.기본이니까 배워야지! 프로그래머스 레벨2 정도에 오니까 인덱스 가지고 배열을 요리조리 돌려서 문제 푸는 걸로는 안 된다.한 예를 들어 보겠다.https://school.programmers.co.kr/learn/courses/30/lessons/12945 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr난 이 문제를 아래와 같이 풀었다.class Solution { public int solution(int.. 2024. 5. 20.
[묘공단] 너비 우선 탐색(BFS) 깊이 우선 탐색을 봤다면 너비 우선 탐색을 볼 차례다. 1. 너비 우선 탐색이란?깊이 우선 탐색은 시작 노드에서 한 방향으로 끝까지 간 다음에 다른 방향에 대해서도 반복하는 알고리즘이다.너비 우선 탐색은 이름에서 알 수 있듯이시작 노드에서 출발해서인접한 노드를 먼저 탐색하고,그 다음 인접한 모드들의 인접한 노드들을 탐색하는 방식으로 진행하는 알고리즘이다.BFS는 큐로 구현되는 경우가 많다.2. BFS를 굳이 쓰는 이유가 뭘까?최단 경로.가중치가 동일한 그래프에서 BFS는, 시작 노드로부터 목표 노드까지의 최단 경로를 보장한다. 다른 경우라면레벨 순서대로 탐색해야 하거나, 특정 깊이에서 모든 노드를 탐색해야 하는 경우에 쓴다. 3. BFS는 어떻게 동작하나?1. 시작 노드를 큐에 추가한다.* 잠깐 *트리라.. 2024. 5. 19.
[묘공단] 깊이 우선 탐색(DFS) 코테를 풀다 보면 깊이우선탐색, 너비우선탐색을 자주 볼 수 있다.해당 알고리즘은 무엇일까? DFS, BFS는 트리를 순회하는 방법이다. 1. 트리라고 하면 아래와 같은 그림을 바로 떠올릴 수 있다. 그럼 아래와 같은 구조를 바탕으로 풀어야 하는 문제 유형은 무엇이 있을까?트리 문제는 주로 트리 순회, 이진 탐색 트리(BTS) 연산, 균형 트리, 특수 트리, 그리고 트리의 경로와 거리 계산으로 나뉜다.모든 걸 다 보면 좋을 것이고, 앞으로 다 살펴볼 것이지만 이번 시간에는 트리 순회 문제에 대해서만 다룬다.트리 순회 문제는 DFS, BFS를 이용해 특정 노드를 찾거나 순서를 출력하는 식이다.기억하자. 트리를 순회해야 된다? -> DFS나 BFS로 푼다. * 참고 *이진 탐색 트리 연산 문제는 삽입, 삭제,.. 2024. 5. 19.
[묘공단] 자바 - Queue 이야기 태초에 Iterable이 계셨고 그 아래에 자식 Collection이 계셨고 그걸 또 Queue가 계승하셨네.앞으로 Deque도 볼 건데 일단 머릿속에 큐(한 번 영어로 쓴 건 그 뒤로는 다 한글로 쓸 것임.)를 중심에 둬 보자.왜냐면 덱 인터페이스가 큐 인터페이스를 상속하기 때문이다.위 그림 상으로는 큐에 대해서 좀 보고 PriorityQueue만 보면 될 거 같지만LinkedList도 봐야 한다.왜? 링크드리스트는 List, 큐, 덱을 모두 구현하기 때문이다.나 같은 범부는 여기까지만 봐도 너무 신기하고 재밌고 이 언어 설계한 사람들이 진짜 천재 같아서 가슴이 두근두근하다.요즘 세상에 누가 자바 쓰냐고 하지만 나는 이 자바만 해도 너무 재밌을 거 같다! 큐(Queue)는 자바에서 컬렉션 프레임워크의 .. 2024. 4. 27.
[묘공단] 스택 이야기 지금까지 묘공단 관련 포스팅을 velog에서 했었는데 이제 티스토리로 옮기고 싶어서 여기에 적는다. 자료구조하면 보통은 스택부터 이야기를 들을 것이다.매우 쉽고 기본이 되니까.스택은 ADT(Abstract Data Type)다.구현된 부분이 없는 일종의 인터페이스 같은 것이다.ADT의 구현은 자바에서 자바 콜렉션 프레임워크에 되어 있다. 근데 스택은 콜렉션에 없다.스택 클래스가 따로 있다.그리고 덱 ADT가 구현된 ArrayDeque을 스택처럼 쓸 수 있다(이건 큐처럼도 쓴다. 양방이 다 뚫려 있어서.). 이게 앞으로 나올 내용을 이해하기 위해 최소한으로 알고 있으면 될 내용이었다.1. 자바에서 스택을 쓸 경우는 뭐가 있을까? 후입선출(LIFO) 구조가 필요한 경우:웹 .. 2024. 4. 22.

티스토리툴바