프로그래밍/알고리즘
-
TestDome 에서 코딩테스트를 ???프로그래밍/알고리즘 2020. 7. 13. 13:11
TestDome 은 뭐하는 곳인가... 간단하게 말하면 우리나라에서 자주 사용하는 프로그래머스, 백준 사이트와 굉장히 유사하다고 보시면 됩니다. 기업에서 직원들을 채용할 때, 코딩 테스트를 보기 위해 이용하는 사이트인 거죠. 보통 외국계 기업, 스타트업 등에서 종종 사용하고 특히 리눅스 환경에서 개발을 하는 회사에서 사용하는 것 같습니다. 프로그래머스와 다른 점이 있나 ? 우선 문제 유형이 좀 다릅니다. 프로그래머스와 백준 사이트의 경우 보통 BFS, DFS, BRUTE FORCE 등의 알고리즘 문제들이 나옵니다. 하지만 TestDome을 통해 입사시험도 보고 무료로 제공되는 테스트들을 몇 가지 해봤을 때, 자료구조의 구현 문제가 대부분이었습니다. 그리고 정말 쉬운 문제로는 이 개발언어를 사용할 줄 아는..
-
[알고리즘] 2차원 버블 정렬(Bubble sort)프로그래밍/알고리즘 2019. 10. 22. 23:36
List 1. 1차원 버블정렬을 이해한다. 2. 주어진 변수를 통해 2차원 버블정렬을 만든다. 2차원 버블정렬(Bubble sort) 버블정렬을 간단하게 설명하자면 오름차순 기준으로 오른쪽에 있는 값과 비교하여 큰값을 오른쪽 끝으로 보내는 과정을 N번 반복하는 것입니다. 1차원 설계는 링크를 통해 들어가시면 확인하실 수 있습니다. 지금부터 2차원 버블정렬을 설계 해봅시다. 2019/03/27 - [프로그래밍/알고리즘] - [알고리즘] 버블정렬(Bubble sort) [알고리즘] 버블정렬(Bubble sort) 알고리즘 버블정렬(Bubble sort) 간단 요약 가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다. 특징) 선택정렬은 앞에서 부터 작은수를 정렬시키지만 버블정..
-
[알고리즘] 동적 계획법(Dynamic Programming)프로그래밍/알고리즘 2019. 6. 7. 23:56
List 1. 동적 계획법(Dynamic Programming) 이란? 2. 피보나치수열 구현 3. 메모이제이션(memoization) 동적 계획법(Dynamic Programming) 이 알고리즘은 다이나믹 프로그래밍 또는 DP라고 많이 불립니다. 이전에 배웠던 알고리즘과 차이가 있다면 큐(queue) , 스택(stack)처럼 특정 자료구조를 사용해야 하는 고정적인 개념이 아니라는 겁니다. 이름의 프로그래밍(Programming) 이란 단어가 의미하는 것은 컴퓨터 언어로 코딩을 하는 것을 말하는 것이 아니라 "계획하다"의 의미를 갖고 있습니다. 따라서 이 알고리즘은 특정 문제들을 특수한 형태로 계획해서 풀어나가야 할 때 사용됩니다. 동적 계획법은 대회나 SW 역량테스트 등의 등장 빈도가 아주 높고 기본..
-
[알고리즘] 집합 찾기(Union Find)프로그래밍/알고리즘 2019. 6. 5. 20:17
List 1. 연결 리스트를 이용한 집합 찾기 2. 배열을 이용한 집합 찾기 3. 트리를 이용한 집합 찾기 4. 연산의 효율을 높이는 법 ※ 코드구현은 생략 연결 리스트를 이용한 집합 찾기 연결리스트를 이용한 표현에서 집합의 원소는 노드로 표현이 됩니다. 각 노드에는 원소를 저장하는 필드, 다음 원소와 대표 원소를 기리키는 두 개의 포인터가 있습니다. 다음 원소를 가리키는 포인터를 통해 집합의 모든 원소들이 연결됩니다. 여기서 대표 원소는 각 집합의 가장 앞에 있는 원소를 의미합니다. 그리고 각 집합에는 마지막 원소를 가리키는 tail 변수 라는것이 존재합니다. 이 변수는 두 집합을 합칠 때 이용됩니다. 하나의 원소 x 만을 갖고 있는 집합이 있다고 가정해봅시다. 연결 리스트의 한 노드의 구성은 오른쪽 ..
-
[알고리즘] 탐욕적 기법(Greedy Algorithm)프로그래밍/알고리즘 2019. 5. 29. 16:02
Goal 1. 탐욕적 기법(Greedy Algorithm)의 개념 2. 탐욕적 기법(Greedy Algorithm)의 특징 3. 탐욕적 기법(Greedy Algorithm)의 구현 서론 가장 유명하지만 가장 기초적이어서, 알고리즘에 입문하기 가장 좋은 녀석입니다. 접근법이 굉장히 직관적이고 단순하기 때문에 알고리즘 대회, 코딩 테스트에서 적지 않게 볼 수 있습니다. 그래서 저는 그리디 알고리즘 문제를 적어도 10 문제 정도는 풀어보고 다른 알고리즘을 풀어보시는 걸 추천드립니다. 왜냐하면 10문제 정도 풀어보시면, 내가 생각하는 것을 코드로 구현하는 능력과 문제를 직관적으로 보는 능력이 생기기 때문입니다. 개념 서론이 길었습니다. 탐욕적 기법(Greedy Algorithm), 욕심쟁이 기법 혹은 그냥 그리..
-
[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)프로그래밍/알고리즘 2019. 5. 26. 15:45
Goal 너비 우선 탐색(BFS, Breadth-First Search)의 개념 너비 우선 탐색(BFS, Breadth-First Search)의 특징 너비 우선 탐색(BFS, Breadth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 너비 우선 탐색(BFS, Breadth-First Search) 너비 우선 탐색은 시..
-
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)프로그래밍/알고리즘 2019. 5. 23. 11:51
Goal 깊이 우선 탐색(DFS, Depth-First Search)의 개념 깊이 우선 탐색(DFS, Depth-First Search)의 특징 깊이 우선 탐색(DFS, Depth-First Search)의 구현 그래프 탐색이란? 그래프 탐색은 그래프의 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것입니다. 그래프의 탐색은 매우 중요합니다. 대부분의 문제들이 탐색하는 것 만으로 해결되기 때문입니다. 예를 들어 다리 문제에서 A 도시와 B 도시가 연결돼있는지 확인하는 것은 단지 탐색을 하였을 때, A, B 도시가 한 연결 요소 안에 존재하는지만 판단하면 됩니다. 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색은 미로를 탐색하는 ..
-
[알고리즘] 해시 테이블 (Hash Table)프로그래밍/알고리즘 2019. 4. 30. 10:38
개념 Hash Function : 해시 함수는 임의의 길이의 문자열을 받아서 고정 문자열로 바꾸어주는 함수이다. 이 때 함수를 구현하는 방법에 따라서 해당 서로 다른 임의의 문자열이 같은 고정 문자열로 되기도 하며 이러한 부분을 충돌이라고 한다.(H(s1) = H(s2)) 아래 사진의 경우에는 좌측에 파란 색들이 key이며 각 key값들이 해시 함수의 결과를 오른쪽 우측에 숫자로 바뀌었음을 보여준다. 나중에 해시 테이블에서는 이 key을 해시한 결과를 배열의 인덱스로 사용한다. 해시 함수를 H()라고 했을 때 H(Jonh Smith) = 02 해시 충돌(Hash Collision) 서로 다른 문자열을 해시한 결과가 동일한 경우 해시 함수를 H()라고 했을 때 서로 다른 문자열 s1과 s2에 대해서 H(s..