군만두의 IT 공부 일지

✅문제: 1269번📌개념정리(1) 대칭 차 (Symmetric Difference) 정의: 두 집합 A와 B의 대칭 차는 A∪B에서 A∩B를 뺀 부분A와 B 중 하나에만 포함된 원소들로 이루어진 집합A△B=(A−B)∪(B−A)두 집합에서 공통되지 않는 요소들의 개수를 구할 때 사용됨.📌문제풀이주어진 두 리스트 A와 B에 대해 각 리스트를 집합으로 변환하고, 대칭 차 연산을 수행하여 대칭 차 집합의 크기를 계산하는 문제임. 1. 주어진 두 리스트 A와 B를 각각 집합으로 변환2. set.symmetric_difference() 또는 ^ 연산자를 사용해 두 집합의 대칭 차 계산3. 대칭 차 집합의 크기를 len() 함수로 계산 import sysinput = sys.stdin.readdef differe..

✅문제: 14888번📌개념정리(1) 재귀 호출정의: 함수가 자기 자신을 호출하는 프로그래밍 기법문제를 작은 부분으로 나누어 반복적으로 해결할 수 있음.이 문제에서는 모든 연산자의 가능한 조합을 확인하기 위해 재귀 호출을 통해 각 연산자를 하나씩 적용하여 결과를 탐색함.(2) 백트래킹정의: 해를 찾는 도중에 막히면 이전 단계로 돌아가 다른 경로를 시도하는 기법가능한 모든 경우의 수를 탐색할 때 자주 사용됨.연산자를 사용할 때마다 해당 연산자를 감소시키고, 재귀 호출이 끝나면 다시 원래 개수로 복구하여 다른 경로를 탐색함.📌문제풀이주어진 숫자와 연산자(+ - * /)를 사용해 가능한 모든 결과를 계산한 뒤, 그중 최대값과 최소값을 구하는 문제임.제약사항각 연산자는 주어진 개수만큼 사용할 수 있음.나눗셈 ..

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

✅문제: 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) 원칙으로 탐색을 진행함.이 알고리즘은 연구소 문제에서 바이러스의 확산을 모델링하는 데 사용됨.📌문제풀이연구소 내에서 바..

✅문제: 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 모듈을 사용하여 이진 탐색을 간편하게 구현할 수 있음. 이 모듈은 정렬된 배열에서 요소를 삽입할 위치를 찾거나, 특정 요소의 인덱스를 찾는 함수를 제..