본문 바로가기

분류 전체보기146

[알고리즘] 이분탐색(Binary Search)이란? ✔️ 이분탐색(이진탐색) 이란?이분탐색이란 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다.  처음과 마지막의 중간값을 선택하여, 찾고자 하는 값과 크고 작음을 비교하는 방식을 반복하여 탐색을 진행한다.따라서, 필수조건은 리스트가 오름차순으로 정렬되어야만 한다.  그림으로 이분탐색에 대해서 더 자세히 알아보자 ! 0.길이가 10인 오름차순으로 정렬된 배열이 있다고 하자. 31 이란 특정한 값의 위치를 찾고자한다. 1.먼저 low, high, mid 값 설정한다. low : 최소값의 인덱스 high : 최고값 인덱스mid : 중간값 인덱스2.설정된 중앙값(mid)가 31보다 작으므로, low의 인덱스를 mid+1로 설정하여 우측을 선택한다.(만약 중앙값(mid)이 31보다 큰 경우라면,.. 2024. 10. 2.
[백준] 6603 로또 자바 : 백트레킹 [실버2] ✔️ 문제 설명더보기문제독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있.. 2024. 10. 1.
[백준] N과M (1), (2), (3), (4) : 자바 백트레킹 이번 포스팅에서는 백준 N과 M 시리즈에 대해서 얘기해보자 ! 문제 (2),(3),(4)는 (1)에 조건이 추가된 문제들이다. N과 M(1) 알고리즘을 풀어봤다면 (2),(3),(4) 는 비교적 쉽게 풀 수 있다.✔️ N과 M (1) : 15649번arr : 출력할 수열을 담을 배열visited : 중복되지 않은 수를 출력하기 위해 방문 여부를 담을 배열import java.io.BufferedReader;import java.io.IOException;import java.util.StringTokenizer;import java.io.InputStreamReader;public class Main{ static int[] arr; static boolean[] visited; priv.. 2024. 10. 1.
[알고리즘] 백트래킹이란? & 대표 문제: 백준 15679 N과M(1) - 자바 ✔️ 백트래킹이란?백트래킹이란?해를 찾는 도중에 막히면 더이상 탐색하지 않고, 이전 단계로 되돌아가서(재귀) 해를 찾아나가는 기법을 의미한다. 백트래킹은 재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드(상태)가 제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외하고 다음 단계로 나아가는 방식이다. 이처럼 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning) 이라고 한다.  따라서, 백트래킹은 모든 노드를 DFS를 통해 탐색하면서 더 이상 필요가 없는 부분을 쳐내는 가지치기(pruning)를 하는 것이다.  DFS 완전탐색으로 경우의 수를 찾아야할 경우, 불필요한 탐색을 건너뛸 여지가 있다면 백트래킹을 이용할 수 있다. .. 2024. 10. 1.
[백준] 7576 토마토 : 자바 BFS [골드5] ✔️ 문제 설명 (펼치기)더보기문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 .. 2024. 10. 1.
[백준] 1600 말이 되고픈 원숭이 : 자바 BFS [골드 5] ✔️ 문제 설명 (펼치기)더보기문제동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x   x  말  x   x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.이제 원숭이는.. 2024. 9. 29.

티스토리툴바