Storage Gonie

개념을 적용한 문제풀이 # 이진트리의 프리오더, 인오더, 포스트오더 순서를 출력하는 문제 - https://www.acmicpc.net/problem/1991 - 코드상에서 3가지 방법의 차이는 출력을 언제 하는가의 차이이다. - 알파벳을 숫자화 해서 A : 0, B : 1, C : 2, ... i의 값으로 사용하고, 2차원 배열로 A[i][0] = 왼쪽 자식 값, A[i][1] = 오른쪽 자식 값을 저장하는 방식으로 트리를 저장하였음. 자식이 없는 경우 -1을 넣어주어 재귀호출이 끝나도록 하였음. * 이진트리의 순회는 왼쪽 자식과 오른쪽 자식의 값을 구분해 가지고 있는게 출력하기 편함. # 트리의 부모 찾기 - https://www.acmicpc.net/problem/11725 - DFS, BFS 두 ..

트리의 순회(Tree Traversal) - 트리도 그래프이기 때문에 DFS와 BFS 방식 모두 가능하다. - 그런데 트리에서만 가능한 아래의 3가지 방법이 있다.(각각의 차이는 루트 노드의 방문을 언제 하냐의 차이) - 이진트리에서는 아래의 3가지 방법이 모두 가능한데, 자식이 여러개인 트리에서는 '프리오더'와 '포스트오더'만 가능하다. 그 이유는 자식이 여러개인 트리의 경우, '인오더 방식'에서 출력이 어느 부분에 위치해야할지 가늠할 수 없기 때문이다. 프리오더 루트 L R 루트 children 인오더 L 루트 R 포스트오더 L R 루트 루트 children # Pre-order(전위순회) * 그래프의 DFS와 순서가 같음. 1) 루트노드 방문 2) 왼쪽 자식 노드를 루트로 하는 서브 트리를 프리오더..

트리의 개념 # 트리(Tree) - 자료구조의 일종으로 '사이클이 없는 그래프'를 Tree 라고 함(이 이유로 임의의 두 정점 사이의 경로는 오직 1개이다) 따라서, 정점의 개수는 V개이고, 간선의 개수는 V-1개 이다. - 트리는 임의의 두 정점 간의 경로가 오직 1개이기 때문에, BFS를 이용하여 찾아낸 그 경로가 바로 최단거리가 된다. - 주의할점이 있는데 (True) "Tree" 이면 "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다." (False) "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다." 이면 "Tree"이다. 그 이유는 아래와 같은경우 정점이 6개이고, 간선이 5개인데 사이클이 있어서 트리라고 볼 수 없는 반례가 존재하기 때문이다. (True) "정점의 개수는 V개, ..

플러드필 알고리즘 - 어떤 배열을 채우는 알고리즘이며, 어떤 위치와 연결된 모든 위치를 찾는 알고리즘이다. - dx, dy 가 사용됨. 유형1. 동시에 진행되는 탐색이 1개뿐인 것 # 단지에 번호를 붙이는 문제 - https://www.acmicpc.net/problem/2667 - 문제요약 : 정사각형 모양의 지도가 주어지는데, 0은 집이 없는 곳이고 1은 집이 있는 곳이다. 이 때 지도를 보고, 연결된 집의 모임 각각에 번호를 붙이려고 한다. 현재 위치를 기준으로 좌, 우, 아래, 위 중 한 곳이라도 집이 있다면 연결되었다고 할 수 있다. - 이 문제는 (x, y)형태로 값이 주어지지만, 이 값들을 그래프로 보면 연결요소의 개수를 구하는 것과 같다. BFS 혹은 DFS를 이용해서 탐색을 수행하는 것을..

연결요소(Connected Component) # 개념 - 연결요소란, '간선으로 연결된 정점들'이고, 이는 그래프를 구성하는 요소가 된다. - 아래의 경우 1개 혹은 2개의 그래프로 볼 수 있으며, 연결요소가 2개인 것은 변함이 없다. # 연결요소의 개수를 구하는 문제 - https://www.acmicpc.net/problem/11724 - 연결 요소의 개수를 구하는 것은 DFS나 BFS 탐색을 이용해서 구할 수 있다. 1) 정점을 차례대로 시작점으로 두고 DFS혹은 BFS를 진행하는데, check배열이 true로 방문한 상태이면 탐색을 진행하지 않는다. 2) DFS 혹은 BFS를 수행한 횟수를 세어주면 그것이 곧 연결요소의 개수가 된다. 이분 그래프(Bipartite Graph) # 개념 - 그래프..

