군만두의 IT 공부 일지

✅문제: 2293번📌문제풀이주어진 동전들로 특정 금액을 만드는 경우의 수를 구하는 문제임. 각 동전은 무한히 사용할 수 있으며, 동전의 종류와 목표 금액이 주어짐.DP 테이블 초기화dp[x]: 금액 x를 만드는 경우의 수를 저장하는 배열dp[0] = 1: 금액 0을 만드는 방법은 아무 동전도 사용하지 않는 1가지 경우뿐임.동전 업데이트각 동전에 대해 해당 동전을 포함하여 만들 수 있는 금액을 계산함.현재 금액 x에서 dp[x] += dp[x−coin] 으로 이전 값에 추가함.즉, 동전 coin을 사용해 금액 x를 만드는 경우의 수를 누적함.결과 출력DP 테이블에서 dp[k] 값을 출력하여 금액 k를 만드는 경우의 수를 반환함.import sysinput = sys.stdin.readdef solutio..

✅문제: 1181번📌문제풀이주어진 단어들을 정렬하여 출력하는 문제임. 단어를 길이순으로 먼저 정렬하고, 길이가 같으면 사전순으로 정렬하며, 중복된 단어는 한 번만 출력해야 함.입력 데이터를 리스트로 저장입력으로 주어진 단어들을 리스트로 읽어옴.동일한 단어가 여러 번 입력될 수 있으므로 중복을 제거해야 함.중복 제거set()을 사용하여 중복된 단어를 제거한 뒤, 리스트로 변환함.이를 통해 각 단어를 한 번씩만 처리할 수 있음.정렬 기준 적용sort() 함수의 key를 사용하여 두 가지 정렬 기준을 설정함.단어의 길이순 정렬길이가 같은 경우 사전순 정렬import sysinput = sys.stdin.readdef solution(words): unique_words = list(set(words))..

✅문제: 1263번📌개념정리(1) 그리디 알고리즘 (Greedy Algorithm)정의: 문제를 해결하는 데 있어 매 순간 최적의 선택을 함으로써 전체 문제의 최적해를 도출하는 알고리즘작업들의 마감 시간을 기준으로 정렬한 뒤, 가장 늦게 시작할 수 있는 시간부터 계산하여 모든 작업을 수행할 수 있는지 확인하는 방식으로 해결할 수 있음.(2) 정렬정의: 데이터를 특정 기준에 따라 재배열하는 작업작업을 마감 시간 기준으로 정렬하여, 가장 늦게 마감해야 하는 작업부터 역순으로 스케줄링할 수 있음.📌문제풀이주어진 작업의 소요 시간과 마감 시간을 기반으로 모든 작업을 수행할 수 있는 가장 늦은 시작 시간을 계산하는 문제임. 각 작업은 소요 시간과 마감 시간이 주어지며, 모든 작업을 마감 시간 내에 끝낼 수 있..

목차9.2 기본 데이터 처리9.2.4 GROUP BY 처리GROUP BY 또한 ORDER BY와 같이 쿼리가 스트리밍된 처리를 할 수 없게 하는 처리 중 하나임.GROUP BY 절이 있는 쿼리에서는 HAVING 절을 사용할 수 있는데, HAVING 절은 GROUP BY 결과에 대해 필터링 역할을 수행함.GROUP BY 작업은 인덱스를 사용하는 경우와 그렇지 못한 경우로 나뉨.인덱스를 사용할 때인덱스를 차례대로 읽는 인덱스 스캔 방법인덱스를 건너뛰면서 읽는 루스 인덱스 스캔 방법인덱스를 사용하지 못할 때임시 테이블 사용9.2.4.1 인덱스 스캔을 이용하는 GROUP BY(타이트 인덱스 스캔)조인의 드라이빙 테이블에 속한 칼럼만 이용해 그루핑할 때, GROUP BY 칼럼으로 이미 인덱스가 있다면 그 인덱스를..

✅문제: 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가 아닌 성적은 평균 계산에 포함되며, 해당 과목의 가중치를 총 ..

1. 연결 리스트에서 값을 찾는데 시간 복잡도가 얼마나 걸리는가? 더 개선된 구조가 있는지? 단점은?연결 리스트에서 값을 찾는 시간 복잡도는 O(n)입니다. 이는 리스트를 처음부터 순회해야 하기 때문입니다.개선된 구조로는 해시 테이블을 사용할 수 있으며, 평균적으로 O(1)의 시간 복잡도로 값을 찾을 수 있습니다.그러나 해시 테이블은 메모리 사용량이 많고 해시 충돌 문제가 발생할 수 있다는 단점이 있습니다. 또한, 이중 연결 리스트나 트리를 사용하여 검색 성능을 개선할 수 있지만, 이 경우 구현의 복잡성이 증가합니다.O(n)의 시간 복잡도가 걸립니다. 뒤쪽 원소도 빠르게 검색할 수 있는 Doubly Linked List 구조도 있으며, 이는 저장 공간이 더 필요하다는 단점이 있습니다. 그 외에 Circu..