지난 챕터에는 divide and conquer에 대해 다루어 보았다. 이번 챕터에서는 그 중에서도 퀵정렬에 대한 내용을 다루어 볼 예정이다. 목차는 다음과 같다. Quicksort? divide and conquer에 대한 내용은 아래 링크에 작성하였다! https://wanna-developer02.tistory.com/46 [알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort 이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 wanna-developer02.tist..

이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 배운 알고리즘이다. 그만큼 기초적인 부분이라고 할 수 있다. 분할정복이란 하나의 문제를 작은 여러개의 문제로 쪼갠 후 재귀적으로 각 문제를 해결한 후 이를 다시 합쳐 원래 문제를 해결하는 방법이다. 이에 대한 접근은 다음과 같이 할 수 있다. STEP 1) Divide 답을 얻을 수 있을 때까지 한 문제를 2개 이상의 작은 문제로 나눈다. STEP 2) Conquer 길이가 충분히 짧아지면 답을 바로 구할 수 있다. STEP 3) Combine 작은 문제를 해결..

2학기가 끝난 기념(?)으로 가장 중요한 과목이었던 알고리즘을 정리해보려고 한다. 더 미뤄서 머리에서 사라지기 전에..!자료구조랑 겹치는 부분은 최대한 배제하겠지만 어느정도의 교집합은 어쩔 수 없는 거 같다. 그럼 시작-! 이번 챕터에서는 첫 주에 배웠던 order function을 정리해 볼 예정이다. 1. order function의 종류우리는 알고리즘의 time complexity, 즉 시간복잡도를 함수를 이용해 표현한다. 사용하는 함수는 크게 7가지이다. lg n n (linear) n lg n n^2 (quadratic) n^3 (cubic) 2^n (exponential) n! (combinatorial)세로선을 그었을 때 그래프와의 교점이 아래에 있을수록 시간이 짧게 걸리는 함수라고 할 수 ..

프로그래머스 _ 코딩 기초 트레이닝 DAY 22 - (2) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181846 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 0 이상의 두 정수가 문자열 a, b로 주어질 때, a + b의 값을 문자열로 return 하는 solution 함수를 작성해 주세요. (1 풀이

프로그래머스 _ 코딩 기초 트레이닝 DAY 21 - (2) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181851 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 0번부터 n - 1번까지 n명의 학생 중 3명을 선발하는 전국 대회 선발 고사를 보았습니다. 등수가 높은 3명을 선발해야 하지만, 개인 사정으로 전국 대회에 참여하지 못하는 학생들이 있어 참여가 가능한 학생 중 등수가 높은 3명을 선발하기로 했습니다. 각 학생들의 선발 고사 등수를 담은 정수 배열 rank와 전국 대회 ..

프로그래머스 _ 코딩 기초 트레이닝 DAY 21 - (1) 출처 -https://school.programmers.co.kr/learn/courses/30/lessons/181852 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 정수로 이루어진 리스트 num_list가 주어집니다. num_list에서 가장 작은 5개의 수를 제외한 수들을 오름차순으로 담은 리스트를 return하도록 solution 함수를 완성해주세요. 입력 #1 | [12, 4, 15, 46, 38, 1, 14, 56, 32, 10] 출력 #1 | [15, 32, 38, 46, ..

프로그래머스 _ 코딩 기초 트레이닝 DAY 19 - (5) 출처 -https://school.programmers.co.kr/learn/courses/30/lessons/181858 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 랜덤으로 서로 다른 k개의 수를 저장한 배열을 만드려고 합니다. 적절한 방법이 떠오르지 않기 때문에 일정한 범위 내에서 무작위로 수를 뽑은 후, 지금까지 나온적이 없는 수이면 배열 맨 뒤에 추가하는 방식으로 만들기로 합니다.이미 어떤 수가 무작위로 주어질지 알고 있다고 가정하고, 실제 만들어질 길이 k의 배열을 예상해봅시..

프로그래머스 _ 코딩 기초 트레이닝 DAY 19 - (3) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 아무 원소도 들어있지 않은 빈 배열 X가 있습니다. 길이가 같은 정수 배열 arr과 boolean 배열 flag가 매개변수로 주어질 때, flag를 차례대로 순회하며 flag[i]가 true라면 X의 뒤에 arr[i]를 arr[i] × 2 번 추가하고, flag[i]가 false라면 X에서 마지막 arr[i]개의 원소를..

프로그래머스 _ 코딩 기초 트레이닝 DAY 18 - (4) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181864 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 문자 "A"와 "B"로 이루어진 문자열 myString과 pat가 주어집니다. myString의 "A"를 "B"로, "B"를 "A"로 바꾼 문자열의 연속하는 부분 문자열 중 pat이 있으면 1을 아니면 0을 return 하는 solution 함수를 완성하세요. 입력 #1 | myString = "ABBAA" / pat ..

이번 챕터에서는 트리 중 가장 대표적인 binary tree (이진 트리)를 기록할 예정이다. 순서는 다음과 같다. binary tree - binary tree의 정의와 종류 - binary tree의 ADT - binary tree를 linked list로 나타내면? binary tree traversal - tree algorithm 종류 1. Binary Tree 1-1. Binary Tree 정의와 종류 Binary Tree는 각 노드가 최대 2개의 자식노드만 갖는 트리를 의미하며, 정확히 2개만 갖는 트리는 proper binary tree라고 부른다. 참고로 트리의 종류를정짓는 요소는 크게 2가지로 structural property, relational property가 있다. struct..