본문 바로가기

전체 글76

BOJ 1629 곱셈 문제링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 요약 (A^B)%C를 구하는 문제 풀이 주어지는 세 수의 최댓값이 2,147,483,647이다. 지수값이 저렇게 큰수면 곱하다가 시간초과 나버린다. 시간복잡도를 줄이기 위해서 분할정복으로 해결하여야 한다. 지수 B가 짝수인 경우에는 A^B=(A^(B/2))^2 이고 홀수인 경우엔 A^B = A*(A^((B-1)/2))^2이다. 이렇게 연산을 logB개로 줄일수 있게 되고 시간복잡도도 즉 O(logB)가 된다. 숫자가 매우 크기 때문에 long lon.. 2022. 3. 12.
너비 우선 탐색(bfs) bfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32를 참고 하자. 너비 우선 탐색(bfs) BFS(Breadth First Search) 이름 뜻 그대로 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다. 장점 너비를 우선으로 탐색하기 때문에 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장 최단 경로가 존재한다면, 어느 한 경로가 무한히 깊어진다 해도 최단 경로를 반드시 찾을 수 있다. 노드 수가 적고 깊이가 얕은 해가 존재할 때 유리하다. 단점 재귀 호출을 사용하는 DFS와 달리 큐를 이용해 다음에 탐색할 노드들을.. 2022. 3. 11.
깊이 우선 탐색(dfs) dfs 대해 알아보기 전에 그래프에 대한 기초가 필요하다. https://hongcode.tistory.com/32https://hongcode.tistory.com/32를 참고 하자. 깊이 우선 탐색(dfs) DFS(Depth First Search) 이름 뜻 그대로 루트 노드나 임의의 노드에서 시작하여 최대로 진입할 수 있는 깊이까지 탐색하고 다시 돌아와 다른 노드로 같은 방식으로 탐색하는 방법을 말한다. 장점 최선의 경우, 가장 빠른 알고리즘이다. 운이 좋게 항상 해에 도달하는 올바를 경로를 선택하다면, dfs가 최소 실행시간에 해를 찾는다. bfs에 비해 저장공간의 필요성이 적다. 백트레킹을 해야 하는 노드들만 저장해주면 된다. 단점 찾은 해가 최적이 아닐 가능성이 있다.(알고리즘은 항상 최악의경.. 2022. 3. 11.
그래프(Graph) 현실 세계의 사물이나 추상적인 개념 간의 연결관계를 표현한 것 일반적이고 강력한 자료구조 정점(Node or Vertex)과 간선(Edge or Branch)으로 구성 G=(V, E)로 표현 가능 , V: 정점 집합 / E: 간선 집합 주요 용어 정리 경로 Path 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것 단순 경로: 경로 중 한 정점을 최대 한 번만 지나는 경로 의미(일반적) ex) A --> E로 가는 경로 A --> B --> E A --> B --> C --> E A --> B --> D --> E 사이클 cycle 시작한 점에서 끝나는 경로 a.k.a. ‘회로’ 단순 사이클: 같은 정점을 두 번 이상 방문하지 않는 사이클 (일반적 / 시작점 제외) ex) 단순 사이클 A --> B -.. 2022. 3. 11.
벡터(Vector) Vector는 동적 배열 구조를 구현한 것으로 맨 끝에서만 삽입 삭제가 일어나는 구조이다. 동적으로 크기가 변하고 메모리가 연속적이기 때문에 자동으로 배열의 크기를 조절할 수 있고 유연하게 객체의 추가 및 삭제가 가능하다는 일반 배열과의 차이점을 보여준다. 어떻게 사용하는가? #include // vector를 포함하고 있는 헤더파일 vectorv; // vector의 크기를 정하지 않았을 경우 선언법(다른 자료형도 가능) vectorv(10); // vector의 크기를 정한 경우 선언법 ex)크기 10 vectorv(10,1); // 크기를 10으로 정하고 데이터를 전부 1로 초기화하는 경우 선언법 v[idx]; // 벡터 v의 idx번째의 원소를 참조한다. v.front(); // 벡터 v의 첫번째.. 2022. 3. 11.
덱(Deque) 디큐 혹은 덱이라고 부르며 쉽게 설명하면 스택(Stack) + 큐(Queue)인 구조라고 생각하면 된다. 스택 + 큐 구조 (엄밀히 말하면 아님) 앞과 뒤 2방향에서 원소를 삽입하거나 삭제할수 있다. 여러 메모리 블록에 나뉘어 저장된다. 어떻게 사용하는가? #include // dequeue가 포함된 헤더파일 deque dq; // int형 덱 선언, 다른 자료형을 넣어도 됨 dq.push_front(x); // 덱에 데이터 x를 앞에서 입력한다. dq.pop_front(); // 덱의 데이터를 앞에서 삭제한다. dq.push_back(x); // 덱에 데이터 x를 뒤에서 입력한다. dq.pop_back(); // 덱의 데이터를 뒤에서 삭제한다. dq.size(); // 덱의 크기를 반환한다. dq.em.. 2022. 3. 11.

티스토리툴바