AVL Tree ratsgo's blog의 AVL Tree 를 참고하여 작성하였습니다. 이진탐색트리(Binary Search Tree)의 일종 이진탐색트리의 탐색 시간복잡도 : 𝑂(ℎ), h : 트리의 높이 서브트리의 높이를 조절해서 전체 트리가 한쪽으로 늘어지지 않도록 하는 것이 핵심 균형된 트리를 만들어 ℎ를 줄입니다. 기본적으로 삽입(insert) / 삭제(delete) 연산은 일반적인 BST과 동일합니다. 다만, 연산 이후 Balance Factor(BF) 값에 따라 서브트리를 재구성해 트리 전체의 균형을 맞춥니다 (Rebalance). Balance Factor(BF) : 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값 두 서브트리의 높이가 같거나 잎새노드라면 BF = 0 (em..

BeautifulSoup 데이터를 추출하는데 필요한 기능이 들어 있는 파싱(parsing)라이브러리 웹 스크래핑에 활용할 수 있습니다. 파싱 : 받아온 데이터에서 필요한 내용만 추출하는 것 스크래핑(scraping) : 컴퓨터 프로그램이 다른 프로그램으로부터 들어오는 인간이 읽을 수 있는 출력으로부터 데이터를 추출하는 기법 예제를 통해 이해하는 것이 빠를 것 같습니다. Ex import requests from bs4 import BeautifulSoup # url을 정의하고 requests library를 이용하여 get 요청 > html 값을 text로 받아옵니다. url = "https://finance.naver.com/sise/" response = requests.get(url).text # ..

[Django] Test driven development, TDD 테스트 주도 개발은 무언가를 개발할 때 바로 개발부터 하는 것이 아니라 개발하려는 항목에 대한 점검 사항을 테스트코드로 만들고 그 테스트를 통과시키는 방식으로 개발을 진행하는 방법입니다. 프로그램이 복잡해 질수록 추가한 기능 사이에 상호 연관성이 점점 늘어납니다. 나중에는 개발한 내용을 확인하는 과정을 건너뛰는 지경에 이를 수도 있죠. 그렇게 쌓이다 보면 문제가 발생했을 때 어디서부터 찾아야할지 막막해질 수 있습니다. 개발을 한 단계씩 진행할 때마다 테스트를 하면 이런 상황을 막을 수 있습니다. 테스트 주도 개발은 개발한 코드가 테스트를 만족하는지 자동으로 확인하면서 개발할 수 있도록 하는 방법입니다. 테스트 코드 작성 : 만들고 싶은 ..

백준11404번 플로이드 2021.06.20 플로이드 Solution 플로이드 알고리즘으로 해결하였습니다. input start, end 로 2차원 배열(input_map) 에 cost 저장 노선이 여러개일 경우 짧은 것으로 갱신 floyd 알고리즘으로 모든 최단 경로 찾기 결과가 inf 인 경우, 경로가 없는 것이므로 0으로 수정 (문제 조건) Source # 2021.06.20 inf = int(1e9) def floyd(input_map, V): for i in range(V): input_map[i][i] = 0 for k in range(V): for i in range(V): for j in range(V): input_map[i][j] = min(input_map[i][j], input_ma..

백준18353번 병사 배치하기 2021.06.16 병사배치하기 Solution LIS (Longest Increasing Sequence) 를 내림차순으로 변형하여 풀이하였습니다. 0 ~ N-1 을 돌며 DP[N]을 구합니다. (n) DP[N] = DP[N-i] + 1 (i = 0 ~ n-1) N-i번보다 N번이 작으면 N-i번 오른쪽에 N번이 위치할 수 있고, 이렇게 했을 때 N-i번의 최대 길이에 +1 한 것이 N번의 최대길이 후보가 됩니다. 0 ~ n-1 을 돌며 왼쪽 부분수열 중 n번이 오른쪽에 놓일 수 있는 후보를 고릅니다. +1 한 값과 비교해 DP[n]을 업데이트합니다. DP[N] 중 최댓값을 N에서 뺀 값이 정답입니다. Source # 2021.06.16 병사배치하기 # Solution :..

