[PS #36] 이상한 술집 (13702)

September 18, 2021

1. 문제 개요 문제 링크 : https://www.acmicpc.net/problem/13702 난이도 : 실버 III 주제 : 이진 탐색 풀이 일자 : 2. 문제 접근 리스트가 아닌 정수데이터에서도 이진탐색으로 접근할 수 있다는 간단한 아이디어를 떠올리는데 아주 조금 애먹었다. 일반적인 이진 탐색과 같이 범위를 절반씩 좁혀서 탐색하는 것은 동일하다.…


[PS #35] 숫자 카드 2 (10816)

September 15, 2021

1. 문제 개요 문제 링크 : https://www.acmicpc.net/problem/10816 난이도 : 실버 IV 주제 : 이진 탐색 풀이 일자 : 2. 문제 접근 해시 테이블 혹은 Python 의 를 사용하면 아주 쉽게 풀 수 있는 문제이다. 하지만, 이진 탐색을 공부하고 있어서 굳이 이진 탐색으로 풀어보았다. 3. 소스코드 3-1. 해시 테이…


[ALG] 이진 탐색 (Binary Search)

September 14, 2021

본 포스트는 저자가 학습하며 작성한 글 이기 때문에 틀린 내용이 있을 수 있습니다. 지적은 언제나 환영입니다. 1. 이진 탐색 (Binary Search) 이진 탐색 (Binary Search) 은 정렬 되어 있는 리스트 에서 특정 값을 찾아내는 알고리즘이다. 오름차순, 내림차순의 여부는 크게 상관없으나 보통의 경우 '오름차순으로 정렬된 데이터' 를 사…


[PS #34] 수 찾기 (1920)

September 13, 2021

1. 문제 개요 문제 링크 : https://www.acmicpc.net/problem/1920 난이도 : 실버 IV 주제 : 이진 탐색 풀이 일자 : 2. 문제 접근 리스트에서 특정 수의 존재 유무를 검사하는 문제이다. 선형탐색으로 풀 수도 있으나, 당연히 시간 제한이 존재해 보다 빠른 알고리즘을 채택해야한다. 이진탐색 (Binary Search) …


[PS #33] 외판원 순회 2 (10971)

September 12, 2021

1. 문제 개요 문제 링크 : https://www.acmicpc.net/problem/10971 난이도 : 실버 II 주제 : DFS/BFS 풀이 일자 : 2. 문제 접근 DFS 로 순회하되, 노드 간 간선의 비용이 대칭적이지 않다. A → B 와 B → A 는 비용이 다를 수도 있다는 뜻이고 즉, 갈림길을 맞닥뜨리면 그대로 분기하여 모든 경우의 수를…


[PS #32] 네트워크 (43162)

September 12, 2021

1. 문제 개요 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43162 난이도 : Level 3 주제 : DFS/BFS 풀이 일자 : 2. 문제 접근 어렵지 않은 문제였다. 임의의 노드 한개에서 DFS 탐색한 이후 아직 방문하지 않은 임의의 노드에서 다시 DFS 탐색을 시작하는 것을 반복해서 …


[ALG] 시간복잡도와 빅오 (Big-O) 표기법

September 11, 2021

본 포스트는 저자가 학습하며 작성한 글 이기 때문에 틀린 내용이 있을 수 있습니다. 지적은 언제나 환영입니다. 1. 알고리즘의 비용 계산 특정 문제를 해결하는 알고리즘은 여러가지가 존재할 수 있다. 그 중 가장 최적의 알고리즘을 선택해야하는데, 그 선택의 기준으로 공간 복잡도 (Space complexity) 와 시간 복잡도 (Time complexit…


[PS #31] 타겟 넘버 (43165)

September 08, 2021

1. 문제 개요 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43165 난이도 : Level 2 주제 : DFS/BFS 풀이 일자 : 2. 문제 접근 재귀를 통해 0부터 시작하여 각 숫자마다 음수, 양수로 구분하여 더하는 2개의 분기를 만든다. 그렇게 모든 숫자를 다 더하면 모든 경우의 수를 …


[PS #30] 바이러스 (2606)

September 07, 2021

1. 문제 개요 문제 링크 : https://www.acmicpc.net/problem/2606 난이도 : 실버 III 주제 : DFS/BFS 풀이 일자 : 2. 문제 접근 1번 노드와 연결된 다른 컴퓨터의 개수를 단순히 세면 된다. DFS 와 BFS 둘다 사용해볼 수 있다. 간선이 끊긴 노드는 자연스럽게 탐색하지 않으니, 입력값에 따라 그래프만 잘 만…


[PS #29] 반복수열 (2331)

September 07, 2021

1. 문제 개요 문제 링크 : https://www.acmicpc.net/problem/2331 난이도 : 실버 IV 주제 : DFS/BFS 풀이 일자 : 2. 문제 접근 백준 DFS 문제 리스트에서 찾아 풀이한 문제인데, 굳이 DFS/BFS 같은 알고리즘을 사용해야하나? 라는 의문이 드는 문제였다. 반복을 검사하는 조건은 수열이 진행하면서 이전에 등장…