jhphon0730

[반복문] LeetCode 125번 문제 학습

문제 설명Valid Palindrome 문제는 주어진 문자열이 회문(Palindrome)인지 아닌지 판단하는 거임. 회문이 뭐냐면, 문자열을 뒤집어도 똑같은 거. 예를 들어, "racecar"는 회문이지만 "hello"는 아님.근데 이 문제엔 조건이 좀 붙음:대소문자 구분 안 함. 즉, 'A'랑 'a'는 같은 거로 취급.특수문자, 공백, 기호는 무시. 알파벳이랑 숫자만 신경 쓰면 됨.예를 들어, "A man, a plan, a canal: Panama"는 다 정리하고 나면 "amanaplanacanalpanama"가 돼서 회문이 맞음.또 다른 예로, "race a car"는 "raceacar"가 돼서 회문이 아님.결론적으로, 문자열을 정리한 다음에 회문인지 체크해야 함.문제를 푼 과정소문자를 대문자로 변..

[반복문] LeetCode 121번 문제 학습

문제를 푼 과정 처음엔 완전 탐색으로 구현해봤음→ 모든 날짜 쌍을 비교해서 최대 이익을 구하는 방식→ 작은 입력엔 잘 돌아가지만 큰 입력에서 느려짐그래서 최적화된 알고리즘으로 개선함→ 지금까지 본 가장 싼 가격(minPrice) 을 저장해두고→ 현재 가격 - minPrice 로 이익을 계산해서 최대값을 업데이트함→ 이러면 한 번의 순회로 해결 가능해서 시간복잡도 O(n)임 문제에 대한 설명주어진 배열 prices는 각 날짜의 주식 가격을 의미함.이 중 하루를 골라 주식을 사고, 그 이후 중 하루를 골라 팔아서얻을 수 있는 최대 이익을 구하는 문제임.조건은 단순함:한 번만 사고, 한 번만 팔 수 있음무조건 나중에 사는 게 아님. 산 날보다 뒤에 팔아야 함문제를 풀려면 어떤 알고리즘을 써야 하는지처음 떠오를..

문제를 푼 과정118번에서 파스칼의 삼각형 전체를 만든 코드를 활용했음.119번은 특정 행만 필요하니까 인자와 반환값만 조정했음.쉽게 맞췄다고 하니 로직이 잘 들어맞았음.문제에 대한 설명이 문제는 파스칼의 삼각형에서 주어진 행 번호(rowIndex)의 행을 반환하는 문제임.예를 들어 rowIndex = 3이면 [1,3,3,1]을 반환해야 함.이전 행을 기반으로 현재 행을 계산하는 방식이 118번과 같음.문제를 풀려면 어떤 알고리즘을 써야 하는지반복문을 사용해서 각 행을 순차적으로 계산하면 됨.동적 프로그래밍처럼 이전 행의 값을 재활용하는 방식이 간단함.필요한 행만 반환하도록 마지막에 슬라이싱하면 됨.package mainimport ( "fmt")func getRow(rowIndex int) []int ..

