전체 글
-
[백준] 14494 다이나믹이 뭐예요? with PythonPS 2022. 7. 14. 23:07
📌 BOJ 14494 다이나믹이 뭐예요? 💡 조건 다이나믹 프로그래밍(동적 계획법), 다이나믹은 이름이 엄청 거창하지만 사실 이름에 비해 개념은 간단하다. 다이나믹의 기본 아이디어는 바로 이전에 계산한 값을 사용해서 (= 이미 계산된 값을 사용해서, 어려운 말로 메모이제이션.) 반복되는 똑같은 연산 횟수를 줄이는 것. 다차원 배열로도 가능하다. 오른쪽, 아래쪽으로만 움직일 수 있을 때, D[1][1]에서 D[x][y]까지 도달하는 경우의 수를 구하는 문제는 일일히 모든 경우를 다 계산할 필요 없이, D[i][j] = (i, j)에 도달하는 누적 경우의 수 = D[i-1][j] + D[i][j-1]를 세워서 해결할 수도 있다. →, ↓, ↘의 세 방향만 사용해서 한 번에 한 칸씩 이동할 때, 왼쪽 위 (1..
-
[백준] 3079 입국심사 with PythonPS 2022. 7. 14. 20:36
📌 BOJ 3079 입국심사 💡 조건 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. (1 ≤ Tk ≤ 109) 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 상근이와 친구들..
-
[백준] 2548 대표 자연수 with PythonPS 2022. 7. 12. 15:52
📌 BOJ 2548 대표 자연수 💡 조건 정보초등학교의 연아는 여러 개의 자연수가 주어졌을 때, 이를 대표할 수 있는 대표 자연수에 대하여 연구하였다. 그 결과 어떤 자연수가 다음과 같은 성질을 가지면 대표 자연수로 적당할 것이라고 판단하였다. “대표 자연수는 주어진 모든 자연수들에 대하여 그 차이를 계산하여 그 차이들 전체의 합을 최소로 하는 자연수이다.” 예를 들어 주어진 자연수들이 [4, 3, 2, 2, 9, 10]이라 하자. 이때 대표 자연수는 3 혹은 4가 된다. 왜냐하면 (4와 3의 차이) + (3과 3의 차이) + (2와 3의 차이) + (2와 3의 차이) + (9와 3의 차이) + (10과 3의 차이) = 16, (4와 4의 차이) + (3과 4의 차이) + (2와 4의 차이) + (2와 ..
-
[백준] 1939 중량제한 with PythonPS 2022. 7. 12. 15:12
📌 BOJ 1939 중량제한 💡 조건 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다. 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다. 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,..
-
이진트리의 순회자료구조 2022. 7. 12. 14:37
📌 이진트리의 순회 💡 이진트리순회(Binary Tree Traversal) 문제 정의 이진 트리의 모든 노드를 한번씩 방문한다. 트리에 있는 노드의 순서를 결정한다. 순회방법 중위순회(L-V-R) 전위순회(V-L-R) 후위순회(L-R-V) 💡 중위순회 void inorder(struct link *ptr){ if(ptr){ inorder(ptr -> left_child); printf("%d", ptr -> data); inorder(ptr -> right_child); } } 💡 전위순회 void preorder(struct link *ptr){ if(ptr){ printf("%d", ptr -> data); preorder(ptr -> left_child); preorder(ptr -> right_..
-
트리와 이진트리의 개념자료구조 2022. 7. 12. 14:21
📌 트리와 이진트리의 개념 💡 트리의 개념 트리란? 계층적 구조의 자료를 표현할 때 사용 ex) 가계도, 회사의 조직도, 폴더 구조 등 트리의 정의 하나 이상의 노드로 이루어진 유한 집합 Root(루트) 라고 하는 노드가 하나 존재한다. 나머지 노드들은 n(n >= 0) 개의 집합 T[1], ... ,T[n]으로 분할 이처럼 분할된 트리를 루트의 서브트리라고 한다. 💡 트리에 관련된 용어들 Level 1 : 노드의 차수(Degree), 트리의 차(Degree) Level 2 : 단일노드(Leaf node or Terminal node) Level 3 : 부모노드, 자식노드, 형제노드 Level 4 : 조상노드, 자손노드, level, 트리의 높이 or 깊이 💡 이진트리의 개념 이진트리(Binary Tre..
-
이중 연결 리스트자료구조 2022. 7. 12. 13:50
📌 이중 연결 리스트 💡 이중 연결 리스트의 개념 이중 연결 리스트(Double Linked List)란? 한 노드에 두 개의 Link 가 저장 이중 연결 리스트는 양방향으로 이동가능 단일 연결 리스트의 경우, 한 방향으로만 이동이 가능. struct node{ struct node *llink; // 이전 노드 포인트 int data; struct node *rlink; // 다음 노드 포인트💡 이중 연결 리스트의 종류 체인 처음 노드의 llink와 마지막 노드의 rlink는 NULL ptr = ptr -> llink -> rlink = ptr -> rlink -> llink 원형 이중 연결 리스트 원형 이중 연결리스트에 노드를 추가하는 방법 새로 추가되는 링크의 노드를 먼저 바꾸는 것이 좋다.void..
-
추가적인 리스트 연산자료구조 2022. 7. 12. 13:31
📌 추가적인 리스트 연산 💡 추가적인 리스트 연산들 단일 연결 리스트(Chain) 에 대한 연산 체인의 방향을 반대로 : invert() 두 개의 체인을 통합 : concatenate() 원형 리스트에 대한 연산 원형 연결리스트의 길이를 계산하는 연산 : length() 원형 연결리스트의 제일 앞에 새로운 노드 삽입 : insert_front() 💡 Invert 함수 포인터 3개를 사용해 가리키는 포인터를 변경해준다. lead, middle, tail 세 개의 포인터를 사용한다고 하면, return 값은 middle 이다. 💡 concatenate 함수 A 체인 혹은 B 체인이 NULL 일 경우, 나머지를 반환한다. A를 순회하면서 접근하고, A 마지막 노드의 포인터를 B로 가리켜준다. 💡 원형 연결리스..