군만두의 IT 공부 일지

✅문제: 17218번 📌개념정리(1) 동적 프로그래밍(Dynamic Programming)정의: 복잡한 문제를 간단한 하위 문제로 나누어 해결하고, 이를 통해 중복 계산을 최소화하는 방법서브문제의 결과를 저장하고 재사용함으로써 계산 시간을 효율적으로 단축함.(2) 최장 공통 부분 수열(Longest Common Subsequence, LCS)정의: 두 시퀀스에서 순서를 유지하면서 둘 모두의 부분 수열이 되는 가장 긴 수열을 찾는 문제LCS는 문자열 비교, 데이터 동기화, 생물학적 서열 분석 등 다양한 분야에서 활용됨.📌문제풀이두 문자열 사이의 최장 공통 부분 수열을 구하는 문제임. 각 문자열을 순차적으로 비교하면서 공통 문자를 발견할 때마다 결과 문자열에 추가함.1. 두 문자열의 길이에 대한 2차원 ..

✅문제: 1717번 1717번: 집합의 표현초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작www.acmicpc.net📌개념정리(1) 분리 집합(Disjoint Set)정의: 상호 배타적인 부분 집합들로 나누어진 전체 집합을 효율적으로 표현하고 처리하기 위한 자료구조주요 연산find: 특정 원소가 속한 집합을 찾는 연산union: 두 원소가 속한 집합을 하나로 합치는 연산구현 방법경로 압축(Path Compression): find 함수를 재귀적으로 호출한 뒤, 찾은 루트 노드가 바로 부모 노드가 되도록 함.합병(by ran..

✅문제: 1068번 1068번: 트리첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다www.acmicpc.net📌개념정리(1) 트리(Tree)정의: 계층적 관계를 표현하는 비선형 자료구조하나의 루트 노드와 여러 자식 노드들로 구성되며, 노드 간에는 부모-자식 관계가 존재함.트리 구조는 노드와 노드를 연결하는 에지(edge)로 구성되며, 사이클이 존재하지 않음.파이썬에서 트리 사용각 노드의 자식 정보를 저장하기 위해 리스트를 사용할 수 있음.리스트의 각 요소는 해당 인덱스 노드의 자식 노드 인덱스를 저장하는 또 다른 ..

✅문제: 14502번 14502번: 연구소인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크www.acmicpc.net📌개념정리(1) 너비 우선 탐색(BFS, Breadth-First Search)정의: 그래프의 각 노드를 가까운 노드부터 탐색하는 알고리즘으로, 레벨 별로 탐색을 진행함.파이썬에서는 collections 모듈의 deque를 사용하여 큐 연산을 수행하고, 이를 통해 FIFO(First In First Out) 원칙으로 탐색을 진행함.이 알고리즘은 연구소 문제에서 바이러스의 확산을 모델링하는 데 사용됨.📌문제풀이연구소 내에서 바..

✅문제: 25206번 25206번: 너의 평점은인하대학교 컴퓨터공학과를 졸업하기 위해서는, 전공평점이 3.3 이상이거나 졸업고사를 통과해야 한다. 그런데 아뿔싸, 치훈이는 깜빡하고 졸업고사를 응시하지 않았다는 사실을 깨달았다! 치www.acmicpc.net 📌개념정리(1) 리스트 인덱싱정의: 파이썬에서 연속적인 데이터를 저장하는 자료구조특정 요소를 찾을 때, 인덱싱을 통해 각 요소에 접근할 수 있음.📌문제풀이주어진 과목들의 학점을 기반으로 평균 학점을 계산하는 문제임. 과목 이름, 학점 단위, 그리고 성적이 입력값으로 주어지며, P는 Pass/Fail 과목으로 평균 계산에서 제외됨.1. 각 과목의 학점 단위와 성적을 분리하여 처리2. P가 아닌 성적은 평균 계산에 ..

✅문제: 7795번 7795번: 먹을 것인가 먹힐 것인가심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을www.acmicpc.net📌개념정리(1) 이진 탐색(Binary Search)정의: 정렬된 배열에서 특정한 값을 효율적으로 찾는 탐색 기법탐색 범위를 반으로 줄이면서 값을 찾기 때문에 O(log N)의 시간 복잡도를 가짐.파이썬에서는 bisect 모듈을 사용하여 이진 탐색을 간편하게 구현할 수 있음. 이 모듈은 정렬된 배열에서 요소를 삽입할 위치를 찾거나, 특정 요소의 인덱스를 찾는 함수를 제..

✅문제: 2230번 2230번: 수 고르기N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어www.acmicpc.net📌개념정리(1) 투 포인터(Two Pointers)정의: 서로 다른 두 위치의 포인터를 동시에 조작하여 해결하는 알고리즘주로 정렬된 배열에서 두 요소의 특정 관계를 만족시키는 문제에 사용함.📌문제풀이주어진 배열에서 두 수의 차가 M 이상이면서 가장 작은 경우를 찾는 문제임. 배열을 정렬한 후, 투 포인터 기법을 사용하여 두 수의 차이를 조절하며 최소 차이를 구함.1. 주어진 수를 오름차순으로 ..

✅문제: 1316번 1316번: 그룹 단어 체커그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때www.acmicpc.net📌개념정리(1) 집합(Set)정의: 중복을 허용하지 않는 순서가 없는 자료구조파이썬에서는 집합 자료형(set)을 이용하여 요소의 중복을 자연스럽게 제거할 수 있음.파이썬에서 집합 사용요소 추가: add() 메소드를 사용하여 집합에 요소를 추가함.요소 확인: in 연산자를 사용하여 요소가 집합에 있는지 확인할 수 있음.요소 삭제: remove() 메소드를 사용하여 집합에서 요소를 제..