웹서비스 사용자(클라이언트)가 서버 에 접속하여 요청을 보내고 제공받는 서비스입니다. 클라이언트가 특정 url 에 접속하여 서버에 요청을 보냅니다. 서버는 해당 요청에 알맞는 정보(html 파일 등)을 보냅니다. 클라이언트는 전달받은 정보를 렌더링하여 출력합니다. Front-End / Back-End Front-End 웹브라우저에서 특정 주소를 가진 서버 컴퓨터에 요청을 보내면 서버에서 제공하는 웹사이트가 제공됩니다. (ex. html파일을 받아 렌더링해서 화면에 보여줍니다.) 예를들어, a 태그를 가진 영역을 클릭하면 웹 브라우저는 다시 해당 주소를 가진 서버에 html 파일을 요청하고, 서버에서 받아 렌더링해서 보여줍니다. 이처럼 보여주는 화면이 Front-End입니다. 여기에 사용되는 프로그래밍 언..

[Python] 객체지향프로그래밍 - OOP (Object Orientated Programming) Object Orientated Programming in Python https://www.youtube.com/watch?v=JeznW_7DlB0 를 참고하여 작성하였습니다. 모든 Python의 구현은 Class의 Instance인 Object로 이루어집니다. 오버로딩 / 오버라이딩 오버로딩 : 한 클래스 내에 이미 사용하려는 이름과 같은 이름을 가진 메소드가 있더라도 매개 변수의 개수나 타입이 다르면 다르게 정의되는 것을 의미합니다. 오버라이딩 : 상속관계에 있는 부모클래스에서 이미 정의된 메소드를 자식클래스에서 같은 시그니쳐를 갖는 메소드로 재정의하는 것을 의미합니다. 특수한 메서드 파이썬에는 내..

Binary Search Tree 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조입니다. 코드 전체를 보시려면 이곳 을 참고하세요. 이진탐색의 장단점 : 탐색 시간복잡도는 𝑂(log𝑛)으로 빠르지만 자료 입력, 삭제가 불가능 연결리스트의 장단점 : 자료 입력, 삭제 시간복잡도는 𝑂(1)로 효율적이지만 탐색은 𝑂(𝑛)의 시간복잡도가 소요되어 비효율적 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게 만들어진 자료구조입니다. 특징 중복된 값을 가진 노드는 없습니다. 각 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값을 지닌 노드들로만 이루어집니다. 각 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값을 지닌 노드들로만 이루어집니다..

2021.06.12 정수삼각형 Solution DFS : 삼각형의 꼭대기에서부터 아래 or 오른쪽아래로 깊이우선탐색을 합니다. DFS로 탐색을 구현할 때 리턴하는 값은 다음과 같이 설정할 수 있습니다. 맨 아래인 경우 : 해당 노드의 값 맨 아래가 아닌 경우 : 해당 노드의 값 = 그 다음노드부터 맨 아래까지의 최대경로 이렇게 설정하면 결국 재귀로 구현한 깊이우선탐색의 최종 반환 값이 원하는 결과가 됩니다. DP : 위의 DFS에서 각 노드를 탐색할 때, 이미 탐색한 적이 있는 경우 메모이제이션 을 활용할 수 있습니다. 해당 노드부터 맨 아래까지의 경로 중 최댓값을 DP 배열에 저장하고, 이미 탐색한 적이 있는 경우 (DP 배열이 초기값이 아닌경우) 에는 메모이제이션 해둔 값을 반환하도록 합니다. Sou..

2021.06.12 퇴사 Solution DFS : 특정 일자에 상담이 가능한지 그 뒤(다음 깊이탐색)로 상담이 가능한지를 재귀적으로 깊이우선탐색합니다. 재귀함수는 다음과 같이 구현할 수 있습니다. 기저조건 : N+1일째 이상을 탐색할 경우 퇴사이므로 0을 리턴합니다. 재귀함수 정의 : 특정 날짜를 입력받아 퇴사할때까지 상담으로 받을 수 있는 금액의 최댓값을 반환하는 함수 해당 날짜의 고객을 상담할 수 있는지 확인합니다. 상담할 수 있다면 금액을 초기값으로 설정하고, 다음 탐색할 노드들을 탐색하고 그 중 최댓값을 더해 반환합니다. DP : 특정 날짜에부터 퇴사일까지 받을 수 있는 최댓값을 메모이제이션합니다. 재귀함수에서 DP에 기록이 되어있다면 반환하도록 하여, 중복된 탐색을 제거할 수 있습니다. Sou..