정글에서 온 개발자

계층 관계를 갖는 객체를 표현하기 위해 만들어진 자료구조 계층 관계가 없는 자료를 트리로 표현해서 같은 연산을 빠르게 할 수 있는 경우가 많다. 용어. 개념 정리 노드(node)와 간선(edge)로 이루어져 있다. 노드 간에는 상/하위 관계가 있다. 두 노드가 연결되었을 때는 한쪽이 상위, 다른쪽이 하위여야 한다. 상위는 부모(parent), 하위는 자식(child), 부모가 같은 노드는 형제(sibling) 부모와 부모들은 선조(ancestor), 자식과 그 자식들은 자손(descendant) 자식은 여러개 가질 수 있어도 부모는 하나만 가질 수 있다. 가장 윗쪽 노드는 **루트(**root;뿌리) 자식이 하나도 없는 노트는 리프(leaf;잎) 깊이(depth) :루트에서 어떤 노드에 도달하기 위해 거..

객체들의 상호 관계를 표현하기 위해 고안된 자료 구조 계층 관계만을 표현하는 트리에 비해 훨씬 다양한 현실 세계의 문제 표현 개요 그래프 표현 인접 행렬 표현 - 모든 정점의 관계를 표현. 밀집 그래프에서 유리 인접 리스트 표현 - 그래프 간 간선의 관계만 표현. 희소 그래프에서 유리 암시적 그래프 표현 ex) 좌표 표현 - 연결관계가 암시적(바로 옆의 좌표)으로 표현됨 문제가 비교적 단순한 경우 . 그래프 표현이 번거로워 사용 그래프가 아주 큰데, 일부만 사용(정점을 모두 그리지 않음) 단점. 그래프를 사용하는 알고리즘과 변환과정이 합쳐짐 → 코드가 복잡해짐 깊이 우선 탐색(DFS) 대표적 그래프 알고리즘. 재귀 사용 내부적으로 스택이 됨. 너비 우선 탐색(BFS) 가중치가 없는 그래프에서 두 점 사이..

