Joon's Blog Joon's Blog

Goal 1. 탐욕적 기법(Greedy Algorithm)의 개념 2. 탐욕적 기법(Greedy Algorithm)의 특징 3. 탐욕적 기법(Greedy Algorithm)의 구현 서론 가장 유명하지만 가장 기초적이어서, 알고리즘에 입문하기 가장 좋은 녀석입니다. 접근법이 굉장히 직관적이고 단순하기 때문에 알고리즘 대회, 코딩 테스트에서 적지 않게 볼 수 있습니다. 그래서 저는 그리디 알고리즘 문제를 적어도 10 문제 정도는 풀어보고 다른 알고리즘을 풀어보시는 걸 추천드립니다. 왜냐하면 10문제 정도 풀어보시면, 내가 생각하는 것을 코드로 구현하는 능력과 문제를 직관적으로 보는 능력이 생기기 때문입니다. 개념 서론이 길었습니다. 탐욕적 기법(Greedy Algorithm), 욕심쟁이 기법 혹은 그냥 그리..

문제 보기 정말 작심삼일이라고 고작 8일하고 포기했던 1일 1백준을 다시 시작합니다... 정말 직관적이고 쉬운 문제를 풀면서 자신감을 키우기 위해 그리디문제를 가져왔습니다. 풀이 연속하는 20일중 10일을 사용할 수 있다 .... 이런 경우에 캠핑을 가장 많이 사용하기 위해서는 어떻게 해야될까요? 당연히 휴가 시작날짜부터 바로 캠핑을 시작하는 것이 가장 많이 사용하는 방법일겁니다. 그렇게 되면 휴가 28일중 첫날부터 사용하여 연속하는 20일 동안 총 10일을 사용할수 있을것입니다. 그리고 남은 8일은 다시 연속하는 20일이 되기 때문에 사용횟수가 초기화되서 8일 모두 사용할 수 있게 됩니다. 이러한 상황을 이제 코드로 구현해봅시다. 이러한 Case 의 번호를 저장할 변수 a 를 선언합니다. 연속적인 연산..

Goal 너비 우선 탐색(BFS, Breadth-First Search)의 개념 너비 우선 탐색(BFS, Breadth-First Search)의 특징 너비 우선 탐색(BFS, Breadth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색은 시..

Goal 깊이 우선 탐색(DFS, Depth-First Search)의 개념 깊이 우선 탐색(DFS, Depth-First Search)의 특징 깊이 우선 탐색(DFS, Depth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색은 미로를 탐색하는 ..

그래프란? : 그래프(graph)는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조입니다. 그래프는 정점과 간선들의 집합이라고 할 수 있습니다. 그래프는 보통 지도에서 자주 사용하는 자료구조인데, 예를 들어 인천에서 서울까지의 최단거리, 최소비용 등을 구하는 데 사용합니다. 필요한 개념 및 용어 1. 정점(vertex) 와 간선(edge) 정점은 그래프의 위치, 간선은 정점들 간의 관계를 의미합니다. 2. 무방향 그래프(undirected graph) 와 방향 그래프(directed graph) 무방향 그래프는 간선을 통해 양 방향 이동이 가능하다. 방향 그래프는 간선을 통해 단 방향 이동이 가능하다. 3. 가중치 그래프(weight graph) 간선에 연결 강도를 표시할 수 있는 그래프 (ex..

문제분석 DP 유형의 문제들은 점화식을 도출하는 것이 문제의 전부입니다!! D[i] = i 번째 인덱스를 마지막으로 하는 수열의 최대 길이 arr[i] = 주어진 수열 이라고 정의하고 시작하겠습니다. 그러면, D[1] = 1 은 자명합니다. D[2] 부터는 주어진 수열의 데이터를 비교해야 합니다. 1. 이전 값 중에 arr[2] 보다 작은 값들을 모두 후보 인덱스로 둡니다. 2. D[후보 인덱스] 중에 최댓값을 구합니다. 3. 그 최댓값에 자기 자신인 1을 더해줍니다. 설명이 조금 복잡하니 예시문제로 다시 봅시다. 10 20 10 30 20 50 이러한 수열이 있습니다. 이때, D[4] 를 구하고자 합니다. 그러면 우선 arr[4] = 30 의 값 보다 작은 값들을 이전 인덱스에서 색출합니다. 10 20..

문제 분석 문제에 친절하게 스택을 사용하라고 나와있죠? ㅎㅎ 내용은 이렇습니다. 원하는 수를 사용하기 위해서는 반드시 스택에 push, pop 하는 과정을 거쳐야 합니다. 스택에 값은 아래의 그림처럼 채워집니다. 예를 들어, 가장 처음에 5를 사용해야 한다면 1 ~ 5 의 숫자를 push 한 후에 pop 을해서 사용하는 겁니다. 이게 이해가 되셨다면, 만들고자 하는 배열을 저장해야 하는데 이 배열을 큐에 저장하면 간단합니다. 입력 파트를 보면 먼저 입력된 값부터 스택에서 추출하기 때문입니다. 따라서 예시문제를 순서대로 큐에 push 하게 되면 아래 그림처럼 채워집니다. 자, 이제부터 알고리즘을 설계해봅시다. 1. 큐를 선언하여 입력되는 값을 큐에 넣습니다. 2. 우선 큐의 front 값에 대해서 처리해줍..

문제분석 굉장히 읽기 싫을 정도로 긴 문제지만 결국 소괄호가 한쌍으로 존재하는 가? 를 묻는 문제네요. ㅎㅎ 알고리즘 문제를 풀 때, 접근법이 굉장히 중요한 게 제가 처음에 이 문제를 접근하는 방법은 이렇습니다. '(' , ')' 두 개의 개수를 카운트해서 같으면 VPS 이다 ~ 라고 접근했습니다. 이 방법 역시 그렇게 어렵진 않지만 굉장히 단순 무식한 방법 같았습니다. 그래서 다른 분들의 코드를 보니 세상에 천재들이 많더군요. 개발자 지망생 김 모 씨의 접근법은 이렇습니다. 여는 괄호 '(' 가 나오면 무조건 스택에 PUSH 하고 닫는 괄호 ')' 가 나왔을 때, 배열 안에 여는 괄호 '(' 가 존재하면 스택에서 POP 하고 배열이 비어있다면 FALSE 하는 겁니다. 같은 문제를 이렇게 구현할 수 있다..