일지 & 개발

이론 이번에 볼 자료구조는 깊이 우선 탐색(DFS)이다. 깊이 우선 탐색은 영어로 Depth First Search이고 줄어서 DFS라고 많이 부른다. 그래프 탐색 알고리즘 중 하나인데 그래프 말고도 트리에서도 적용이 된다. 반대로 넓이 우선 탐색(BFS)도 있는데 코드 테스트에서는 DFS 보다 BFS가 많이 나오지만 그래도 공부를 해야 되는 기본적인 알고리즘이다. DFS알고리즘을 알기위해서는 트리, 그래프, Stack 자료구조를 알아야 이해가 되는데 이 부분은 우선 공부한 뒤로 이 알고리즘을 공부하는 것을 추천한다. 안 그러면 이 뒤에 내용이 이해가 안 될수가 있기 때문이다. 자세한 설명은 아래의 사이트에 참조하면된다. https://namu.wiki/w/%EA%B9%8A%EC%9D%B4%20%EC%9..

문제 요약 알고리즘 분류: 분할정복, 재귀호출 난이도: Silver2 문제내용: 종이안에 정사각형 흰색 영역 개수와 파란색 영역을 구해라. 사이트: https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제풀이 이번에는 문제 유형은 완전탐색 방법에서 분할 정복으로 풀어야 될 문제이다. 어떻게 분할해서 풀면 된다. 나누는 방법은 간단하다. 문제에서는 주어진 가로세로 길이가 2^N이기 때문에 가로세로 각각 2로 나누어서 탐색 ..

문제 요약 알고리즘 분류: 동적계획법, dp 난이도: Silver1 문제내용: 스티커가 2 × n개가 있다. 하지만 하나 자르면 상하좌우 사용을 못한다. 사용할수 있는 스티커중 가중치 최대값을 구해라. 사이트: https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제풀이 이번 문제는 테스트 개수 T를 주고 길이가 최대 100,000이다. 브루드포스 같은 알고리즘으로 풀면 시간초과가 나서 가장 좋은 방법은 동적계획법으로 해결하는 방법이다...

이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알고리즘은 복잡하고 여러개의 연산이 있는데.. 작은 단위를 연산을 한다음 반복되거나 중복 되는 연산은 최소화 해서 풀어 나가는 알고리즘이다. 동적계획법은 시간 복잡도상에서 최적으로 나타낼수있는 강력한 알고리즘이지만 완벽한 알고리즘이라고 할수는 없다. dp로 해결하는 이유는 메모리 절약과 시간복잡도의 최적화로 되어 있지만 문제 푸는데는 어느정도 한계가 있고 이론보다는 접근 방법이나 아이디어가 더 많이 요구되기도 한다. 자세한 설명은 아래 사이트에서 찾아 보면된다. https://ko.wikipedia.or..

문제 요약 알고리즘 분류: 트리, 탐색 난이도: Silver2 문제내용: 루트가 1이라고 가정할때 2번 노드부터 N개까지의 부모노드를 출력해라. 사이트: https://www.acmicpc.net/problem/11725 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제풀이 이번 문제는 트리의 활용과 트리의 탐색에 대한 내용을 알고있으면 풀수있다고 생각한다. 트리에 대한 자세한 설명은 여기에서 확인 해보면 된다. 문제 접근 방법 일단 예제 1번을 그림 으로 대충 표현한다면 아래와 같다. 왼..

이론 이번에 볼 자료구조는 트리이다. 트리는 연결리스트(Linked List)에서 노드간의 부모와 자식을 갖는 자료 구조이다. 연결리스트는 앞과 뒤로 이루어 져 있는데 트리는 계층별로 상하 관계로 되어 있는 구조이다. 트리는 코딩테스트 뿐만 아니라 실무나 실생활에서도 많이 접하기 때문에 반드시 알아야 될 기본 자료구조이다. 자세한 설명은 밑에 사이트에 참조하면된다. https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84) 트리(그래프) - 나무위키 트리를 정의할 때에는 다양한 정의가 쓰이고, 다음은 모두 동치이다. GGG는 회로가 없는 연결 그래프이다.GGG는 회로가 없고, 단순 그래프의 형태를 유지하면서 간선을 추가할 경우 회로가 생긴다 ..

문제 요약 알고리즘 분류: 힙, 우선순위 큐, 자료구조 난이도: Silver2 문제내용: 선물N개와 아이들 M개가 있다. 아이들은 순서대로 선물 N개 선택할수 있고 이전에 선택된 선물을 또 선택가능하다. 아이들이 원하는 선물개수가 없는 경우 실망한다. 아이들이 실망 하지 않고 선물을 다 가져 갈수 있는지 확인해라.. 사이트: https://www.acmicpc.net/problem/23757 23757번: 아이들과 선물 상자 모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다. www.acmicpc.net 문제풀이 이번 각 10^5개 데이터라서 O(NM)으로 풀면시간이 초과가 된다. 그래서 O(MlogN)이 나오도록 처리를 해야 한다. 그러기..

문제 요약 알고리즘 분류: 백트래킹 난이도: Silver3 문제내용: N, M 가 주어 졌을때 1 ~ N수 에서 중복된 숫자가 없고 크기 순으로 출력하면 된다. 중복되는 수열은 여러번 출력하면 안된다. 사이트 주소: https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다. https://jih3508.tistory.com/84 [알고리즘 이론] ..