분류 전체보기

[그래프탐색] BFS - JS, Python

너비 우선 탐색 - Breath Frist Search 가까운 노드부터 탐색하는 알고리즘 DFS는 최대한 멀리있는 노드를 우선으로 탐색하는 방식으로 동작한다했는데, BFS는 가까이 있는 노드부터 우선탐색 큐를 이용한 선입선출방식 가중치 없는 그래프에서 최단 경로 문제에서 많이 쓰인다 ex) 서울에서 부산으로 가는데 거쳐야하는 최소 정거장의 수 ex) 임의의 4자리 숫자 x에서 한자리(0~9)로 변경하면 다른 숫자 y를 만들 수 있음 이떄 x에서 z를 만들기 위한 최소 변경횟수 ex) 친구관계에서의 단계 1. 탐색 시작 노드를 큐에 삽입하고 방문처리 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 3. 2번 과정을 더이상 수행할 수 없을 때까지 반복 ..

HTTP

HTTP Hyper Text Transfer Protocol의 약자로 웹상에서 정보를 주고받을 수 있는 프로토콜 HTTP는 클라이언트와 서버 사이에 이루어지는 요청/응답 (request/response) 프로토콜 예를 들면 클라이언트인 웹 브라우저가 HTTP를 통하여 서버로부터 웹페이지(HTML)이나 그림 정보를 요청하면 서버는 이 요청에 응답하여 필요한 정보를 해당 사용자에게 전달하는 것 HTTP를 통해 전달되는 자료는 http:로 시작하는 주소(URL)로 조회할 수 있음 HTTP의 특징 2가지 1. 요청 / 응답 (Request / Response) HTTP 통신의 핵심이자 전송이라는 것은 보내는 주체와 받는 주체가 있음 보내는 주체는 주체에게 요청(request)를 보내고, 받는 주체는 요청을 보낸..

[백준 11047] 동전0 - python

아이디어 입력받는 동전을 내림차순으로 정렬한 뒤, coin리스트를 돈다. 입력받은 돈 K 가 현재 coin보다 작을 경우에는 pass K의 몫과 나머지를 구한 후에 각각 result와 K값에 넣어준다 N, K = map(int, input().split()) coin = [] for _ in range(N): coin.append(int(input())) result = 0 # 코인최소개수 coin.sort(reverse=True) for i in coin: if i > K: continue if K == 0: break result += K//i K %= i print(result)

[그래프탐색] DFS- JS, Python

탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그래프, 트리 등의 자료구조 안에서 탐색하는 문제 자주 물음 DFS와 BFS를 다루기 전에 스택, 큐, 재귀함수에 대한 개념을 알아야 하는데 전 포스팅에 정리한 내용을 확인해 주세요 2021.02.07 - [이론/자료구조] - 스택(Stack) - JS 2021.02.07 - [이론/자료구조] - 배열 - JS 2020.04.15 - [이론/알고리즘] - 재귀 함수 배열 - JS 배열이란? 가장 일반적인 구조 메모리 상에 같은 타입의 자료가 연속적으로 저장됨 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위 특징 같은 타입의 데이터를 나열한 선형 자료구조 ssafy-story.tistory.com 스택(Stack) - JS 참고사이트자바..

비트 연산자 - 비트 부정 연산에 대한 고찰

JS 문제를 풀다가 '|'를 발견하고 당황했다,, 이 기본적인걸 까먹었다니 ㅜㅜ 블로그에 정리하면서 다시 상기시키려 한다 JS에는 다양한 연산자가 존재한다 1. 할당 2. 비교 3. 산술 4. 비트 5. 논리 6. 문자열 7. 조건(삼항) 8. 쉼표 9. 단항 10. 관계 할당과 비교, 산술은 자주 쓰이는 것이므로 정리하지 않고 넘어가려한다 혹시 알고싶은 분은 여기 들어가보시면 됩니다 비트 연산자 비트 연산자는 피연산자를 10진수, 16진수, 8진수처럼 취급하지 않고 32비트의 집합으로 취급한다. 예를 들면 10진수의 9는 2진수의 1001로 나타낼 수 있다. 비트 단위 연산자는 이진법으로 연산을 수행하지만 JS의 표준 숫자값을 반환한다. 라고 MDN에 정리가 되어있다 연산자 사용법 name 설명 논리곱..

[소수 판별] 에라토스테네스의 체 - JS

에라토스테네스의 체 소수 판단 알고리즘 소수들을 대량으로 빠르고 정확하게 구하는 방법 단일 숫자 소수 여부 확인 어떤 수의 소수 여부 확인할 때는 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N*1/2)의 시간 복잡도로 빠르게 구할 수 있음 수가 수(N)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N의 제곱근 이하이기 때문 원리 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나감 배열을 생성하여 초기화 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (지울 때 자기자신은 지우지 않고 이미 지워진 수는 건너뛴다) 2부터 시작하여 남아있는 수를 모두 출력한다 Array() : 배열 초기화 Array안에 수(n)를 넣으면 n..