군만두의 IT 공부 일지

✅문제: 1991번📌문제풀이이 문제는 주어진 이진 트리를 전위 순회(Preorder), 중위 순회(Inorder), 후위 순회(Postorder) 방식으로 탐색한 결과를 출력하는 문제임. 각 순회 방식의 차이를 이해하고, 이를 구현하는 연습을 할 수 있음.트리 구성입력으로 주어진 노드 정보(루트, 왼쪽 자식, 오른쪽 자식)를 바탕으로 트리를 생성.각 노드를 Node 객체로 표현하며, 딕셔너리 tree를 사용해 트리 구조를 저장.순회 방식 구현전위 순회 (Preorder):순서: 루트 → 왼쪽 자식 → 오른쪽 자식.루트를 먼저 방문하고, 왼쪽과 오른쪽 자식을 재귀적으로 방문.중위 순회 (Inorder):순서: 왼쪽 자식 → 루트 → 오른쪽 자식.왼쪽 자식을 먼저 방문한 후, 루트를 방문하고 오른쪽 자식을..

✅문제: 11057번📌문제풀이0부터 9까지의 숫자로 이루어진 오르막 수의 개수를 계산하는 문제임. 오르막 수는 각 자릿수가 이전 자릿수 이상인 수를 의미하며, n자리 오르막 수의 개수를 동적 계획법(DP)을 사용하여 계산함.DP 배열 초기화dp[i][j]: i자리 오르막 수 중 마지막 숫자가 j인 경우의 수를 저장하는 배열.초기값: dp[1][j] = 1: 한 자리 수는 0부터 9까지 각각 1개임.점화식dp[i][j]: i자리 오르막 수에서 마지막 자릿수가 j인 경우를 구하기 위해, 이전 자릿수에서 0부터 j까지의 값을 더함.dp[i][j] = dp[i−1][0] + dp[i−1][1] + ⋯ + dp[i−1][j]결과 계산모든 계산은 10007로 나눈 나머지를 저장함.n자리 오르막 수의 총 개수는 d..

