Algorithm

[알고리즘] 시간 복잡도(Time Complexity)란? (Big-O 표기법)

1. 시간복잡도란? 시간 복잡도(Time Complexity)란 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것| 시간 복잡도란 크기 n의 모든 입력에 대해 걸리는 최대의 시간(최악의 경우) 명칭이 시간 복잡도라 헷갈릴 수 있지만 시간 복잡도는 시간 개념이 아니라 알고리즘이 실행될 때 동작하는 모든 연산의 횟수가 몇번인지 세는 것 알고리즘의 성능 평가 유형엔 최선, 평균, 최악이 있는데, 이 중 최악의 경우로 알고리즘의 성능을 평가한다. 그 이유는 알고리즘이 복잡해질 수록 평균 성능을 구하기 어렵기도 하며, 나머지 경우 모두 최악의 경우보다는 빠르므로 최악의 경우가 앞선 두 경우를 모두 포함할 수 있기 때문이다. 2. Big-O Notation(Big-O 표기법) B..

[기본 정렬 알고리즘] 3. 삽입 정렬(Insertion Sort)이란

1. 정렬 알고리즘이란? 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 그렇다면 왜 정렬 알고리즘을 사용해 데이터를 열거할까? 이유는 탐색하기 위해서다. 컴퓨터는 수 많은 데이터를 처리해야하는데 만약 데이터를 정렬하지 않는다면 데이터를 하나하나 일일이 탐색(순차 탐색)하여 원하는 데이터를 탐색해야 한다. 일반적으로 데이터를 삭제/삽입하기보다 탐색/조회하는 경우가 많기 때문에 매번 데이터를 탐색할 때마다 이런 식의 탐색은 매우 비효율적이다. 하지만 데이터가 일정한 규칙에 따라 순서대로 열거되었다면 다양한 탐색 방법을 이용하여 원하는 데이터를 빠르고 효율적으로 탐색할 수 있다. 2. 삽입 정렬(Insertion Sort)이란? - 삽입 정렬이란 자료 배열/리스..

[기본 정렬 알고리즘] 2. 버블 정렬(Bubble Sort)이란

1. 정렬 알고리즘이란? 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 그렇다면 왜 정렬 알고리즘을 사용해 데이터를 열거할까? 이유는 탐색하기 위해서다. 컴퓨터는 수 많은 데이터를 처리해야하는데 만약 데이터를 정렬하지 않는다면 데이터를 하나하나 일일이 탐색(순차 탐색)하여 원하는 데이터를 탐색해야 한다. 일반적으로 데이터를 삭제/삽입하기보다 탐색/조회하는 경우가 많기 때문에 매번 데이터를 탐색할 때마다 이런 식의 탐색은 매우 비효율적이다. 하지만 데이터가 일정한 규칙에 따라 순서대로 열거되었다면 다양한 탐색 방법을 이용하여 원하는 데이터를 빠르고 효율적으로 탐색할 수 있다. 2. 버블 정렬(Bubble Sort)이란? - 버블 정렬이란 서로 인접한 두 원소..

[기본 정렬 알고리즘] 1. 선택 정렬(Selection Sort)이란

1. 정렬 알고리즘이란? 정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. 그렇다면 왜 정렬 알고리즘을 사용해 데이터를 열거할까? 이유는 탐색하기 위해서다. 컴퓨터는 수 많은 데이터를 처리해야하는데 만약 데이터를 정렬하지 않는다면 데이터를 하나하나 일일이 탐색(순차 탐색)하여 원하는 데이터를 탐색해야 한다. 일반적으로 데이터를 삭제/삽입하기보다 탐색/조회하는 경우가 많기 때문에 매번 데이터를 탐색할 때마다 이런 식의 탐색은 매우 비효율적이다. 하지만 데이터가 일정한 규칙에 따라 순서대로 열거되었다면 다양한 탐색 방법을 이용하여 원하는 데이터를 빠르고 효율적으로 탐색할 수 있다. 2. 선택 정렬(Selection Sort)이란? - 선택 정렬이란 배열/리스트에서..

[JAVA] 프로그래머스 위장(Hash Lv.2)

1 . 문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. c..

[JAVA] 프로그래머스 전화번호 목록 (Hash Lv.2)

1 . 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. 입출력 예..

[JAVA] 프로그래머스 완주하지 못한 선수 (Hash Lv.1)

1 . 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participant completion return ["leo", ..

[JAVA] 해시맵(HASH MAP)

1. HashMap이란? : Map 인터페이스를 구현한 대표적인 컬렉션 클래스다. 시간복잡도는 O(1). 1 -1. HashTable vs HashMap : HashTable은 쉽게 말해 Old 버전. HashMap은 새로운 버전. - 공통점 : HashTable 과 HashMap은 모두 Map 인터페이스를 구현했으며, 데이터를 키와 값의 쌍으로 저장한다(key, value). 또한 저장 순서를 유지하지 않는다. 키는 중복을 허용하지않지만 값은 중복을 허용한다. - 차이점 : 동기화의 유무. HashTable은 동기화가 되어있으나, HashMap은 동기화가 되어있지 않다. 1-2. HashMap 과 LinkedHashMap : HashMap은 저장 순서를 유지하지 않는다. 하지만 저장 순서를 유지해야하는..