그래프를 탐색하는 방법 - 그래프를 탐색하는 방법에는 DFS와 BFS가 있으며, 두 방식 모두 목적은 모든 정점을 1번씩 방문하기 위한 것이다. - 따라서, 두 방법 모두 각각의 노드에 방문 했는지 안했는지를 체크하는 check 배열이 필요하다. - 순서를 출력해 낼 때, 현재 정점의 위치만을 출력하며, 이것은 두 방식 모두 동일하다. # DFS(깊이 우선 탐색) 구현 : 스택 or 재귀호출 스택을 직접 컨트롤하는 경우, 재귀호출을 사용하지 않고 구현할 수 있고, 재귀호출을 사용하는 경우 중첩된 호출에 의해 스택을 간접적으로 사용하게 됨. 의미 : '최대한 깊숙히 많이 가는 방법'으로 모든 정점을 1번씩 방문하는 것 탐색방법 : 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고, 갈 수 없으면 이전 정..

그래프의 표현 정점 : {1, 2, 3, 4, 5, 6} 간선 : {(1, 2), (1, 5), (2, 5), (2, 3), (3, 4), (2, 4), (4, 5), (4, 6)} - '정점'이 V개 일 때 보통 정점에 1~V 혹은 0~V-1로 번호를 매기기 때문에 개수만 저장해둬도 된다. - '간선'은 무엇과 무엇을 연결하는지에 대한 중요한 관계를 나타내므로 간선을 저장하는 것이 그래프를 저장하는 것이 된다. - 그래서 보통 문제에서 그래프에 관해 입력데이터를 줄 때는 정점의 개수, 간선의 개수, 간선의 관계를 아래와 같이 준다. (양방향 그래프인지 단방향 그래프인지는 문제의 본문을 읽어야지만 알 수 있다) 예시 1) 가중치가 없는 경우 6 8 // n : 정점의 개수, m : 간선의 개수 1 2 /..

그래프의 개념 # 그래프(Graph) - 자료구조의 일종 - 그래프는 정점집합과 간선집합으로 만들어진다. G = (V, E) - 정점(Node, Vertex)은 말그대로 점을 의미하고, 간선(Edge)은 정점간의 관계를 나타낸다. - 예시1) 지하철노선이나 도로를 그래프로 나타낼 수 있음. - 예시2) 페이스북같은 경우는 사람이 정점이고 두 사람이 친구사이면 둘을 간선으로 연결해줄 수 있음 그래프에서 사용되는 용어 # 경로(Path) - 출발지와 도착지가 있고 그 사이를 연결하는 정점과 간선이 있으면 이것을 경로라고 한다. - 예시) A->C->D->E->B A->B A->C->B # 사이클(Cycle) - 경로 중에서 시작점과 도착점이 같은 경우를 사이클이라고 한다. - 예시) 'A'->C->B->'A..

정렬을 적용한 문제풀이 # 가장 빈도가 높은 수를 출력하는 문제 - https://www.acmicpc.net/problem/11652 - 방법1) 정렬한 뒤 하나씩 카운트하기, if (a[i-1] != a[i]) 으로 서로 다른 수의 경계값을 인식함. 시간복잡도 = 정렬(NlogN) + 카운트(N) 정렬된 수에서 경계값을 인식시켜줄 때는 a[i] a[i+1]을 비교하고, 제일 마지막 값은 경계값을 인식 못 하므로 꼭 따로 조건 추가해주기! - 방법2) C++ STL의 map을 이용하여 개수를 카운트 하고, 가장 등장빈도가 높으면서 작은 수 인 것을 출력. 시간복잡도 = 하나씩 카운트(N) + 비교(N이하) * count 메소드를 사용할 수 없는 이유는 시간복잡도가 N*N이 되어버리기 때문. # 오름차순..

정렬을 적용한 문제풀이 # N개의 수를 입력받아서 정렬하는 문제 - https://www.acmicpc.net/problem/2751 - 퀵 정렬 직접구현, 병합 정렬 직접구현, STL sort함수 사용 3가지 방법으로 풀이를 진행하였음 # (x, y) 좌표 정렬하기 문제 - https://www.acmicpc.net/problem/11650 - 아래의 여러가지 방법으로 정렬할 수 있음 1) pair, vector, sort 사용 2) struct, vector, sort ( , , 비교함수) 사용 3) struct, vector, sort( , , 람다함수) 4) struct, vector, sort, 연산자 오버로딩 # (x, y) 좌표 정렬하기2 문제 - https://www.acmicpc.net/..