Bibi's DevLog 🤓🍎

[Swift] 그래프와 탐색 알고리즘 DFS/BFS 가장 도움이 된 글.. https://nareunhagae.tistory.com/56 🙏 '이것이 코딩 테스트다' 책도 함께 참고해 작성했습니다. 그래프 Graph 그래프에서는 모든 객체는 정점(노드)로 나타내고, 모든 관계는 간선으로 나타낸다. 노드 Node / 정점 Vertex 그래프에서 데이터를 담는 단위. (그림에서의 동그라미 = 노드) 두 노드가 인접하다adjacent : 두 노드가 간선으로 연결되어 있음을 의미 간선 Edge 노드 사이를 잇는 선. 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 알고리즘 문제 중 1차원 배열, 2차월 배열 탐색 문제를 그래프 형태로 생각하면 문제를 쉽게 풀 수 있다. 그래프 표..

[210701] Hello Coding 알고리즘 4. 퀵 정렬 분할 정복 divide and conquer : 문제 해결 방법 중 가장 유명한 재귀적 알고리즘. 특정 알고리즘(기술)이 아닌, 문제를 풀기 위한 방법론이다. 분할 정복의 증명 - '유클리드 호제법 Euclid's algorithm' 참고하기 예시 : 농부가 어떤 땅을 똑같은 정사각형 토지로 나누고 싶을 때. 분할 정복으로 푸는 단계. 기본 단계를 찾는다. 이 부분은 가능한 가장 간단한 문제여야 한다. 전체 문제가 기본 단계가 될 때까지 나누거나 작게 만든다. 분할 정복에서는 재귀 함수를 호출할 때 마다 문제를 작게 나누어야 한다. 예제 Q. 배열의 모든 숫자를 더한 합계 구하기. 반복문이 아닌 재귀 함수를 사용한다. 기본 단계를 찾는다. (..

3장. 재귀 시작하기에 앞서 예제 코드 직접 실행해 보기 적어도 한 번은 연필과 종이를 가지고 재귀함수의 실행 과정을 따라가 보기. 의사코드(pseudocode, 슈도코드) : 문제와 풀이 방법을 간단한 코드로 설명한 것. 실제로 동작하진 않음 재귀 recursion 재귀 함수가 자기 자신을 호출하는 것. 문제 : 여러 겹으로 포장된 상자들이 있고, 그 상자가 또 다른 상자들 속에 들어 있다. 몇 개일지 모르는 상자들 중 열쇠가 들어있는 상자를 찾아야 한다. 방법 1 : 반복문 사용하기 내부를 확인할 상자를 쌓아놓는다(=상자 더미). 상자 하나를 집어서 내부를 확인한다. 만약 안에 상자가 있다면, 확인할 상자 더미에 놓은 뒤 2로 돌아간다. 만약 안에 열쇠가 있다면 작업을 종료한다. 아래는 위 과정에 대..

[210630] (어제에 이어서 작성) Hello Coding 알고리즘 2장. 선택 정렬 배열, 연결리스트, 선택 정렬에 관해 공부한다. 메모리가 동작하는 방법 컴퓨터 메모리의 동작 방식. 엄청나게 많은 서랍이 있고, 각 서랍에는 주소가 붙어 있다. 메모리에 무언가를 저장할 때는 컴퓨터에게 공간을 요청한다. 여러 개의 원소를 저장할 때, '배열'과 '리스트' 두 방식 중 하나를 선택한다. 배열 vs 연결 리스트 배열 (array) 친구들과 영화를 보러 가서 자리를 찾을 때에 비유할 수 있다. 3명이서 좌석을 예약했는데 한 명이 더 왔다면, 4명이서 붙어 앉을 수 있는 좌석으로 다 같이 옮겨 앉아야 함 배열의 모든 원소는 같은 자료형이어야 한다. 장점 : READ가 빠르다. 인덱스 index : 배열에서는..

[210628] Hello Coding 알고리즘 1장. 알고리즘의 소개 들어가는 글 알고리즘 : 어떤 일을 하기 위한 명령의 집합 성능 여러 알고리즘들의 장단점과 차이점을 이해하고 쓸 줄 알아야 한다. 다른 자료구조 / 알고리즘을 쓰는 것만으로도 성능이 크게 달라질 수 있다. 단순 탐색 simple search 탐색 문제를 풀 때 사용. 동작 : 단순히 원소 하나하나를 맞는지 아닌지 일일이 확인하는 방식 n개의 원소 리스트에서 최대 n번만에 정답을 찾음 이진 탐색 binary search 탐색 문제 search 를 풀 때 사용. 이진 탐색은 매 단계마다 절반의 후보들을 없앨 수 있다. input : 정렬된 원소 리스트 output : 원하는 원소가 있으면 그 위치를 반환. 아니면 null 반환. 동작 정..

프로그래머스 Lv1 - 자연수 뒤집어 배열로 만들기 class Solution { public int[] solution(long n) { String nStr = Long.toString(n); String[] nStrArr = nStr.split(""); int length = nStr.length(); int[] answer = new int[length]; for (int i = 0; i < length; i++) { answer[i] = Integer.parseInt(nStrArr[length-i-1]); } return answer; } }혼자서도 잘 해냈나요? : 무수한 구글링 끝에 ⭕ 막힌 부분 : 효율성을 위해 답에 넣어진 숫자는 빼야 할 것 같은데 어떻게 빼지? 끝자리 * 10의 배수 ..

[Hello Coding] 알고리즘 1장. 알고리즘의 소개 알고리즘이란? : 어떤 일을하기 위한 명령의 집합. 특히 다른 코드보다 속도를 빠르게 하거나, 문제를 풀기 위한 것. 알고리즘의 성능 여러 알고리즘들의 장단점과 차이점을 알아야 한다. 단순히 다른 자료구조/알고리즘을 사용하는 것만으로도 성능이 크게 달라진다. 이진 탐색 탐색 문제 Search : 주어진 데이터에서 원하는 항목을 어떤 방법으로 찾을 것인가. 예) 1부터 100까지의 숫자들 중 &#39;78&#39;이라는 숫자 찾기 단순 탐색 Simple search : 처음부터 하나씩 순서대로 항목을 탐색 예) 1, 2, 3, 4, ... 77, 78 순으로 탐색해 78을 찾는다. N개의 원소를 가진 리스트에서 최대 N번 만에 답을 찾을 수 있다...