이우의 개발일지

백준 1541번 잃어버린 괄호   사실 그리디는 말그대로 욕심쟁이 알고리즘이라고, 매번 선택에 있어서 가장 최적의 답을 고르는 알고리즘입니다. 우리가 최적이라고 아니깐 이걸 쓰는거지 만약에 예외 테스트가 존재할 시 망할 수도 있는 것이죠. 그래서, 점화식을 잘 세우고 접근을 해야합니다.  이 문제를 봤을 때 괄호를 쳐서 최소의 숫자를 도출해내는 것이 요구 결과입니다.어떻게해야 최소가 된다고 하는지 유심히 봤을 때 뒤에 - 마이너스가 나오는 순간부터 다 빼주면 최소가 나오는 결과에 도달 할 수 있습니다.  또 다른 문제 조건은 string으로 한번에 받아서 문자를 숫자로 처리해야한다는 것인데요. 그래서 이부분에서는 STL 함수인 stoi 함수를 썼습니다. 이 함수는 string을 int형으로 바꿔주는 함수..

백준 15650번  N과 M(2) 풀이 N과 M (2) 설명백트래킹은 완전 탐색과 비슷하게 하나하나 다 경우를 따져보는 알고리즘이다.일반적으로 다 따져보기 때문에 경우의 수가 큰 문제는 적용할 수 없다. 보통 재귀함수를 섞어서 쓰기 때문에 선행적으로 재귀에 대한 이해가 필요하다.  이 문제에서 볼 때 조건은 아래와 같이 2가지이다.조건 1. N개의 자연수를 M 개씩 나열한다.조건 2. 오름차순으로 나열한다. 조건 1을 따져보면 n개와 m개를 입력받고 재귀함수 안에서 m개의 조건을 충족하면 출력한다.bool issu[9];int list[9];int num = 0;int n, m;void func(int a) { if (num == m) { for (int i = 1; i i) continue; el..

백준 1260번 BFS와 DFS BFS와 DFS 풀이이 문제는 생각보다 까다로울 수 있는데, 일반적인 BFS와 DFS 구현에서 추가로 조건이 다음과 같이 붙는다. 조건 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다.조건 2. DFS와 BFS 동시에 구현하기 조건 3. 들어간 순서대로 출력하기 BFSvoid Bfs(int start) { Q.push(start); vis_b[start] = 1; cout  먼저, BFS를 보면 일반적인 구현방식과 동일한데 중간에 sort 함수가 보일 것이다. 간선의 개수가 최대 10,000개까지 가능해서 처음에 이중 for문을 시도했다가 시간초과가 뜨는 쓴 맛을 봤다... ㅋㅋ 이중 for문에 시간복잡도는 O(n^2) 이고 내가 현재..