Development/Problem Solving 7

Leetcode) TreeNode.java

Intro LeetCode 의 코딩 문제들을 풀다보면 자주 나오는 Node 계열 클래스들이 있습니다. 대표적으로 TreeNode와 ListNode 등이 있는데요. 처음 이런 문제를 접할 때에는 너무 당황해서 어떻게 풀어야 할지도 모르고 테스트 코드를 작성하기도 참 막막 한데요, 지금은 어느정도 익숙 해 졌다 보니 묵묵히 inner class로 복사해 집어 넣은 후에 코드를 작성 하기 시작합니다. TreeNode 예제 문제 https://leetcode.com/problems/range-sum-of-bst/ ListNode 예제 문제 https://leetcode.com/problems/merge-nodes-in-between-zeros/ 하지만 매번 같은 코드를 복사해서 이너클래스로 넣어서 만드는 것도 ..

Leetcode) 소개 및 풀이 코드 Github에 자동 커밋방법

Intro 개발공부를 시작 한 이후로 오랜 취미중 하나였던 온라인 게임을 그만 두었습니다. 사실 온라인 게임을 오래동안 해 왔던 이유는, 그 자체가 재밌다는 이유도 조금은 있었지만 그보다는 주로 무료한 시간을 달래기 위함이었습니다. 그러면서 게임이라는 가상 공간에서 모르는 사람들과 만나 협력하고 경쟁하여 승리를 따냈을 때의 그 달콤한 성취감에 중독되어서 시간이 남는다. 무료하다. 이 두가지 조건이 만족될때면 어김없이 게임을 하곤 했었습니다. MAY 2020. Queenstown, New Zealand 퇴근후 집에 오면 어김없이 이런 열악한 환경에서도 리그오브레전드 혹은 롤토체스를 즐겨 하곤 했습니다. 그러다 한국에 돌아와 2020년 11월. 개발 공부를 시작 한 이후로 게임을 하는 첫번째 조건이었던 시간..

문제풀이: 가장 긴 팬린드롬(palindrome)

Intro 프로그래머스 3단계에 해당하는 가장 긴 팬린드롬 문제를 풀어보았습니다. 팰린드롬은 앞으로 읽어도, 반대로 읽어도 똑같은 단어를 말하는데요, 기러기, 스위스등이 있습니다. 2020년에 개봉한 크리스토퍼 놀란 감독의 영화 TENET에서도 영화 전반에 걸쳐 palindrome의 의미가 녹아들었으며, 그 제목 자체도 팬린드롬 이였습니다. 문제가 워낙에 간단하기 때문에 금방 풀 거라고 생각 했는데, 몇가지 간과했던 점들이 있기 때문에 총 4번의 시도 끝에 풀이 하였습니다. 특별한 알고리즘이 필요한 문제는 아니지만 효율성 체크가 기다리고 있는 문제이기 때문에 제법 고민이 필요합니다. 문제 문제의 조건 자체는 굉장히 간단합니다. leetcode.com 에서는 공개된 2107개의 테스트 중 무려 5번째에 위..

JAVA로 알아보는 힙 (Heap) 자료구조

Heap Heap은 최소값 및 최대값을 최대한 빠르게 찾아내기 위해 특별히 고안된 자료 구조 입니다. 완전 이진트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리의 형태)를 기본으로 하고 있으며, 그 목적에 걸맞게 두개의 타입으로 나뉩니다. Max-Heap Max-Heap 에서 root 노드의 key는 무조건 해당 노드의 자식 노드들의 key보다 크거나 같습니다. 또한 같은 속성이 모든 sub-tree 들에게도 재귀적으로 적용됩니다. 간단히 말해 Max-Heap 트리에서 자식 노드에 딸린 트리 하나 하나가 모두 Max-Heap의 조건을 만족합니다. Min-heap Min-Heap 에서는 반대로 root 노드의 키값이 모든 자식들의 키 보다 작거나 같습니다. 또한 재귀적으로 자식 트리들 하나..

피보나치 수열과 프로그래머스 땅따먹기 문제로 알아보는 Dynamic Programming (동적 프로그래밍)

https://programmers.co.kr/learn/courses/30/lessons/12913 자세한 문제는 programmers를 통해 확인 해 주세요. 문제 땅따먹기라고 하지만, 우리가 알고있는 땅따먹기와는 거리가 있습니다. 차라리 어렸을 적 하고 놀던 "사방치기"를 떠올리는 것이 조금 더 가깝습니다. 맨 첫줄 부터 시작해서 1 2 3 5 5 6 7 8 4 3 2 1 한줄씩 아래로 내려가는데, 일단 지금 밟은 열은 다음번 행에서 또 밟을 수가 없습니다. 예를 들어 첫 줄에서 5로 시작했다면, 다음 줄에서는 8을 밟을 수 없습니다. 탐욕법 무조건 지금 상황에서의 최선을 선택하는 "탐욕법" 으로 문제를 푼다면 다음 줄에서 더 큰 숫자의 기회를 잃을 수 있기때문에 다른 접근이 필요합니다. 위의 예시..

무한깊이 그리고 너비우선탐색 BFS

Intro DFS DFS는 트리나 그래프에서 한 루트로 검색하다가 특정 상황에서 최대한 깊숙히 들어가서 확인 한 뒤, 다시 돌아가 다른 루트를 탐색하는 방식입니다. 미로찾기를 생각하면 쉬운데요, 한 방향으로 끝까지 들어갔다가 막다른 길에 다다르면 (트리의 바닥에 도착) 왔던 길을 돌아가서 다른 방향으로 갑니다. 이 일을 찾는 값이 나올 때까지 혹은 모든 트리를 순회 할 때 까지 반복합니다. DFS의 가장 큰 약점은 깊이가 무한으로 이어지면 빠져나올 수 없다는 점 입니다. 미로를 가다보면 왔던길이 또 나타나는 그런 미로도 있습니다. 가끔 등산을 할때도 그런 길에 들어갔다가 왔던 길에 다시 도착하는 경험을 해본 분들이 있을텐데요, 이럴 경우는 BFS를 이용해 해결 해야 합니다. BFS BFS는 너비우선탐색 ..

n중 for문과 깊이우선탐색 DFS

Intro 재미삼아 취미로 시간 날때마다 한 두 문제씩 풀었던 programmers의 코딩 테스트 연습이 어느덧 100문제를 넘어갔습니다. for문과 배열만 있다면 어떤 문제든 해결 할 수 있다고 말씀해주신 학원 초급 자바선생님의 말씀대로, 왠만한 문제는 머리속으로 떠올린 아이디어를 간단하게 노트에 적어 구체화 시킨 후에 그것을 IDE 상에 코드로 구현을 하면 해결되지 않는 문제가 없었습니다. 하지만 어느순간부터는 빈번히 막히는 일이 발생했고, 이제는 문제를 만났을때 "n중 for문 으로 풀어야지!" 라는 말도 안되는 해결 방안이 제시되기 시작했습니다. 그간 외면했던 DFS/ BFS를 정면으로 마주해야 하는 순간입니다. (물론 탐색하는 과정은 결국 동일합니다) DFS DFS는 깊이우선 탐색 Depth F..