기록하고 싶은 것들

가상머신이란?하드웨어를 소프트웨어적으로 구현 & 그 위에서 OS를 작동하게 하는 기술 사용 이유는?다른 OS를 사용할 경우 독립작업공간 필요, 하나의 머신에서 여러명에게 운영체제 환경 제공 VirtualBox오라클 - 가상머신 솔루션 Uploaded by Notion2Tistory v1.1.0

포트폴리오 정보 https://youtu.be/KJUdqPDAtTI 드림코딩 참고 1. 프로젝트로 공부해나가야 하는지 실용적인 방법 배울 수 있음, 결과를 눈으로 볼 수 있음 당장 낼 수 있는 무언가를 가지게 됨 문제 해결 능력 (문제를 해결하는 연습 해나가기) 2. 포트폴리오를 어떻게 만들어 나가면 좋은지 html + css: 정적인 반응형 웹사이트 js: 동적인 웹사이트(서버에서 데이터를 받아옴),+ node js를 이용해서 백엔드 구축 프레임워크를 이용한 spa 만들기 (ex react 라이브러리) 히든카드 1.중요한 기술/스택을 1-2개에 초점 2.독창적인, 창의적인 아이디어 3.자주 쓰는 앱들의 주요 기능 카피 (ex 채팅app 만들어보기, 날씨 보여주기 app, 간단한 게임) 개발자의 중요한 ..

최소 공통 조상: 기초 문제BOJ ‘LCA’ 문제 최소 공통 조상최소 공통 조상 문제는 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제 기본적인 최소 공통 조상 알고리즘모든 노드에 대한 깊이를 계산최소 공통 조상을 찾을 두 노드 확인 먼저 두 노드의 깊이가 동일하도록 거슬러 올라가기이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라가기모든 LCA(a,b) 연산에 대하여 2번의 과정 반복 LCA 알고리즘import sys sys.setrecursionlimit(int(1e5)) # 런타임 오류를 피하기 위한 재귀 깊이 제한 설정 n = int(input()) parent = [0] * (n + 1) # 부모 노드 정보 d = [0] * (n + 1) # 각 노드까지의 ..

데이터가 업데이트가 가능한 상황에서의 구간 합 문제BOJ 구간 합 구하기 문제 바이너리 인덱스 트리(Binary Indexed Tree)바이너리 인덱스 트리는 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결할 수 있는 자료구조펜윅 트리(fenwick tree)라고도 함 0이 아닌 마지막 비트를 찾는 방법특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해서 K&-K를 계산하면 됌 b = 8 for i in range(n+1): print(i, "의 마지막 비트:", (i & -i)) 바이너리 인덱스 트리: 트리 구조 만들기트리 구조 만들기: 0이 아닌 마지막 비트 = 내가 저장하고 있는 값들의 개수 바이너리 인덱스 트리: 업데이트(Update)특정 값을 변경할 때: 0이 아닌 마지막 비트만큼..

음수 간선이 포함된 상황에서의 최단 거리 문제 BOJ ‘타임머신’문제음수 간선이 순환이 포함된다면 최단 거리가 음의 무한인 노드 발생 벨만 포드 최단 경로 알고리즘음수 간선에 관하여 최단 경로 문제는 다음과 같이 분류1) 모든 간선이 양수인 경우2) 음수 간선이 있는 경우1) 음수 간선 순환은 없는 경우2) 음수 간선 순환이 있는 경우벨만 포드 최단 경로 알고리즘은 음의 간선이 포함된 상황에서도 사용또한 음수 간선의 순환을 감지 가능벨만 포드의 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느림 동작 원리출발 노드 설정최단 거리 테이블 초기화다음의 과정을 N-1번 반복전체 간선 E개를 하나씩 확인각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신만약 음수 간선 순환이 발..

트리트리는 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조[트리 관련 용어]루트 노드: 부모가 없는 최상위 노드단말 노드: 자식이 없는 노드크기: 트리에 포함된 모든 노드의 개수깊이: 루트 노드부터의 거리높이: 깊이 중 최대값차수: 각 노드의 간선 개수기본적으로 트리의 크기가 N일 때, 전체 간선의 개수 N-1개 이진 탐색 트리(Binary Search Tree)이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조 일종이진 탐색 트리의 특징: 왼쪽 자식 노드< 부모 노드 < 오른쪽 자식 노드부모 노드보다 왼쪽 자식 노드가 작음부모 노드보다 오른쪽 자식 노드가 큼 트리의 순회(Tree Traversal)트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법을..

우선순위 큐우선순위 큐는 데이터를 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우자료구조추출되는 데이터스택가장 나중에 삽입 데이터큐가장 먼저 삽입 데이터우선순위 큐가장 우선순위가 높은 데이터우선순위 큐를 구현하는 방법1) 단순히 리스트를 이용하여 구현2) 힙(heap)을 이용하여 구현데이터의 개수가 N일때, 구현 방식에 따라서 시간 복잡도를 비교한 내용우선순위 큐 구현 방식삽입 시간삭제 시간리스트O(1)O(N)힙(Heap)O(logN)O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬)이 경우 시간 복잡도..

개발형 코딩 테스트정해진 목적에 따라서 동작하는 완성된 프로그램 개발을 요구하는 코딩 테스트 유형일부 기업은 해커톤을 통해 채용 진행해커톤이란 단기간에 아이디어를 제품화하는 프로젝트 이벤트대개 1-2일 진행, 대회 형식을 빌려 해커톤이 끝나면 만든 프로그램을 시연하고 발표한 다음 채점 진행 개발형 코딩 테스트는 분야에 따라 상세 요구사항이 다를 수 있음하지만 분야에 상관없이 꼭 알아야 하는 개념과 도구에 대하여 학습할 필요가 있음서버, 클라이언트,JSON, REST API… 서버와 클라이언트클라이언트가 요청을 보내면 서버가 응답 클라이언트(Client) = 고객서버로 요청(Request)을 보내고 응답(Response)이 도착할 때까지 기다립니다서버로부터 응답을 받은 뒤에는 서버의 응답을 화면에 출력ex..

소수(Prime Number)소수란 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어떨어지지 않는 자연수코딩 테스트에서는 어떠한 자연수가 소수인지 아닌지 판벼래야하는 문제 자주 출제 약수의 성질모든 약수가 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룸예를 들어 16의 약수는 1,2,4,8,16 이 때 2 X 8 =16은 8 X 2 =16과 대칭따라서 우리는 특정한 자연수의 모든 약수를 찾을 때 가운데 약수까지만 확인하면 됌ex) 16이 2로 나누어 떨어진다는 것은 8로도 나누어 떨어진다는 것을 의미 소수판별: 개선된 알고리즘import math # 소수 판별 함수 def is_prime_number(x): # 2부터 x의 제곱근까지의 모든 수를 확인하며 for i in range..

서로소 집합서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미 서로소 집합 자료구조서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조서로소 집합 자료구조는 두 종류의 연산 지원합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조라고 불리기도 함 여러 개의 합치기 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정합집합 연산을 확인하여, 서로 연결된 두 노드 A,B를 확인1) A와 B의 루트 노드 A’, B’를 각각 찾기2) A’를 B’의 부모 노드로 설정모든 합집합 연산을 처리할 때까지 1번의 과..