전체207 DFS/BFS DFS/BFS를 이용하여 푸는 문제는 코딩 테스트에서 흔히 나오는 유형 중 하나입니다. 알고리즘 및 자료구조에서 탐색 (search) 란, 많은 양의 데이터 중에서 원하는 특정 데이터를 찾는 과정을 의미합니다. DFS는 depth-first search, 즉 깊이 우선 탐색이라고 불리며, BFS는 breadth-first search, 즉 너비 우선 탐색이라고 불립니다. 두 방법 모두 이름에서 알 수 있듯 탐색 (search)를 수행하는 알고리즘입니다. 이를 이해하기 위해서는 먼저 stack과 queue, 그리고 재귀 함수에 대한 이해가 선행되어야 합니다. 이 글에서는 해당 내용들을 전부 알고 있다고 전제하겠습니다. DFS와 BFS는 모두 그래프 자료구조를 탐색할 떄 사용하는 알고리즘입니다. 그래프에 대.. 2021. 2. 2. 구현 코딩 테스트 및 온라인 저지 사이트에서 자주 접하게 되는 문제 유형들 중 하나가 구현 문제입니다. 구현 문제란, 머릿속에 있는 알고리즘을 코드로 옮기는 과정을 의미합니다. 엄밀히 말하자면 모든 문제가 구현 문제인 셈입니다. 구체적으로, 구현 문제는 프로그래밍 언어의 기본 문법구조와 자료구조를 이용하여, 특정 문제를 해결하는 문제입니다. 몇 개의 예시를 들면 다음과 같습니다: 브론즈 5 - 별 찍기 - 1: www.acmicpc.net/problem/2438 골드 5 - 빗물: www.acmicpc.net/problem/14719 골드 4 - 아기 상어: www.acmicpc.net/problem/16236 (삼성전자 기출 문제) 골드 2 - 2048 (Easy): www.acmicpc.net/proble.. 2021. 2. 1. 그리디 그리디 (Greedy Method) 알고리즘에 대해 다루어보고자 합니다. Greedy는 한국어로 번역하여 탐욕법, 또는 욕심쟁이 알고리즘이라고도 합니다. 그리디 알고리즘이라고도 하는데, 개인적으로 알고리즘보다는 방법 (method)이 더 어울리는 표현이라고 생각합니다. 이하 '그리디 알고리즘' 이라고 표현을 통일하겠습니다. 그리디 알고리즘은 이름에서 알 수 있듯, 단순하게 탐욕적으로 문제를 해결하는 방법을 의미합니다. 즉, 지금 당장 현재 상황에 가장 좋은 선택지를 고르는 방법을 뜻합니다. 중요한 점은 이 선택이 추후에 미칠 영향에 대해서는 고려하지 않는다는 점입니다. 따라서 최적해를 보장하지는 않습니다. 그리디 알고리즘은 그 의미가 매우 넓습니다. 두루뭉실하게 '현재 가장 좋은 선택지를 고른다'고 뜻이.. 2021. 1. 30. [백준 2357번] 최솟값과 최댓값 난이도: 골드 1 문제 링크:www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 기말고사 전에 공부해서 풀었던 문제이지만... 블로그에 글로 정리하기에는 바빠서 지금에서야 정리해서 올립니다. 언뜻 보면 쉬워 보이는 최솟값, 최댓값 찾기 문제입니다. 처음엔 별 생각 없이 배열에 정렬해서 넣고 주어진 구간을 전부 탐색하여 최솟값, 최댓값을 찾아왔으나... 시간 초과가 걸렸습니다. 숫자의 크기가 크고, 갯수가 최대 10만 개가 되.. 2020. 12. 23. [백준 1655번] 가운데를 말해요 난이도: 골드 2 문제 링크: www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 제한 시간이 매우 짧은 (0.1초) 문제입니다. 반면 메모리는 상대적으로 넉넉한 편인 문제 같네요. 저는 다음과 같이 접근했습니다. 두 개의 Priority Queue minPQ, maxPQ를 둡니다. minPQ는 제일 작은 수가 top에, maxPQ는 제일 큰 수가 top에 위치합니다. 수를 입력 받아서 다음을 기준으로 push합니다. maxPQ의 element .. 2020. 12. 23. [백준 1107번] 리모컨 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 처음에는 각 숫자 자리수별로 비교해서 가장 가까운 수를 찾는 방법으로 하려다가... 굉장히 비효율적이고 정확하지 않은 알고리즘이 완성되어서 (string으로 입력받은 N을 변환하는 등) 혹시...? 하고 접근해 본 브루트 포스 메소드로 성공적으로 푼 문제입니다. 아래와 같이 접근했습니다. 숫자 0~9에 대해, bool 타입의 isBroken array를 만듭니다. .. 2020. 11. 28. 이전 1 ··· 25 26 27 28 29 30 31 ··· 35 다음
