본문 바로가기

분류 전체보기75

Abstract Data Type (ADT) Abstract Data Type Structures/Funtions C++이나 Java의 Class와 같은 것 알고리즘을 디자인하고 정확도를 개선 Tree Root: 부모노드가 없는 노드 Degree: 자식노드의 수 External node(leaf): 자식노드가 없는 노드 Internal node: 자식노드가 있는 노드 Ancestor of a node x: 루트까지의 simple path의 노드들 (x 포함, proper ancestor: 자기 자신 제외) Descendant: ancestor의 반대 개념. 자신 아래에 있는 모든 노드들. Subtree rooted at a node x: x의 descendant들을 모은 트리. 루트는 x Depth: 0부터 시작하여 자식으로 내려갈수록 1씩 증가 .. 2021. 3. 26.
백준 7562 나이트의 이동 www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 쉬운 문제였는데 테스트 케이스 중간에 멈추길래 뭔가 했는데 그래프를 초기화하지 않아서 그랬던 것이었음.. 테스트케이스 여러번 돌릴 땐 초기화를 잘 하자 #include #include using namespace std; int l, ax, ay, bx, by, sum; int graph[300][300]; // 나이트의 이동 가능 범위 int dx[8] = { 1, 1, 2, 2, -1, -1, -2, -2 }.. 2021. 3. 26.
백준 1012 유기농 배추 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net dfs로 풀었다. 배열을 순차적으로 훑으면서 아직 방문하지 않았으면 dfs로 그래프 내의 모든 노드를 방문하고 '방문함'체크. 방문이 가능한 (그래프의) 수를 세면 된다. 그런데 테스트케이스는 다 맞았지만 제출해보니 틀렸다고 뜸 dfs 재귀 들어가기 전에 범위체크를 안 해서 그런 것이었다. 범위체크 잊지 말고 잘 하자.. #include using namespace std; int t, m, n, k, x, y; bool .. 2021. 3. 24.
백준 1697 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 이용해서 풀었는데 자꾸 틀렸습니다가 뜸 시작점(N)에 다시 방문하지 않게 하기 위해 visited[N]을 1로 넣고 시작했더니 [1 1] 같은 케이스에서 0이 아닌 2가 출력된 것이었음. bfs 앞부분에 같으면 0 출력하고 종료하는 코드를 넣으니까 풀렸다. visited랑 몇번째 방문인지 체크하는 배열을 따로 선언해야 하나 고민중 사실 visited가 0이 아니면 무조건 방문.. 2021. 3. 24.
Array search알고리즘의 Optimality n개 원소를 갖는 배열 E와 정수 K가 주어진다. K=E[index]인 인덱스를 찾고, 없으면 -1을 리턴하라. 1. A: unsorted Array일 때, 순차적 탐색 W(n) = n (Worst case) A(n) = q[(n+1)/2]+(1-q)n (Average case. q:탐색에 성공할 확률) unsorted일 때 F(n)=n 이므로 알고리즘 A는 optimal 2. B: 오름차순 정렬된 배열일 때, 순차적 탐색 W(n) = n A(n) = q[(n+1)/2]+(1-q)n 배열이 정렬되었다는 정보를 이용하지 않음. optimal X 3. C: 오름차순 정렬된 배열일 때, 순차적 탐색하다가 K보다 큰 원소를 만나면 -1 리턴 (찾는 원소가 없다) W(n) = n+1 => n Asucc(n) = .. 2021. 3. 24.
Classifying Functions - Big oh, theta, omega Classifying Functions 점근 증가율, 점근 순서. 상수나 small input은 무시하고 비교한다. Ω(g): big omega. lower bound. 최소 g만큼 빠르게 증가하는 함수 ex) Ω(n)이면 n+10, n^3+3 모두 해당됨 Ω(g): big oh. upper bound. g보다 증가율이 빠르지 않은 함수 ex) Ω(n^2)이면 n^2+7, 3n+10 모두 해당됨 Θ(g): big theta. g와 같은 비율로 증가하는 함수. Ω(g)∩Ω(g) Little oh, little omega: big oh, big omega에서 증가율이 같은 경우는 제외한 것 Big oh, theta, omega의 특성 1. Transitive(전이성): f∈O(g)이고 g∈O(h)면 f∈O(.. 2021. 3. 24.

티스토리툴바