알고리즘
-
문제 (링크) 직선상에 1km 간격으로 배치되어 있는 도시들의 나라 flatland 도시들 중 몇몇은 space station를 가지고 있음 space station으로부터 도시들의 거리들 중 최댓값을 구하기 풀이 def flatlandSpaceStations(n, c): max_gap = 0 if len(c)==1: # end of cities or middle return max(n-c[0]-1, c[0]) c = sorted(c) for i in range(len(c)-1): if c[i+1]-c[i] >max_gap: max_gap=c[i+1]-c[i] return max(max_gap//2, n-c[-1]-1, c[0]) max 함수를 잘 활용해야 하는 문제였다. space station의 위치..
[hackerrank] Flatland Space Stations (Python)문제 (링크) 직선상에 1km 간격으로 배치되어 있는 도시들의 나라 flatland 도시들 중 몇몇은 space station를 가지고 있음 space station으로부터 도시들의 거리들 중 최댓값을 구하기 풀이 def flatlandSpaceStations(n, c): max_gap = 0 if len(c)==1: # end of cities or middle return max(n-c[0]-1, c[0]) c = sorted(c) for i in range(len(c)-1): if c[i+1]-c[i] >max_gap: max_gap=c[i+1]-c[i] return max(max_gap//2, n-c[-1]-1, c[0]) max 함수를 잘 활용해야 하는 문제였다. space station의 위치..
2023.11.19 -
※문제 해석은 책 그대로 쓰지 않고 직접 합니다. 리트코드 706. 해시맵 디자인 1. 문제 Design a HashMap without using any built-in hash table libraries. 빌트인 해쉬 테이블 라이브러리를 사용하지 말고 해시맵을 디자인하세요. Implement the MyHashMap class: MyHashMap() initializes the object with an empty map. MyHashMap()은 빈 맵으로 초기화합니다. void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corre..
[leetcode] 리트코드 706번 해시맵 디자인※문제 해석은 책 그대로 쓰지 않고 직접 합니다. 리트코드 706. 해시맵 디자인 1. 문제 Design a HashMap without using any built-in hash table libraries. 빌트인 해쉬 테이블 라이브러리를 사용하지 말고 해시맵을 디자인하세요. Implement the MyHashMap class: MyHashMap() initializes the object with an empty map. MyHashMap()은 빈 맵으로 초기화합니다. void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corre..
2023.02.01 -
스터디 요일이 매주 화요일이기 때문에 연휴에도 하나쯤 포스팅해 두어야할 것 같아 올리는 버블 정렬 알고리즘입니다. 티스토리 블로그 시작 전에 문제를 풀어본 주제였지만 가볍게 내용 정리 차원에서 올려봅니다! 1. 버블 정렬이란? 먼저 정렬이란, 어떤 데이터의 순서를 정해진 규칙대로 나열하는 것입니다. 정렬에 관한 알고리즘은 다양하고 각 알고리즘마다 작동 방식의 효율이 다르기 때문에 종류와 특징에 대해 잘 알고 있어야 효율적인 알고리즘 구현을 할 수 있습니다. 버블 정렬 Bubble sort이란 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 클 경우 순서를 바꿔주는 알고리즘입니다. 버블 정렬이 진행되는 동안, 숫자가 큰 순서대로 뒤에서부터 배열되는 특징이 있습니다. 2. 시간 복잡도 ..
[알고리즘] 버블 정렬 Bubble sort스터디 요일이 매주 화요일이기 때문에 연휴에도 하나쯤 포스팅해 두어야할 것 같아 올리는 버블 정렬 알고리즘입니다. 티스토리 블로그 시작 전에 문제를 풀어본 주제였지만 가볍게 내용 정리 차원에서 올려봅니다! 1. 버블 정렬이란? 먼저 정렬이란, 어떤 데이터의 순서를 정해진 규칙대로 나열하는 것입니다. 정렬에 관한 알고리즘은 다양하고 각 알고리즘마다 작동 방식의 효율이 다르기 때문에 종류와 특징에 대해 잘 알고 있어야 효율적인 알고리즘 구현을 할 수 있습니다. 버블 정렬 Bubble sort이란 두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 클 경우 순서를 바꿔주는 알고리즘입니다. 버블 정렬이 진행되는 동안, 숫자가 큰 순서대로 뒤에서부터 배열되는 특징이 있습니다. 2. 시간 복잡도 ..
2022.09.09 -
1. 이진 탐색이란 정렬된 데이터로부터 효과적으로 타겟을 찾을 수 있는 알고리즘입니다. 탐색할 자료를 둘로 나누어 찾는 데이터가 있는지 없는지 확인하기 때문에, 데이터가 정렬되어 있을 때 순차 탐색 sequential search보다 훨씬 빠르게 찾을 수 있습니다. 특정 범위 내에서 숫자를 추측하는 guessing game등을 할 때 필승할 수 있는 방법입니다. 이진 탐색은 분할 정복 알고리즘의 일종이기도 합니다. 1부터 71까지 랜덤하게 존재하는 숫자 배열로부터 7을 찾는 제일 효율적인 방법으로 시각화하면 아래 그림과 같습니다. 분할 정복 알고리즘 divide and conquer이란, 문제를 하나 또는 둘 이상으로 나누어 문제를 해결하는 알고리즘입니다. 나눠진 문제가 충분히 작은 상태에서 해결이 가능..
[알고리즘] 이진 탐색 Binary search1. 이진 탐색이란 정렬된 데이터로부터 효과적으로 타겟을 찾을 수 있는 알고리즘입니다. 탐색할 자료를 둘로 나누어 찾는 데이터가 있는지 없는지 확인하기 때문에, 데이터가 정렬되어 있을 때 순차 탐색 sequential search보다 훨씬 빠르게 찾을 수 있습니다. 특정 범위 내에서 숫자를 추측하는 guessing game등을 할 때 필승할 수 있는 방법입니다. 이진 탐색은 분할 정복 알고리즘의 일종이기도 합니다. 1부터 71까지 랜덤하게 존재하는 숫자 배열로부터 7을 찾는 제일 효율적인 방법으로 시각화하면 아래 그림과 같습니다. 분할 정복 알고리즘 divide and conquer이란, 문제를 하나 또는 둘 이상으로 나누어 문제를 해결하는 알고리즘입니다. 나눠진 문제가 충분히 작은 상태에서 해결이 가능..
2022.09.07 -
그래프란? 실제 세계의 현상이나 사물을 노드 Node와 간선 Edge 로 표현하기 위해 사용하는 알고리즘으로, 네비게이션 길찾기, 게임 내 캐릭터 이동, 지식 그래프 등에 사용되며, 앞서 배웠던 트리 또한 그래프의 일종입니다. 우리에게 익숙한 그래프의 예시로는 쾨니히스베르크의 다리 문제가 있습니다. 1. 용어 노드 Node : 위치, 정점 vertex와 같음 간선 Edge : 위치 간의 관계를 표시한 선, 노드를 연결한 선, link 또는 branch 와 같 인접 정점 Adjacent vertex : 간선으로 직접 연결된 노드를 말함 차수 Degree : 방향이 없는 그래프에서 하나의 노드에 연결된 노드의 갯수 평균 차수 average degree: 노드 개수와 간선의 개수를 비교하기 위한 값 진입 차수..
[알고리즘] 그래프 Graph (1)그래프란? 실제 세계의 현상이나 사물을 노드 Node와 간선 Edge 로 표현하기 위해 사용하는 알고리즘으로, 네비게이션 길찾기, 게임 내 캐릭터 이동, 지식 그래프 등에 사용되며, 앞서 배웠던 트리 또한 그래프의 일종입니다. 우리에게 익숙한 그래프의 예시로는 쾨니히스베르크의 다리 문제가 있습니다. 1. 용어 노드 Node : 위치, 정점 vertex와 같음 간선 Edge : 위치 간의 관계를 표시한 선, 노드를 연결한 선, link 또는 branch 와 같 인접 정점 Adjacent vertex : 간선으로 직접 연결된 노드를 말함 차수 Degree : 방향이 없는 그래프에서 하나의 노드에 연결된 노드의 갯수 평균 차수 average degree: 노드 개수와 간선의 개수를 비교하기 위한 값 진입 차수..
2022.08.01