알고리즘, 문제해결103 그리디 그리디 (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. [백준 1774번] 우주신과의 교감 난이도: 골드 4 문제 링크: www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 굉장히 재밌게 번역된 문제입니다. 번역되었다고 말하는 이유는, 이 문제는 원래 영문으로 된 문제입니다 (출처가 미국 정보 올림피아드). 그럼에도 전혀 번역되었다고 생각하지 못할 법한 내용으로 재밌게 번역되어 문제를 풀기에도 즐거웠네요. 문제를 자세히 읽어보면, 다음과 같이 요약할 수 있습니다. 정해진 노드가 입력으로 주어진다. 이미 건설된 노드 간의 엣지.. 2020. 11. 27. [백준 16236번] 아기 상어 이 문제는 삼성 SW 역량 테스트 기출문제 입니다. 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS를 이용한 탐색을 핵심으로 하는 문제입니다. BFS에 대한 이론적 배경은 여기를 참고하세요. BFS를 실제로 이용하여 문제를 푸는 접근법이 아직 생소하여, 인터넷 검색을 많이 활용했습니다. 문제가 내용이 긴데, 요약하면 아래와 같습니다. 상어는 본인보다 작은 물고기만 잡아먹을 수 있다. 상어는 빈 공간 혹은 자기보다 .. 2020. 11. 23. 이전 1 ··· 11 12 13 14 15 16 17 18 다음
