의식이 흐르는대로 해보는 프로그래밍

목차접근Easy난이도라는데, 고민을 많이 꽤 했던 것 같다. Grind 75를 따라가면서, 릿코드 문제를 풀어보고 있는 도중에 접했다. Binary Tree의 지름을 구하는 문제이다. 여기서 Diameter(지름)의 의미는 트리에 존재하는 두 노드간의 가장 긴 거리를 의미한다. root를 거칠수도, 거치지 않을 수도 있다. 처음 접근은 정말 단순하게 생각했던 것 같다. 그냥 root의 left, right의 가장 긴 깊이를 구해서 더하면 끝 아닌가? 생각했다. 왜냐하면 가장 긴 거리가 나오려면, 무조건 root 노드를 지나가야한다고 생각했기 때문이다.근데 엄청난 예제가 등장했다...두둥  이 트리는 root를 거치지 않고서, right노드의 하위노드간에서 diameter가 등장한다.(-1 -> -2)그래..

목차접근오랜만에 작성하는 글.. 인턴기간동안, 회사에서 처음 배우는 개념이나, 처음 다루는 라이브러리와 프레임워크들이 많았어서 정신없이 지나갔다... 이번년 회고글을 작성할 예정이므로 그건 나중에 차차.. 슬라이딩 윈도우 개념으로 해결해보려고 했다. 접근 1처음은 가장 단순한 접근으로 생각해보자.이중 for문을 사용해서 window의 크기, 시작 지점을 반복해가면서 해당 범위의 문자열에 대해서 character를 카운트 해가면서 구하는 방법이 있다.그 후 특정 문자가 `K`회 카운트 되었으면, 맞는 조건에 대해서 길이를 갱신해준다. 하지만 딱 봐도 반복문을 업데이트 해나가는 것과 반복마다 각 길이의 문자열에 접근해나가는 게 시간초과가 발생하기 아주 좋아보인다. 접근 2매 반복마다 문자열의 characte..

목차 접근 DP를 이용해서 행렬 곱셈을 진행할 때 최소가 되는 곱셈 연산의 횟수를 구하는 문제다. 행렬 자체는 연산이 가능하도록 순서대로 주어지는데, 우리는 연산 순서의 우선순위를 결정해야한다. 예시에도 잘 나와있지만, 일단 옮겨보도록 하겠다. 예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자. AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈 연산의 수는 5×3×2 + 5×2×6 = 30 + 60 = 90번이다. BC를 먼저 곱하고 A를 곱하는 경우 A(BC)에 필요한 곱셈 연산의 수는 3×2×6 + 5×3×6 = 36 + 90 = 126번이다. 이렇게 행렬은 연산 우선순위를 변경함으로써, 같은 연산을 진행할..

목차 접근 배낭(Knapsack) 알고리즘 문제다. 배낭 알고리즘에 대해선 자세히 써놓았던 이전 아티클을 참고해보자. 2023.12.11 - [알고리즘(Algorithm)] - [BOJ] 12865번 : 평범한 배낭(DP, Knapsack) 해결 배낭 알고리즘은 대표적인 DP 문제로 축의 의미를 어떻게 정의할건지가 중요하다. 당연히 한 축은 탐새할 물건의 인덱스가 되어야 할 것이다. 나머지 한 축은 가치를 저장할 시점의 용량이 되어야하는데, 여기선 두 가지가 있다. 하나는 사용 중인 메모리 바이트 수(`M`) 다른 하나는 비활성화 했을 때의 비용(`C`) 다. 하지만 메모리 바이트 수를 축으로 삼자니 범위가 $ 1 \le M \le 10,000,000 $ 로 말이 안된다. 그럼으로 비활성화 했을 때의 비..