✅문제: 9095번📌문제풀이1, 2, 3의 합으로 숫자 n을 표현하는 방법의 수를 계산하는 문제임. n은 최대 10까지 주어지며, 이를 동적 계획법(DP)을 사용해 해결함.DP 배열 초기화dp[i]: 숫자 i를 1, 2, 3의 합으로 나타내는 방법의 수를 저장하는 배열초기값 설정dp[1] = 1dp[1]: 1을 표현하는 방법은 1개 (1)dp[2] = 2dp[2]: 2를 표현하는 방법은 2개 (1+1, 2)dp[3] = 4: 3을 표현하는 방법은 4개 (1+1+1, 1+2, 2+1, 3)점화식숫자 i를 1, 2, 3의 합으로 표현하기 위해 고려해야 할 사항마지막 숫자 1: dp[i−1]마지막 숫자 2: dp[i−2]마지막 숫자 3: dp[i−3]따라서, dp[i]=dp[i−1]+dp[i−2]+dp[i−..

✅문제: 17952번📌문제풀이주어진 시간 동안 처리해야 하는 과제들에서 점수를 계산하는 문제임. 각 과제는 점수와 소요 시간이 주어지며, 시간당 한 과제를 처리하며 점수를 얻음.스택 구현각 과제는 (점수, 남은 시간) 형태로 스택에 저장함.새로운 과제가 주어지면 스택에 추가하며, 현재 처리 중인 과제를 1분씩 진행함.시간 감소 및 과제 완료 처리스택의 마지막 과제(현재 진행 중인 과제)의 남은 시간을 1분씩 감소시킴.남은 시간이 0이 되면 과제를 완료하고 해당 점수를 total_score에 추가함.최종 점수 출력주어진 모든 시간 동안 처리 가능한 과제를 완료하며 점수를 계산함.최종적으로 얻은 총 점수를 출력함.import sysinput = sys.stdin.readlinetasks = []total_..

목차 10.3 실행 계획 분석MySQL 8.0 버전부터는 EXPLAIN 명령의 결과로 출력되는 실행 계획의 포맷을 기존 테이블 포맷과 JSON, TREE 형태로 선택할 수 있음.실행 계획의 출력 포맷보다는 실행 계획이 어떤 접근 방법을 사용해서 어떤 최적화를 수행하는지, 그리고 어떤 인덱스를 사용하는지 등을 이해하는 것이 더 중요함.아무런 옵션 없이 EXPLAIN 명령을 실행하면, 쿼리 문장의 특성에 따라 표 형태로 된 1줄 이상의 결과가 표시됨.표의 각 라인(레코드)은 쿼리 문장에서 사용된 테이블(서브쿼리로 임시 테이블을 생성한 경우 그 임시 테이블까지 포함)의 개수만큼 출력됨.실행 순서는 위에서 아래로 표시됨(UNION이나 상관 서브쿼리와 같은 경우 순서대로 표시되지 않을 수도 있음).출력된 실행 계..

목차10. 실행 계획10.1 통계 정보MySQL 서버는 5.7 버전까지 테이블과 인덱스에 대한 개괄적인 정보를 가지고 실행 계획을 수립함.하지만 테이블 칼럼의 값들이 어떻게 분포되어 있는지에 대한 정보가 없기 때문에, 실행 계획의 정확도가 떨어지는 경우가 많았음.MySQL 8.0 버전부터는 인덱스되지 않은 칼럼들에 대해서도 데이터 분포도를 수집해서 저장하는 히스토그램(Histogram) 정보가 도입됨. 히스토그램이 도입됐다고 해서 기존의 테이블이나 인덱스의 통계 정보가 필요치 않은 것은 아님.10.1.1 테이블 및 인덱스 통계 정보비용 기반 최적화에서 가장 중요한 것은 통계 정보임.통계 정보가 정확하지 않다면 엉뚱한 방향으로 쿼리를 실행할 수 있기 때문임. 부정확한 통계 정보 탓에 0.1초에 끝날 쿼리에..

목차9.4 쿼리 힌트MySQL 서버가 서비스의 비지니스를 완벽히 이해하지 못하므로, 서비스 개발자나 DBA가 옵티마이저에게 부족한 실행 계획을 어떻게 수립하는지 알려주기 위한 목적으로 MySQL에서는 힌트를 제공함.MySQL 서버에서 사용 가능한 쿼리 힌트는 다음과 같이 2가지로 구분할 수 있음.인덱스 힌트: 예전 버전의 MySQL에서 사용된 힌트옵티마이저 힌트: MySQL 5.6 버전부터 추가된 힌트이 책에서는 옵티마이저 힌트가 아닌 것은 인덱스 힌트 절로 분류함.9.4.1 인덱스 힌트STRAIGHT_JOIN과 USE INDEX 등을 포함한 인덱스 힌트는 MySQL 서버에 옵티마이저 힌트가 도입되기 전 사용된 기능으로, SQL 문법에 맞게 사용해야 하기 때문에 ANSI-SQL 표준을 준수하지 못함.My..

✅문제: 1260번📌개념정리(1) 깊이 우선 탐색 (DFS, Depth First Search)정의: 그래프 탐색 알고리즘 중 하나로, 현재 노드의 모든 자식을 방문한 뒤 다음 노드로 이동하는 방식으로 탐색함.스택 구조를 활용함 (재귀 함수로 구현 가능).한 노드에서 최대한 깊이 이동한 뒤, 더 이상 이동할 수 없으면 되돌아가서 탐색함.경로 찾기, 네트워크 연결성 확인 문제에 활용됨.(2) 너비 우선 탐색 (BFS, Breadth First Search)정의: 그래프 탐색 알고리즘 중 하나로, 현재 노드와 인접한 노드들을 모두 방문한 뒤 다음 단계로 이동함.큐 구조를 활용함.같은 깊이에 있는 노드들을 우선적으로 방문함.최단 경로 찾기, 레벨 탐색 문제에 활용됨.📌문제풀이주어진 그래프에서 특정 노드 v..