전체 글
[자료구조,개념] 그래프, 트리 (graph,tree)
그게 뭔데 컴덕아. Graph (그래프) 비트코인 차트그래프 이런거 아닙니다. 자료구조입니다. 어떤 Node(vertex 또는 정점)와 Node(vertex 또는 정점)의 관계를 나타내는 자료구조입니다. 구성: Vertex(정점),Edge(간선) 표현식: G(V,E) , G=(V,E) 간선이 방향성을 가지면, 방향성 그래프 / 무방향이면, 무방향 그래프 혹은 양방향 그래프 간선에 가중치가 있으면, 가중치 그래프. 순환(Cycle)이 하나라도 있다? => 순환 그래프. 순환이 하나도 없다 => 비순환(Acyclic) 그래프 DAG (Directed Acyclic Graph) => 방향성 비순환 그래프인데, VCS(version control System) ,블록체인, git의 브랜치 등 다양한 곳에 많이 ..
[백준/2346/파이썬] 풍선 터뜨리기
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 조건 1~N까지 N개의 풍선이 원형으로 놓여있다. i번 풍선 오른쪽에는 i+1,왼쪽에는 i-1. 단, 1번의 풍선의 왼쪽에는 N번 풍선. N번 풍선의 오른쪽에는 1번 풍선이 존재. 각 풍선에는 종이가 들어있고, 종이에는 -N≤n≤N 인 숫자 n이 존재함. 제일 처음에는 1번 풍선을 터뜨리고, 다음에는 풍선 안에 있는 종이를 꺼내어, 그 종이에 적혀있는 값 만큼 이동하여, 다음 풍..
[백준/1158/파이썬] 요세푸스 문제
https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 조건 1~N번까지 , N명의 사람이 원을 이루면서 앉아 있고, 정수 K가 주어짐. 순서대로 K번째 사람을 제거한다.(오징어 게임?!) 한 사람이 제거되면, 남은 사람들로 이루어진, 원을 따라 이 과정을 계속해 나간다. 요세푸스 순열은 ,이 제거된 사람을 순서대로 나열한 것이다 1
[백준/1021/파이썬] 회전하는 큐
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 조건 1번: 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. =⇒ a1에서 Pop이 일어남. 2번 : 왼쪽으로 한 칸 이동 시킨다. ⇒ 왼쪽으로 rotate, 맨 앞 element는 맨 뒤로 간다. 3번 : 오른쪽으로 한 칸 이동 시킨다 ⇒ 오른쪽으로 rotate, 맨 뒤 element는 맨 앞으로 간다. 큐의 크기 N, 뽑아 내려고 하는 수의 개수 M,뽑..
[Python,자료구조] Data structure
알고리즘을 풀기위해서, 최소한의 지식만 간단하게 담았습니다. 원래, 하나하나가 게시글 1개 분량으로 쓸 수 있습니다. 깊게 공부할 때, 구체화 시키겠습니다. -수정일. 2022.01.15 배열 (Array) arr=[] # 파이썬에서는 리스트로 배열을 구현함. 메모리 상에 연속된 공간으로 할당된다. 삽입(Insert), 삭제(Delete) : O(N) 탐색(Searching): O(1) 삽입,삭제가 O(N)인 이유 더보기 arr[3]이 삭제됬을 때, arr[4]는 앞 자리로 옴. (indx =4 ->3) 그럼, arr[0]이 삭제됬을 때는 , 뒤에 있는 친구들이 다 앞자리로 옮겨야 하므로, 삽입,삭제가 N임. 탐색이 빠른 이유 Random access가 가능하다. 간단하게 배열은 메모리 공간에 연속적이기..