https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 이 문제는 점근적 표기법에 대한 문제이다. 시간복잡도의 빅오 함수를 정의하는 것인데, 처음에는 너무 쉽다 생각해서 바로 구현하여 돌렸는데, 91퍼에서 틀려서 뭐가 문제인가 생각하게 만든 문제이다. 이유는 생각보다 간단했다. 내가 생각한 로직은 g(n0)>=f(n0)이 성립하면 된다고 생각했다. 하지만 여기서 생각할 것은 f(n)=fn && a1
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제는 너무 어려웠다.. 그래서 결국 해설을 봤다.. 처음에 내가 구현한 방법은 단순히 모든 DFS를 다 돌아서 사이클을 찾아내는 방식으로 했다. 그래서 시간초과가 났다. 그래서 시간초과를 해결하기 위해서는 사이클이 있는 경우 사이클을 이루는 갯수를 세고, 이 과정에서 사용한 노드는 더 이상방문할 필요없는 노드로 처리하여 중복적으로 탐색하는 것을 막아야 했다. 예를 들어 2->1->3->3과 1->..
https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 이번 문제는 순열 사이클의 갯수를 찾는 문제였다. 그런데 이 문제는 11724번과 로직이 똑같았다. BFS로 탐색을 진행하면서 탐색이 끝날때마다 카운트를 세면 되는 로직이었다. 가장 기본적인 BFS라고 생각할 수 있다. 그래서 오늘은 BFS에 대해서 간단하게 정리해보려고 한다. BFS란 한국말로 너비우선탐색이다. 너비를 우선..
https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 오늘 풀은 문제는 간단한 BFS문제였다. 풀었던 문제들과 같은 유형이여서 1트만에 풀어냈다. 단지번호 붙이기 문제와도 비슷하다. BFS로직은 같고 인접리스트를 상하좌우, 대각선으로 해서 탐색을 진행하면 된다. 전체 테이블을 탐색하면서 섬이 있으면 섬의 면적 전체를 방문처리한다. 그리고 다음 섬을 탐색하는 식으로 전체 테이블을 탐색한다. 섬의 수를 세는 로직은 아래와 같다. for(int i=..
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이 문제는 이분탐색 문제인데 lowerbound와 upperbound의 개념을 알아야 풀 수 있는 문제였다.. 그래서 애를 많이 먹었다. 나는 lowerbound와 upperbound를 말로는 이해하지 못했다.. 그림으로 이해했다. 먼저, lowerbound는 배열에서 범위 내의 원소들 중 찾으려는 값(key)보다 크거나 같은(key
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 오늘 풀은 문제는 덱큐 문제인데, 좀 시간이 걸렸다. 이 문제에서 주의 할 것은 값을 빼는 것은 무조건 첫번째 인덱스라는 것이다. 나는 첫번째와 마지막에서 둘다 뺄 수 있는 줄 알고 로직을 짰다가 고생을 했다.. 동작 방식은 간단하다. 주어진 뽑으려는 위치에 있는 값을 저장하고, 앞과 뒤중에 그 값에 더 가까운 곳에서 시작해서 뽑은 값을 옮기면 된다. 뽑으려는 값의 인덱스 위치를 찾고, 전체 ..
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 오늘 풀은 문제는 이진 트리 검색이다. 저번에 풀은 트리 순회 문제와 순회 방식은 같지만 입력 받는 값들이 전위 순회로 출련된 값들이 주어진다. 그래서 트리를 클래스형으로 구성할 때 조건문을 신경써야 한다. 또한 이 문제는 입력받는 노드의 수가 정해져있지 않아서 입력값이 null인지를 확인하여 반복을 멈추어야한다. 그래서 이 문제는 입력에 주의하여 이진 트리를 생성하는 것이 관건이다...
https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 오늘은 트리의 기초인 트리순회 3가지에 대해 공부해보고 문제를 풀었다. 처음에는 1차원 배열로 시도하려고 했지만 어떤식으로 배열을 처리해야할지 감이 잡히지 않아서 클래스를 이용한 순회로 변경하였다.. 이 문제를 풀기위해 알아야 할 것은 전위순회, 중위순회, 후위순회인데 전,중,후를 나누는 기준은 부모노드를 어디에 두느냐이다. 말 그대로 순회를 할때 부모노드를 제일먼저 탐색하고 왼쪽자식,..