목차 접근 Ref: [Velog] 그림으로 알아보는 LCS 알고리즘 [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다. velog.io [Wikipedia] Longest Common Subsequence Longest common subsequence - Wikipedia From Wikipedia, the free encyclopedia Algorithmic problem on pairs of sequences Comparison..

목차 접근 !! 이 문제를 풀기전에 조금 더 쉬운 버젼인 아래의 문제를 먼저 해결해보고 오는 것을 추천한다. [BOJ - 2467번: 용액] 위의 용액 문제 또한 투포인터로 해결할 수 있다. 정렬이 되어 있는 용액 리스트에서 두 용액을 합쳤을 때 특성값이 0에 가장 가까운 두 용액을 구하는 문제이다. 정렬 또한 되어있기 때문에, 그냥 투포인터로 0에 가장 가까운 방향으로 업데이트를 진행하면서 정답을 구하면 되는 문제이다. 그럼 이제 이 문제는 어떻게 해결할 것인가? 이번엔 세개의 용액을 합쳐서 특성값이 0에 가장 가까운 세 용액을 구하는 문제이다. 일단 위의 그냥 용액과는 다르게 전체 용액의 수 `N` 은 5,000 이하다. 쓰리포인터..? 뭐라고 말해야할지 모르겠지만, 하나는 고정해두고 나머지 두개에 ..

목차 접근 최소 스패닝 트리를 구하고, 그 비용을 구하는 문제다. 문제 자체는 간단하기에 크루스칼 알고리즘을 이용해서, 쉽게 해결했다. 해결 각 별 사이들간의 거리를 미리 다 구해놓고, 연결된 별과 그 거리를 저장해준다. 또 거리를 기준으로 오름차순 정렬을 수행한 뒤, 크루스칼 알고리즘을 수행한다. 크루스칼 알고리즘은 Union-Find 알고리즘을 수행하는데, 해당 내용은 이전 아티클을 참고하자. 2023.12.21 - [알고리즘(Algorithm)] - [BOJ] 1197번 : 최소 스패닝 트리(Kruskal) 코드 n = int(input()) coords = [] edges = [] for _ in range(n): a, b = map(float, input().split()) coords.appe..

목차 접근 `n`개의 정점을 가는 이진 트리의 정점에서 1 ~ n까지 중복 없이 번호가 매겨져 있다. 이런 이진 트리에서 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제다. 정말 많이 틀리고, 시간이 들었다. 여러 개선점에 대해서 생각해보는 시간이었다. 먼저 기본적인 접근에 대해서 생각해보자. 중위순회는 이진트리를 Left - Mid - Right 순으로 탐색을 진행한다. 후위순회는 이진트리를 Left - Right - Mid 순으로 탐색을 진행한다. 그럼 맨 처음 주어진 각각의 순회의 결과에서 후위순회의 마지막 결과값이 처음 트리의 Mid의 값이라는 것을 알 수 있다. 그럼 아래와 같으 과정을 거치면, 트리를 재귀적으로 분해해나갈 수 있다. 위에서 구한 Mid..

목차 접근 D.P.로 해결하는 간단한 문제. 근데 생각지도 못한 완전탐색을 진행하면서.. 너무 당연한 형태의 D.P.문제여서 그냥 풀면되겠지 했는데, 생각보다 점화식이 떠오르지 않았다. 왼발과 오른발에 대한 얘기가 있어서 어떻게 접근하지 하면서, 질문게시판 제목들을 보면서 대충 풀이를 유추했는데 시간복잡도에 관한 질문들이 많이 보였다. 그럼 혹시...? 하면서 전체탐색을 진행하며 D.P.를 수행하여 해결했다. 해결 이번에 밟아야할 발판에 대해서, (왼발, 오른발) 모든 조합에 대한 경우의 수를 탐색하며 D.P.를 수행했다. 이렇게 전체 탐색에 대한 의심을 한 이유는 입력의 길이가 100,000개 까지 들어올 수 있다는 것, (왼발, 오른발)의 조합이 5 x 5 = 25가 나옴으로 최대 시간복잡도는 `O(..

목차 접근 스도쿠를 풀어내는 문제다. 스도쿠 문제는 N과M 문제와 더불어서 백트래킹으로 푸는 가장 대표적인 예제 중 하나이다. DFS를 수행하면서, 특정 조건을 만족하는지 체크하고 DFS가 끝나면, 다시 원래 상태로 되돌려놓는 알고리즘이다. 이렇게 DFS 알고리즘 시작단에 끝나는 조건을 명시해주면, 특정 조건이 맞는 케이스일 때까지 전체적으로 탐색을 진행할 것이다. 해결 백트래킹으로 해결하자. 0인 위치를 먼저 기록해두고, 0인 위치를 하나씩 채워나가는 방식으로 구현을 진행하자. 또한 스도쿠의 정답이 여러개가 나올 수 있음으로 종료단에, return이 아닌 exit를 이용해서 한번만 출력하고 프로그램을 종료시켜줘야한다. 안그럼 출력 초과가 뜬다.. 코드 sdoku = [] zero_idx = [] for..