군만두의 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_..

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

✅문제: 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) 정렬정의: 데이터를 특정 기준에 따라 재배열하는 작업작업을 마감 시간 기준으로 정렬하여, 가장 늦게 마감해야 하는 작업부터 역순으로 스케줄링할 수 있음.📌문제풀이주어진 작업의 소요 시간과 마감 시간을 기반으로 모든 작업을 수행할 수 있는 가장 늦은 시작 시간을 계산하는 문제임. 각 작업은 소요 시간과 마감 시간이 주어지며, 모든 작업을 마감 시간 내에 끝낼 수 있..