본문 바로가기

Etc96

이분 탐색(Binary Search) 이분 탐색 BigO: O(log N) 결정 문제의 답이 이분적일 때(Yes or No) 사용할 수 있는 탐색 기법이다. 데이터가 오름차순 정렬된 배열에서 특정 값(N)을 찾아낸다. 정렬된 리스트에서 검색 범위를 줄여 나가면서 검색 값을 찾는다. 검색이 반복될 때마다 검색 범위가 반으로 줄어들기 때문에 속도가 빠르다. 예를 들어서 1~50의 숫자가 오름차순 정렬된 카드 더미에서 28번 카드를 찾는다고 가정하자. 첫 번째 카드부터 I번째 카드는 v[i], 28은 val로 정의할 때, 우리가 찾고자 하는 값은 i를 증가시키면서 v[i] >= val가 되는 지점(처음 결정 문제가 True가 되는 지점)의 i 값이다. 이분 탐색의 아이디어는 경계를 포함하는 구간 [start, end]을 잡은 뒤 구간의 길이를 절.. 2023. 1. 25.
분할 정복(Divide & Conquer) 분할 정복 크고 방대한 문제를 쉽게 풀 수 있는 문제 단위로 나누고, 그것들을 다시 합쳐서 문제를 해결하는 방법이다. 일반적으로 재귀 함수를 통해 구현하며, 메모리 제한이 없다면 비교적 빠르게 문제를 해결할 수 있다. 부분 문제가 다른 부분 문제에 영향을 미치지 않는다. (DP의 경우 영향을 미친다.) Divide: 기존 문제를 작은 문제로 나눈다. → 큰 문제를 어떻게 나눌 것이고, 이 과정의 최종 목표는 무엇인가? Base Case: 더 작은 부분의 문제로 나누지 않아도 바로 답을 구할 수 있는 경우 Recursive Case: 같은 형태의 부분 문제로 쪼개야 하는 경우 Conquer: 나누어진 문제가 여전히 분할이 가능하면 또 다시 Divide를 수행하고, 그렇지 않으면 문제를 해결한다. Combi.. 2023. 1. 25.
[Python] 프로그래머스: 여행경로 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🐰 문제 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 🐰 제한 사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 .. 2023. 1. 5.
[Python] 백준 7569번: 토마토 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 🐰 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 .. 2023. 1. 4.
[Python] 백준 1260번: DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 🐰 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 🐰 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다.. 2023. 1. 3.
[Java] 백준 1012번: 유기농 배추 보호되어 있는 글 입니다. 2022. 11. 21.

티스토리툴바