문제를 푼 과정파스칼의 삼각형을 만들기 위해 2D 배열을 초기화했음.각 행의 크기를 행 번호에 맞게 설정하고 모두 1로 채웠음.아직 숫자 계산 로직은 없어서 완성되지 않았음.func generateArray(numRows int) *[][]int { row := make([][]int, numRows) for i := 1; i  문제에 대한 설명이 문제는 파스칼의 삼각형을 주어진 행 수만큼 생성하는 문제임.각 행의 숫자는 이전 행의 인접한 값의 합으로 계산되며, 양 끝은 1임.결과는 2D 배열로 반환해야 함.문제를 풀려면 어떤 알고리즘을 써야 하는지반복문을 사용해서 각 행을 순차적으로 생성하면 됨.이전 행의 값을 기반으로 다음 행을 계산하는 방식이 간단함.동적 프로그래밍처럼 이전 결과를 재활용하면 효율적..

문제에 대한 설명이 문제는 이진 트리에서 루트부터 리프까지의 경로 합이 targetSum과 같은지 확인하는 문제임.경로가 리프에서 끝나야 하고, 그 합이 targetSum과 일치해야 함.한 경로라도 조건을 만족하면 true를 반환하면 됨.문제를 푼 과정DFS로 경로 합을 계산하려고 재귀 함수를 작성했음.리프 노드에서 합을 체크하려 했지만 로직이 맞지 않았음.에러가 발생한 건 널 포인터 참조와 합 계산 방식 때문임.type TreeNode struct { Val int Left *TreeNode Right *TreeNode}func dfs(root *TreeNode, targetSum int) bool { if root == nil { return false } if root.Left == nil && ..

문제를 푼 과정처음에는 최대 깊이를 구하는 로직으로 작성해서 틀렸음.최소 깊이를 구하려고 작은 값을 선택했지만, 루트에서 따로 계산해서 실패함.재귀 하나로 통합해서 리프까지의 최소 경로를 찾도록 수정함.문제에 대한 설명이 문제는 이진 트리의 최소 깊이를 찾는 문제임.루트에서 가장 가까운 리프 노드까지의 깊이를 계산해야 함.한쪽 자식이 없으면 그쪽은 무시하고 반대쪽 깊이를 구해야 함.이 문제를 풀려면 어떤 알고리즘을 써야 하는지재귀를 사용해서 트리의 깊이를 탐색해야 함.리프 노드에 도달했을 때 최소 깊이를 계산해야 함.DFS를 활용해 모든 경로 중 가장 짧은 길이를 찾으면 됨.package mainimport "fmt"type TreeNode struct { Val int Left *TreeNode Rig..

이 문제는 오름차순으로 정렬된 배열을 높이 균형 이진 탐색 트리(Height-Balanced BST)로 변환하는 거임  문제 이해입력: 오름차순으로 정렬된 배열 (예: [-10, -3, 0, 5, 9]).출력: 이진 탐색 트리(BST)인데, 높이가 균형을 이루고 있어야 해. BST는 왼쪽 서브트리의 모든 값이 노드보다 작고, 오른쪽 서브트리의 모든 값이 노드보다 큰 트리임높이 균형: 트리의 왼쪽과 오른쪽 서브트리 높이 차이가 최대 1이어야 함.정렬된 배열을 BST로 만들 때, 중간 값을 루트로 선택하면 높이 균형을 유지할 수 있배열이 정렬되어 있으니까 중간 값은 자연스럽게 왼쪽 절반과 오른쪽 절반을 나눠서 시작.왼쪽 절반은 왼쪽 서브트리, 오른쪽 절반은 오른쪽 서브트리로 재귀적으로 만들면 균형이 잡힘.이..

사용한 알고리즘DFS를 사용하여 풀었음 왜 DFS냐?: 트리의 각 경로를 끝(리프 노드)까지 내려가서 깊이를 계산하고, 그 결과를 위로 올리면서 최대값을 찾으니까 깊이 우선 탐색 방식임재귀: 각 노드에서 왼쪽과 오른쪽으로 재귀 호출을 해서 트리의 깊이를 탐색함 특히 후위 순회와 비슷한 형식으로 풀면 되는데, 왼쪽과 오른쪽 자식을 먼저 탐색한 뒤, 현재 노드에서 결과를 처리(최대값 선택)하는 방식이 후위 순회의 특징과 맞다고 생각함.이 문제를 풀기 위해 필요한 알고리즘재귀적 DFS (사용한 방식)가장 직관적이고 간단하기 때문임각 노드에서 왼쪽과 오른쪽 깊이를 재귀적으로 구하고, 최대값을 취하는 방식.트리의 구조를 자연스럽게 활용 가능.왜 DFS를 추천하나?이 문제는 깊이를 구하는 게 목적이라, 끝까지 내려..

DFS를 기반으로 한 재귀적 알고리즘이 문제는 이진 트리가 좌우 대칭인지 확인하는 것이 문제의 핵심.기존 100번 문제는 두 트리를 동시에 내려가며 "같은지"를 확인하는 데 초점을 두었지만 지금은 거울 형식으로 대칭하는 지 확인하는 것인 핵심인 문제임여전히 재귀적 DFS. 100번 문제와 비슷하지만, 비교 대상이 "동일성"이 아니라 "대칭성"이라서 자식 노드의 연결 방향이 반대인 점만 다르다는 것을 알고 풀면 됨  "Symmetric Tree"는 트리가 거울 대칭인지 확인하는 문제. 즉, 루트의 왼쪽 서브트리와 오른쪽 서브트리가 서로 대칭이어야 함예를 들어, 왼쪽 서브트리의 왼쪽 자식은 오른쪽 서브트리의 오른쪽 자식과 같아야 하고, 왼쪽 서브트리의 오른쪽 자식은 오른쪽 서브트리의 왼쪽 자식과 같아야 함p..

DFS를 기반으로 한 재귀적 알고리즘트리의 루트부터 시작해서 왼쪽과 오른쪽 자식으로 깊이 들어가며 비교하니까, 깊이를 우선적으로 탐색하는 DFS의 특성을 따르고 있음. 트리 비교를 위한 재귀적 DFS로 문제를 풀었음 두 개의 이진 트리가 다른 지 비교하는 문제. DFS-중위 순회를 통해 결과 값이 다른 지 같은 지 비교하는 방식으로 구현을 하려고 하였으나. 구조적 동일성 확인의 한계: 중위순회는 노드 방문 순서만 기록하니까, 트리의 구조가 다르더라도 우연히 값의 순서가 같게 나올 가능성이 있음. 예를 들어, 한쪽 트리는 왼쪽 서브트리만 있고 다른 쪽은 오른쪽 서브트리만 있는 경우, 중위순회 결과가 동일할 수 있는데 실제로는 구조가 다름추가 검증 필요: "Same Tree" 문제는 값뿐만 아니라 구조도 완..