MakerHyeon

● 인접행렬 - 구현이 빠르다. - 노드가 서로 연결되어 있는지 확인이 쉽다. - 특정 노드에 연결된 모든 노드를 검색할때,adj[i][1]~adj[i][v]를 전부 확인해야한다. - 전체 노드 탐색시 시간복잡도가 O(V^2) 이다. #include using namespace std; int N,M; int adj[10][10]; int main() { cin >> n >> m; for (int i=0;i> a >> b; adj[a][b] = 1; adj[b][a] = 1; } } ● 인접리스트 - 특정 노드에 연결된 노드 바로 검색 가능 - 노드가 서로 연결되어 있는지 확인이 오래걸린다.(특정노드가 검색노드 갖고있는지 리스트 탐색해야함) #include using namespace std; int n..

인접행렬 VS 인접 리스트 1.인접행렬 - edge 가 많은 그래프일 때 쓰는게 좋다.- edge 탐색이 빠르다. 2. 인접리스트 - edge 가 적은 그래프일 때 쓰는게 좋다.- 메모리를 적게 쓴다. 최단 거리를 구할 때는 BFS를 사용DFS는 재귀(or 스택),BFS는 큐로 구현가지치기를 하면 백트랙킹 인접행렬 frm sys import stdin node,edge = map(int,stdin.readline().split()) adj = [0 for _ in range(node) for _ in range(node)] for _ in range(edge): src, dest = map(int, stdin.readline().split()) adj[src][dest] = 1 adj[dest][src]..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 테이프를 최소로 쓰기 위해선 어떻게 해야할까? 바로 구멍난 곳들을 왼쪽 기준으로 차례로 붙여나가면 된다. SOLUTION CODE # PYTHON 1) 좌표로 풀기 N,L = map(int,input().split()) coord = [False] * 1001 for i in map(int,input().split()): coord[i]=True ans = 0 x = 0 while..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net SOLUTION CODE # PYTHON 1) Combination from itertools import combinations # arr=[] # for i in range(9): # arr.append(int(input())) heights = [int(input()) for _ in range(9)] for combi in combinations(heights,7): if sum(combi)==10..

◆ 순열 1) python from itertools import permutations v = [0,1,2,3] for i in permutations(v,4): print(i) 2) C++ #include #include #include using namespace std; int main() { vector v{0, 1, 2, 3}; do { for (int i : v) printf(" %d", i); printf("\n"); } while (next_permutation(v.begin(), v.end())); } ◆ 조합 1) python from itertools import combinations v=[0,1,2,3] for i in combinations(v,2): print(i)

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 해당문제는 파이썬의 경우 튜플과 최소힙/최대힙을 따로 두는 형식으로 풀 수있었으며 C++은 후자의 방식으로 풀었다. 파이썬 튜플의 경우 정렬시 맨앞의 값을 기준으로정렬해나가며,값이같다면 뒤의 값으로 정렬을 이어나간다. 헷갈리지말자.파이썬은 최소힙이 기본이며,C++은 최대힙을 기본으로 지원한다! SOLUTION CODE # PYTHON 1) 튜플 이용 import heapq a..

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 아주 쉽지만 자료구조의 중요성을 느낄 수 있었던 문제이다. 해당문제는 리스트를 이용하면 시간초과가 나온다. 1. 맨앞값 삭제 O(N) 2. 맨앞의 값을 맨뒤로 보내기 (삽입,삭제) O(N) X 2 이짓을 1이 남을때까지,즉 N-1번반복하면 N-1 X O(N) 총 복잡도는 O(N^2)이 된다. 따라서 해당문제는 시간복잡도 O(1)인 queue를 이용한다. SOLUTION CODE # PYTHON f..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 릿코드 문제와 똑같구만... SOLUTION CODE # PYTHON for _ in range(int(input())): stk = [] isVPS = True for ch in input(): if ch == '(': stk.append(ch) else: if stk: # 스택 비어있지않을때 stk.pop() else: # 스택 비어있으면 False isVps =..