BerryDevelop

이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 좁혀간다 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 (ex: 선택 정렬에서 매 단계마다 가장 작은 값 찾기) 이진탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2 N에 비례함. 예를 들어 초기 데이터 개수가 32일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남음. 2단계 : 8개 가량 3단계 4개 가량 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(log N)을 보장함 #이진 탐색 소스코드 구현(재귀함수) def binary_searc..

1. aws에 인스턴스 생성 2.키페어 생성 및 다운로드 받기 3. mac 터미널에서 home brew로 awscil 다운 brew install awscli 4.aws에서 만들어둔 인스턴스에 들어가서 연결 선택-> ssh 클라이언트 (퍼블릭 DNS을(를) 사용하여 인스턴스에 연결) 에 나오는 명령어 복사 ssh -i "프라이빗키" ec2-user@~~~~.ap-northeast-2.compute.amazonaws.com 5. 터미널에서 프라이빗 키 받은 위치로 이동 6. 4번에서 복사해온 것 터미널에 입력 터미널에서 ec2 연결됨 7. ec2서버에서 깃 다운로드 sudo yum install -y git 8. 자바 11버전 다운로드 sudo amazon-linux-extras install java-o..

문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20)..

정렬(Sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 각 정렬 알고리즘 비교 정렬 알고리즘 핵심 아이디어 평균 시간 복잡도 공간 복잡도 특징 선택 정렬 가장 작은 데이터를 '선택'해서 정렬되지 않은 데이터 중에서 가장 앞쪽에 있는 데이터와 위치를 바꾸는 방법 O(N^2) O(N) 아이디어가 매우 간단합니다. 삽입 정렬 데이터를 앞쪽에서부터 하나씩 확인하며 데이터를 적절한 위치에 '삽입'하는 방법 O(N^2) O(N) 데이터가 거의 정렬되어 있을 때 가장 빠름 퀵 정렬 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법 O(NlogN) O(N) 대부분에 경우에 가장 적합 충분히 빠름 계수 정렬 특정한 값..

문제 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다. 오늘부터 인구 이동이 시작되는 날이다. 인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다. 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루 동안 연다. 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다. 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은..

문제점 jwt토큰을 이용하여 로그인을 구현하려고 했는데 토큰이 발행이 안됐다. 자바 11버전에서는 jaxb를 제공하지 않아서 따로 추가해줘야 한다. 2023-01-18 18:44:12.676 ERROR 11548 --- [nio-8090-exec-6] o.a.c.c.C.[.[.[/].[dispatcherServlet] : Servlet.service() for servlet [dispatcherServlet] in context with path [] threw exception [Handler dispatch failed; nested exception is java.lang.NoClassDefFoundError: javax/xml/bind/DatatypeConverter] with root cause..

BFS: 너비 우선 탐색 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 큐 자료구조를 이용 탐색 시작 노드를 큐에 삽입하고 방문처리 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 BFS 동작 예시 1부터 시작하면 1이랑 거리가 가까운 2, 3, 8이 먼저 탐색되고, 그다음 2랑 가까운 7 ••• 마지막으로 거리가 제일 먼 6이 탐색됨 BFS 코드 예제 from collections import deque #BFS 메서드 정의 def bfs(graph, start, visited): #큐(Queue) 구현을 위해 deque 라이브러리 사용 queue = deque([start]) #현재 노드..

DFS: 깊이 우선 탐색 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 스택 자료구조 혹은 재귀함수를 이용 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다. #DFS 메서드 정의 def dfs(graph, v, visited): #현재 노드를 방문처리 visited[v] = True print(v, end=' ') #현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i ,visited) ..

더보기 그래프 탐색 알고리즘을 사용하기 위해 알아야할 자료구조를 알아보자 스택 자료구조 선입후출: 먼저 들어온 데이터가 나중에 나가는 형식의 자료구조 입구와 출구가 동일한 형태로 스택을 시각화 할 수 있다.(ex: 박스 쌓기) 스택 동작 예시 스택 구현 예제(python) 리스트 자료형 사용 - append() :가장 오른쪽에 원소 삽입 - pop(): 가장 오른쪽 원소 삭제 stack = [] #삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack...

문제설명 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 형태 자물쇠와 M x M 크기인 정사각형태 열쇠가 주어짐 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않음 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 함 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 구현 https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그..