현재 방법이 맥에서는 되고, 윈도우에서는 디버그 까지만 적용이 됩니다. 좀더 보완하겠습니다.ㅜㅜㅜ2023.10.14 - [정리] - 백준 문제 편하게 풀기지난번 포스팅에서 명령어를 통해 실행을 했다.(Redirection)그런데 그것도 귀찮아지기 시작했다.결정적으로는 디버깅할 때는 stdin redirection이 작동을 안했다.VSC 가 Hackable 하다는 걸 어디서 주워들었기 때문에, 이럴 때 쓰라고 있는 GPT한테 방법을 물어봤다.요약tasks.json 를 통해 빌드 명령을 실행할 수 있다.launch.json을 통해서 디버깅 환경을 설정할 수 있다.상세.vscode 폴더를 내가 작업하려는 디렉토리에 만들고, 그 안에 아래 두 파일을 넣는다.tasks.json{ "version": "2.0..

정렬 복습 화요 퀴즈를 봐야해서 빠르게 정렬을 복습했다. 2023.10.18 - [정리] - 주요 정렬 요약(8+2) 주요 정렬 요약(8+2) 나만의 언어로 암기해보기 버블 정렬: 이웃 교환의 연속 셰이커정렬 : 이웃교환을 위 아래 번갈아서 함 단순선택(선택 정렬) : 자리 정해서 한번에 새치기(원격 교환) 단순삽입(삽입 정렬) : 한명 krafton-jungle-essay.tistory.com 오픈 북이였는데도 퀵정렬 문제를 제대로 풀지 못한 걸로 봐서 아직 달달 외우진 못했다. 오늘 책을 보고 설명을 하는데, 피벗이 양쪽 끝에 있는 경우에도 설명이 막혔다. 다시 한 번 손으로 그려보면서 이해를 해야겠다. 면접과 구현에 관해 다시 한번, 가장 중요한 건 작동을 하는 코드다. 면접에서도 일단은 구현은 해..

나만의 언어로 암기해보기 버블 정렬: 이웃 교환의 연속 셰이커정렬 : 이웃교환을 위 아래 번갈아서 함 단순선택(선택 정렬) : 자리 정해서 한번에 새치기(원격 교환) 단순삽입(삽입 정렬) : 한명씩 새치기 이진 삽입정렬 셸 정렬: 징검다리 교환 퀵 정렬: 피벗을 기준 (원격)교환하며 분할 정복 병합 정렬: 반씩 쪼개서 분할 정복 힙 정렬: 힙으로 정렬해놓고 하나씩 꺼내며(다시 힙으로 만들면서) 정렬 도수 정렬: 누적도수 분포표를 인덱스로 사용하여 정렬 (비교 및 교환이 없음) 아래부터 각 정렬의 설명 버블(이웃 교환의 연속) - O(n^2) 맨 뒷쪽부터 상호 교환을 앞쪽 까지 함(한 패스) 패스를 n 번 반복함 (패스마다 교환이 n-1번씩 줄어듬) 개선 패스에서 교환이 안 일어나면 끝내기(break) 교..

책읽기: Introduction to Algorithms 40페이지까지 읽어보았다.문제풀기: 18번문제까지 풀었다. 외판원 순회 2 에러 푸느라 애먹었다. 베이스 케이스를 잘못 잡아서 고생했다.2023.10.17 - [정리] - 알고리즘과 자료구조의 정의타당하지 않은 알고리즘도 유용할 수 있다는 것을 다시 한번 상기됐다. 알고리즘과 자료구조의 정의알고리즘 어떤 값이나 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차 잘 정의된 계산 문제를 풀기 위한 도구 계산 문제를 정의하려면 입력과 출력의 관계를krafton-jungle-essay.tistory.com2023.10.17 - [정리] - 알고리즘의 분석어렴풋했던 내용을 정리하고 넘어갈 수 있었다. 알고리즘의 분석알고리즘을 ..

루프 불변성 점진적인 방법에서 활용 가능하다. For 나 While 등 루프를 돌아도 변하지 않는 조건 알고리즘이 타당한 이유를 쉽게 이해할 수 있게 사용된다. 세가지 특징이 있다. 초기조건 : 첫번째 반복을 시작하기 전에 루프 불변성이 참이여아한다. 유지조건: 다음 반복이 시작되기 전까지도 계속 참이여야 한다. 종료조건: 루프가 종료될 때 그 불변성이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 한다. 귀납법과 비슷하다. 베이스가 참임을 보임 귀납적 과정을 증명함 +. 마지막으로 알고리즘의 타당성을 보이는 것이 중요 정렬 알고리즘을 풀기로 했으면 루프 불변성이 마지막에 정렬된 수열을 나타내야 하는 것. 분할 정복 재귀적 구조를 가진 알고리즘 중 하나 세단계 분할: 현재 문제를 같은 문제..

알고리즘을 실행하는 데 필요한 자원을 예측하는 것을 의미한다. 대부분 그 자원은 시간이다. 알고리즘을 이용할 구현 기술의 모델을 정의하는 것이 좋음. (ex RAM 모델) RAM(random-access machine)모델 명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다. 명령어와 비용도 정확히 하는 것이 좋지만 지루함.(하려고 하지 말자) RAM 모델을 남용하기 보다는 실제 컴퓨터가 어떤 식으로 설계되어 있는지 참고하는 것이 좋음 RAM 의 명령어 - 상수 시간이 걸림 산술연산 ( 덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, 내림, 올림) 데이터 이동 연산 (읽기, 저장하기, 복사하기) 제어 연산 ( 조건 분기, 무조건 분기, 함수 호출, 리턴) 단, 워드 크기가 임의로 커지지 않는다는 조건 하에 ( ..

알고리즘 어떤 값이나 집합을 입력으로 받아 또 다른 값이나 값의 집합을 출력하는 잘 정의된 계산 절차 잘 정의된 계산 문제를 풀기 위한 도구 계산 문제를 정의하려면 입력과 출력의 관계를 잘 서술해야 한다. 어떤문제의 사례는 그 문제의 해를 계산하기 위해 필요한 입력으로 구성되며 문제의 정의에서 요구하는 입력에 대한 제약조건을 만족해야 한다. 알고리즘이 모든 입력 사례에 대해 항상 올바른 출력을 내고 종료할 경우 이를 타당(correct)하다고 한다. 타당한 알고리즘이 계산 문제를 푼다(solve)고 말한다. 타당하지 않은 알고리즘도 오류의 비율을 조절할 수 있으면 유용할 때가 있다. 알고리즘에 대한 지식과 기술을 얼마나 알차게 학습했느냐가 숙련된 프로그래머와 초보자를 구분하는 기준이 될 수 있다. 알고리..

2023.10.16 - [정리] - 소수 구하기의 여러가지 방법과 시간복잡도 비교 ChatGPT 덕분에 이쁜 그래프도 넣을 수 있었다. 소수 구하기의 여러가지 방법과 시간복잡도 비교 관련문제 백준 1978 소수 찾기 백준 9020 골드바흐의 추측 메모이제이션 메모이제이션 : 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계 krafton-jungle-essay.tistory.com 2023.10.16 - [정리] - 파이썬 ‘=’ 이 연산자가 아니다 논란과 주의할 점 왜 썸네일이 귀여운 바다코끼리인걸까? 읽어보면 알 수 있다. 파이썬 ‘=’ 이 연산자가 아니다 논란과 주의할 점 사실 논란의 여지가 없다. ‘=’ 은 연산자(operator)가 아니라 **..