나짱's 블로그

안녕하세요 여러분~!오늘은 코테에서 종종 나오게 되는 순열과 조합을 살펴볼게요.이 또한 파이썬에서는 내장함수가 있지만우리의 Swift는 직접 구현해야 합니다 🥲하지만 이자식 나름 쉽더라구요? 같이 한번 뿌셔봅시당! 순열(Permutation)이란?순열의 정의부터 살펴볼게요. 순열이란서로 다른 n개 중에서 r개를 택하여 일렬로 배열하는 경우 입니다. 예제를 통해 알아볼까요?array = [1,2,3] array에서 2개의 요소를 고른다고 해봅시다.[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]] 이렇게 6개의 경우가 나올거에요.이때 순열은 순서가 다르면 다른 경우로 보기때문에[1,2] 와 [2,1] 은 다른 경우로 인식하게 됩니다. 조합이란?조합은 순열과 비슷한 개..

안녕하세요 여러분~!코테 알고리즘의 꽃인 BFSBFS 하나 잘 외워두면 든든~ 하게 코테 문제를 풀 수 있는데요같이 BFS 알고리즘 뿌셔봅시당 👊👊 BFS 알고리즘 이란?BFS는 Breadth First Search 의 약자로너비우선탐색이라고 불립니다.근접한 노드들부터 전부 탐색하겠다는 의미인데요.그림으로 BFS 동작 원리를 이해해볼까요? 아래와 같은 연결성을 가진 그래프(트리)가 있다고 합시다. 1번 노드부터 시작하여 연결된 모든 노드를 방문하고자 합니다. 우선 1번노드와 연결된 2,3번 노드를 예약하겠습니다.현재 방문한 노드: [1]현재 예약된 노드: [2,3] 예약된 노드들 중 먼저 예약된 2번노드를 방문합니다.2번 노드를 방문했더니 새로 연결된 4,5번 노드를 발견했네요.4,5번 노드를 예약리..

안녕하세요 여러분~!자료구조 하면 빠질수 없는 기본중에 기본 스택과 큐 를 한번쯤 들어보셨을텐데요?자료형은 둘 다 Array를 사용하지만 데이터 입출력 방식에서 차이가 있습니다. 스택(Stack) 이란?스택은 Array로 나타내는 후입선출 형태의 선형 자료구조입니다.후입선출 = LIFO(Last In First Out)나중에 넣은 데이터부터 출력한다는 뜻인데요. Swift로 구현해볼까요?다음과 같이 리스트가 있습니다.array = [] 1부터 3까지의 숫자를 리스트에 입력해볼게요.array.append(1)array.append(2)array.append(3)array = [1,2,3] 출력은 어떻게 할까요?스택은 나중에 넣은 데이터부터 출력하기 때문에 removeLast()를 이용해줄게요. array...

안녕하세요 여러분~!이번에는 다익스트라를 배워보도록 하겠습니다.이름만 들으면 아주아주 어려울 것 같은 요놈사실 개념만 잘 알아놓으면 보너스 문제라는 사실 알고계셨나요?다익스트라 자식,, 사실은 외강내유에요😝 다익스트라란?다익스트라는 최단 경로 탐색 알고리즘입니다최단 경로? 최소값? = Heap?맞습니다 다익스트라는 힙을 이용하여 구현할 수 있습니다. 일단 그림으로 다익스트라 알고리즘의 동작방식을 이해해볼까요? 각 노드가 간선으로 연결되어있고 가중치를 가지고 있네요위에서 말씀드린대로 최단경로탐색을 할건데요그렇다면 가중치가 작은 경로부터 탐색을 해야겠죠 일단 시작노드인 1부터 탐색을 시작해볼까요?노드1에서 방문 가능한 노드는 2,3,4가 되겠네요현재 방문할 수 있는 노드의 후보군은 2,3,4 입니다.이중..

안녕하세요 여러분~!파이썬에서는 당연하게 사용했던 Heap 자료구조...Swift로는 직접 구현해야 하는데요 🥲그렇다고 보너스 문제인 힙 문제를 포기할 순 없죠힙 템플릿 외우고 야나도 힙 뿌실수 있다~ 외쳐봅시다!!!! Heap 자료구조란?본격적으로 Heap에 대해 알아봅시다!힙 = 우선순위 큐 라고도 부르는데요이론적인 내용 쏙 빼놓고 핵심만 얘기하자면큐에서 가장 작은 (또는 가장 큰) 값을 방출하겠다 입니다.* 최대힙일때는 가장 큰 값, 최소힙일때는 가장 작은 값 방출 이때 주의할 개념이 큐의 첫번째 인자(index=0) 는 최솟값을 보장하지만그외 나머지 요소들은 정렬되지 않은 상태라는 것을 유의해야됩니다! 엇 잠깐만요! 큐에서 가장 작은 값을 방출하려면그냥 정렬해서 첫 번째 값 방출하면 되잖아요~여..