문제 풀이/탐색ㆍ그래프 6
[백준] 10026 (적록색약)

#1 알고리즘#1-1 탐색 문제누가봐도 탐색 문제처럼 생겼다. 그렇다면 어떤 탐색을 수행할 것인가? #1-2 탐색 목표RRRBBGGBBBBBBRRBBRRRRRRRR나는 위 테스트 케이스에서 각 알파벳 하나씩을 순회하며, 1113322333333443344444444∴ 색맹 아닌 기준으로 구역의 수는 총 4개와 같은 식으로 변경할 것이다. '인접한 같은 색'끼리는 같은 숫자를 공유하고, '인접한 다른 색'은 서로 다른 숫자를 지닌다. 이렇게 만들려면, 인접한 다른 색으로 가기 전에 먼저 인접한 같은 색에 서로 같은 숫자를 마킹하는 로직이 필요하다. #1-3 Deque 활용 Double-ended queue - WikipediaFrom Wikipedia, the free encyclopedia Abstrac..
문제 풀이/탐색ㆍ그래프 2024.11.27

[백준] 14940 (쉬운 최단거리)

#1 알고리즘#1-1 '최단 거리'의 의미이 문제에서 '최단 거리'란, '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 1차원에서는 간단하다. 검은색 선의 길이와 '최단 거리'가 비례하기 때문이다 (이미 방문한 지역은 다시 방문하지 않는다). 2차원이라면 문제가 복잡해진다. 선의 길이와 '최단 거리'가 비례하지 않는다. 2에서 1로 가는 빨간색 선은 '최단 거리'면서 동시에 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 초록색 선은 '최단 거리'는 아니지만, 빨간색 선과 마찬가지로 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이다. 정리하면, 2차원에서 '최단 거리'는 반드시 '목표 지점(2)으로부터 한번 움직일 때마다 +1한 값'이지만, 역으로 '목표 지점(2)..
문제 풀이/탐색ㆍ그래프 2024.11.13

[백준] 1260 (DFS와 BFS)

#1 알고리즘DFS 및 BFS 알고리즘을 알고 있는지 묻는 간단한 문제다. 하지만, 약간 신경 쓸 점이 3가지 있다. 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 인접 배열을 정렬하면 된다. 나는 퀵 정렬을 이용했다.2. 정점의 개수 N(1 ≤ N ≤ 1,000) 문제에서 출제되는 정점은 1부터 시작한다. 즉, 1-based indexing을 사용하고 있다. 나는 이 문제를 풀기 위해 예전에 정리해 게시글로 남겨두었던 BFS 및 DFS 알고리즘 코드를 그대로 가져다 쓸 건데, 문제는 해당 코드들은 정점이 0부터 시작한다는 조건 하에 짜여진 코드들이다. 즉, 정점이 0-based indexing을 사용하고 있다. 이 차이를 해소하기 위해서 '인접 배열들의 리스트(lis..
문제 풀이/탐색ㆍ그래프 2024.09.24

[백준] 2805 (나무 자르기)

#1 개요#1-1 문제 이해'나무를 자르는 높이(cuttingHeight)'가 무엇인지를 묻는 문제다. 그리고 cuttingHeight의 범위는 0 ~ 1,000,000,000이다. 따라서, cuttingHeight를 1씩 증가시켜서 일일히 확인하는 방법은 시간 관계상 힘들다. 다행인 것은 cuttingHeight가 증가함에 따라, 얻어지는 '목재의 량(woodQuantity)'의 감소한다는 사실이다. cuttingHeight가 감소하면 woodQuantity는 그대로거나 감소한다. cuttingHeight가 index고, woodQuantity는 value인 배열 woods가 있다고 가정하자. 그 배열의 모습은 아래와 같다. #1-2 가상의 배열 'woods'M이 285라고 가정한다. 그리고 M값을 만..
문제 풀이/탐색ㆍ그래프 2024.03.06

[백준] 1920 (수 찾기)

#1 알고리즘#1-1 이진 탐색 (Binary search)#1 알고리즘 #1-1 #1-2 이렇게 해서 x의 인덱스 i를 찾으면 좋겠지만, 이 x가 배열 values 어디에도 존재하지 않는 경우도 있을 것이다. 이 경우엔 어떻게 처리해야 할까? #1-3 업 앤 다운 게임은 우리나kenel.tistory.com시간 초과가 뜨지 않게 하기 위해서 배열에 이진 탐색을 수행한다.  #1-2 힙 정렬 (Heap Sort)#1 알고리즘 #1-1 힙(heap)이라는 영어 단어의 사전적 의미는 쌓아 놓은 무더기다. 그리고 이 단어는 프로그래밍에서도 사용된다. 첫째로 메모리 영역에서, 둘째로 자료구조에서다. 이 둘은 서로 다kenel.tistory.com이진 탐색을 수행하려면 먼저, 배열이 정렬되어있어야 한다. 나는 이..
문제 풀이/탐색ㆍ그래프 2023.12.25

[백준] 1654 (랜선 자르기)

#1 알고리즘#1-1 #1-2 중복된 원소 값이 있는 경우의 이진 탐색 (Binary Search)#1 알고리즘 이진 탐색 (Binary search) #1 알고리즘 이렇게 해서 x의 인덱스 i를 찾으면 좋겠지만, 이 x가 배열 values 어디에도 존재하지 않는 경우도 있을 것이다. 이 경우엔 어떻게 처리해야 할까? 업kenel.tistory.com해당 글을 읽어야 이 다음 부분을 이해할 수 있다 #1-3 #1-4여기에서 정리했던 binarySearchLastIndex()와 다른 부분을 강조 표시했다.
min과 max을 각각 2로 나눈 뒤 더하는 이유는 int형의 오버플로우 방지를 위해서다. 또, values는 내림차순이기 때문에, Up 및 Down을 판단하는 코드에서의 부등호를 반대 방향으로 돌렸다...
문제 풀이/탐색ㆍ그래프 2023.11.04
1
더보기

티스토리툴바