github.com/taemin-kwon93 Github 보러가기 ->

Dev.Kwon Tae Min 78

LeetCode 46. Permutations

순열 만들기 서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1:Input: nums = [1,2,3]Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Example 2:Input: nums = [0,1]Output: [[0,1],[1,0]]Example 3:Input: nums = [1]Output: [[1]]순열이 만들어지는 것에 대해 먼저 이해할 필요가 있다. 요소가 3개 일때 순열의 수는 3! / (3 - 3)! ..

LeetCode 42. Trapping Rain Water 빗물 트래핑

빗물 트래핑높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라 Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Example 1:Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue sec..

LeetCode 23. Merge k Sorted Lists, k개 정렬 리스트 병합

문제 링크 문제 설명: k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.원문설명: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.Merge all the linked-lists into one sorted linked-list and return it. Example 1:Input: lists = [[1,4,5],[1,3,4],[2,6]]Output: [1,1,2,3,4,4,5,6]Explanation: The linked-lists are:[ 1->4->5, 1->3->4, 2->6]merging them into one sorted list:1->1->2->3->4->..

병합정렬(Merge Sort)

병합 정렬(Merge Sort)은 배열을 재귀적으로 반으로 나누고, 각 부분을 정렬한 다음 다시 병합하여 전체 배열을 정렬하는 알고리즘이다.아래 내용은 배열을 나누고 병합하는 과정을 단계별로 설명한다. 주어진 배열[6, 4, 7, 3, 9, 1, 8] 배열을 반으로 나누기 (Divide)첫 번째 나누기 [6, 4, 7, 3, 9, 1, 8] / \[6, 4, 7, 3] [9, 1, 8]두 번째 나누기 [6, 4, 7, 3] [9, 1, 8] / \ / \ [6, 4] [7, 3] [9, 1] [8] / \ / \ / \[6] [4] [7] [3] [9] [1] [8]  배열을 병합..

비선형 자료구조 Graph

그래프란,객체의 일부 쌍(Pair)들이 '연관되어' 있는 객체 집합 구조를 말한다.그래프 이론에서 ‘그래프’는 수학적 구조를 의미하며, 이는 객체 간의 관계를 나타내는 도구다. 그래프는 두 가지 주요 구성 요소로 이루어져 있다.정점 (Vertices): 그래프의 기본 단위. 각 정점은 그래프에서 고유한 객체나 노드를 나타낸다.간선 (Edges): 정점 간의 연결을 나타낸다. 간선은 두 정점을 연결하여 그들 간의 관계를 나타낸다.그래프는 여러 종류로 나뉘며, 각각의 종류는 특정한 특성과 용도를 가진다무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프다. 예를 들어, 두 정점 A와 B를 연결하는 간선이 있다면, A에서 B로 또는 B에서 A로 이동할 수 있다.방향 그래프 (Direct..

프로그래머스 완주하지 못한 선수

완주하지 못한 선수 링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 설명:수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 입출력 예participantcompletionreturn["leo", "kiki", "eden"]["eden", "kiki"]"leo"["mari..

LeetCode 3. Longest Substring Without Repeating Characters

문제 : 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라. (링크) 풀이내용: 이 문제는 O(n)에 풀이가 가능하다.O(n) 풀이를 위해서는 '투 포인터'와 '슬라이딩 윈도우'를 이용해 길이를 구해야 한다. "abcabcbbc" 와 같은 문자열이 있다. (String s = "abcabcbbc")s의 0번째 인덱스인 a부터 2번째 인덱스 까지는 중복이 없다.이 범위는 left라는 포인터와 right라는 포인터의 범위를 조정해 left: 0, right: 2 의 값으로 길이를 구한다.3번째 인덱스 a를 순회할 때 '0번째 인덱스'에 'a'가 있다는 것을 알아야한다.중복 글자를 제외한 범위로 left를 조정하고 다시 조건에 해당하는 글자의 길이수를 계산한다.위 과정이 반복되는 중에 right 포인터..

LeetCode 24. Swap Nodes in Pairs, 페어의 노드 스왑

문제(링크):Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.) Example 1: Example 2:Input: head = [1,2,3,4]Output: [2,1,4,3] Example 3:Input: head = []Output: []  문제 풀이: 1 → 2 → 3 → 4 → 5 → 6 인 연결 리스트에서 3 → 4를 4 → 3 으로 바꾼다고 할 때, 그 앞 1 이 가리키는 node와 뒤의 노드 6으로 연결..

해시 테이블

해시 테이블(Hash Table) 또는 해시맵(Hash Map)은 키를 값에 매핑할 수 있는 구조이다.해시 테이블은 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1)이라는 점이다. 즉, 데이터의 양과 상관 없이 빠른 성능을 기대할 수 있다. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요 기법 중 하나다.  해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다.해시 함수는 다음과 같은 특징이 있다. 고정된 출력 크기: 입력 데이터의 크기와 상관없이 항상 고정된 크기의 해시 값을 출력한다.신속한 계산: 해시 값 계산이 빠르게 이루어진다.결정론적: 동일한 입력에 대해 항상 동일한 해시 값을 반환한다.충..

Quick Sort 구현

quick sort: 정렬 속도가 아주 빠르다는 데서 착안해 붙여진 직관적인 이름이다.퀵정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1개의 요소가 될때까지 반복한다.그룹을 나누는 기준을 피벗(pivot) 이라고 한다. 배열을 두 그룹으로 나누기 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 한다. 아래 배열을 통해 과정을 살펴보자.int[] arr = [5, 7, 1, 4, 6, 2, 3, 9, 8]// pl x pr가운데 인덱스를 피벗 x, 왼쪽 끝 요소를 pl, 오른쪽 끝 요소를 pr 이라 했을 때1. arr[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다. (pl+..