Development/Fundamentals 8

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

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

java로 작성해보는 정렬 알고리즘과 성능 비교

java로 작성해보는 정렬 알고리즘과 성능 비교 얼마전 정렬 알고리즘을 손 코딩 해 볼 기회가 있었습니다. 갑자기 눈앞에 정렬 알고리즘을 손코딩 해야 하는데, 제한시간도 있다 보니 잠시동안 고민이 되었습니다. 당장에 간단하게 작성할 수 있는 버블정렬을 선택해 다른 문제 풀이에 쓸 시간을 조금 더 벌 것인가 아니면 자바를 처음 배울때 직접 구현해보려다가 못했던 퀵정렬을 한번 작성해 볼 것인가. 결론부터 말하자면 안전한 길을 택했습니다. 솔직히 버블정렬의 쉬운 난이도에도 불구하고 항상 실제로 코드를 구동해보고 테스트 하기 전 까지는 맞는지 문제가 있는지 확신이 서지 않았습니다. ​ ​ 과거로 돌아가, 학원에서 초급 자바시간에 정렬에 대해 배우는 기회가 있었습니다. 선택, 버블, 삽입 정렬에 대해서 간단하게 ..

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

피보나치 수열과 프로그래머스 땅따먹기 문제로 알아보는 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

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

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

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

네트워크 표준 모델 OSI 7 계층 ( OSI 7 Layer)

네트워크 표준 모델 OSI 7 계층 ( OSI 7 Layer) The Open Systems Interconnection model (OSI model) is a conceptual model that characterises and standardises the communication functions of a telecommunication or computing system without regard to its underlying internal structure and technology. Its goal is the interoperability of diverse communication systems with standard communication protocols. - https://..

객체지향설계 5대원칙 SOLID

객체지향설계 5대원칙 SOLID 학원 수업에서 선생님이 항상 강조하셨던 SOLID 원칙이 잘 이해가 되지 않아서 개인적으로 공부하기 위해 여러가지 검색을 해보고 많은 글들을 읽어보았습니다. 그러다 우연히 Youtube에서 41분짜리 영상을 접하게 되었는데, 앞부분만 잠깐 보려고 했던게 결국 영상을 마지막까지 보게 되었고 도움이 제법 많이 되었습니다. ​ https://www.youtube.com/watch?v=rtmFCcjEgEw 북 마케도니아 출신 개발자 Katerina Trajchevska가 2018년 암스테르담에서 열린 컨퍼런스에서 SOLID를 주제로 강연을 했던 내용인데요, 본인의 경험을 예로 들어가며 설명을 잘 해줘서 이해하기가 좋았습니다. SOLID는 Robert. C. Martin (Uncl..

Development/Fundamentals 2021.04.11 (4)

이진 탐색 알고리즘 (Binary search)

9주차 주말이 되었습니다. 저는 주말 아침에는 1~2시간 정도 프로그래머스에서 문제를 풉니다. 자기전에 문제를 풀면 밤새 자는동안 그 문제가 머리 속에 맴돌아서 밤늦게는 최대한 안풀려고 조심합니다. programmers.co.kr/ 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시간이 좀처럼 나지 않아 틈날때 조금씩 하던게 이제 레벨1에서는 모든 문제를 끝내서 레벨 2 문제를 풀고 있습니다. 오늘도 그렇게 어려워 보이지는 않던 문제를 하나 골라 몇분만에 정확성 테스트를 모두 통과해서. 쉽게 해결하는 줄 알았는데, 갑자기 까꿍 하고 등장한 효율성 테스트....

반응형