jc.jang

Binary_Search by JichangJang, https://github.com/jangjichang 개념 정렬된 데이터들의 배열에서 특정한 값의 위치를 찾는 알고리즘입니다. 절차는 다음과 같습니다. 배열 중간에 있는 요소를 대상 값과 비교합니다. 대상 값이 요소와 일치하면 요소의 위치(인덱스)를 반환합니다. 대상 값이 요소보다 작으면 배열의 아래쪽 절반에서 1번 단계를 시작합니다. 대상 값이 요소보다 크면 배열의 위쪽 절반에서 1번 단계를 시작합니다. 더 이상 비교할 요소가 없으면 대상 값은 배열에 존재하지 않습니다. 연산 정렬된 배열에서 대상 값을 찾는 연산이 있습니다. 시간 복잡도는 아래와 같습니다. Best Worst Avg 시간 복잡도 O(1) O(logn) O(logn) 최선의 경우 배..

그림과 같이 쇠막대기와 레이저(점선)이 주어질 때, 잘린 쇠막대기 조각의 총 개수를 구하는 문제이다. 문제를 보자마자 드는 생각 -> 모든 막대기에 대해 몇 개의 레이저가 발사되는지 세어서 총 몇 조각이 되는지 합한다. 결과 -> 정답은 맞았지만 시간 복잡도에서 통과하지못함. 모든 막대기의 시작과 끝 인덱스를 저장하는데 O(n) + 모든 막대기들의 시작과 끝 인덱스 사이에 레이저가 있는지 확인하는데 O(nlogn) 시간이 걸린다. (n은 입력된 문자열의 길이) 스택을 이용한 풀이법 -> 문자열을 순회하며 막대기의 시작점인 경우 스택에 추가하고 레이저인 경우 스택의 원소 만큼 쇠막대기 조각의 수를 더한다. 쇠막대기의 끝점인 경우 쇠막대기 조각에 +1을 한다. 결과 -> O(n)시간에 코드 실행.

10/24 - 6장 big-O 예제 풀이 10/25 - 6장 big-O 추가 문제 풀이 11/03 - 7장 실전 문제 살펴보기 11/06 - 7장 최적화 및 문제 풀이 기술 #1 BUD 찾기 11/14 - 7, 8장 기술적 문제, 합격한 뒤에 11/15 - 9장 면접 문제 (자료구조) 11/21 - 9장 면접 문제 예제 1.6까지 (파이썬으로 해시 구현해야 함)

주제 알고리즘의 효율성을 나타내는 지표에 대해 알아보자. 노트 big O에 대해 학습하고 예제를 풀던 중 좋은 예제라고 생각되어 정리하려고 한다. 여러 개의 문자열로 구성된 배열이 주어졌을 때 각각의 문자열을 먼저 정렬하고 그다음에 전체 문자열을 사전 순으로 다시 정렬하는 알고리즘이 있다고 가정하자. 이 알고리즘의 수행 시간은 어떻게 되겠는가? 이 big O에 대한 개념이나 쉬운 예제들을 이해하는데 큰 어려움은 없었다. 하지만 이 문제는 일종의 버릇처럼 대답하던 나의 답변을 고쳐준 좋은 예제였다. 시간 복잡도를 표현할 때 N을 사용하기보다는 의도가 드러나도록 변수명을 설정하라. 가장 길이가 긴 문자열의 길이를 s라 하자. 배열의 길이를 a라 하자. 이제 알고리즘의 시간 복잡도에 대해 알아보자. 하나의 문..

알고리즘 스터디 1주차 스택, 큐 Intro Oct 15, 2019 장지창 안녕하세요. 프로그라피 5기 Django팀 장지창입니다. 오늘은 알고리즘 스터디 1주차에 진행한 스택, 큐에 대해 알아보겠습니다. 저희는 매주 두개의 자료구조 주제를 선정하여 관련 문제를 풉니다. 그리고 오프라인에서 개념 강의를 제공하는 방식으로 스터디가 진행되고 있습니다. 지금부터 아래에서 언급하는 내용은 제가 알고리즘 스터디를 준비하면서 스택, 큐에 대해 알아본 내용입니다. 혹시나 틀린 부분이 있거나 다른 생각이 있으시다면 댓글이나 이메일을 통해 서로 의견을 공유할 수 있으면 좋을 것 같습니다. 개념 설명 저번 글에 이어서 큐를 소개하겠습니다. 큐는 스택과 반대로 FIFO(First In First Out)순서를 따르는 선형 ..

알고리즘 스터디 1주차 스택 Intro Oct 15, 2019 장지창 안녕하세요. 프로그라피 5기 Django팀 장지창입니다. 오늘은 알고리즘 스터디 1주차에 진행한 스택, 큐에 대해 알아보겠습니다. 저희는 매주 두 개의 자료구조 주제를 선정하여 관련 문제를 풉니다. 그리고 오프라인에서 개념 강의를 제공하는 방식으로 스터디가 진행되고 있습니다. 지금부터 아래에서 언급하는 내용은 제가 알고리즘 스터디를 준비하면서 스택, 큐에 대해 알아본 내용입니다. 혹시나 틀린 부분이 있거나 다른 생각이 있으시다면 댓글이나 이메일을 통해 서로 의견을 공유할 수 있으면 좋을 것 같습니다. 개념 설명 먼저, 스택입니다. 스택은 LIFO(Last In First Out) 순서를 따르는 선형 데이터 구조입니다. 스택의 모든 삭제..