알고리즘
-
이 문제는 우선 순위 큐를 활용해서 푸는 문제입니다. 처음에는 어떤 방식으로 큐에 넣어서 가장 많이 포함하는 부분을 구하는지와 두번째 값 기준으로 오름차순 정렬을 하는 부분에서 시간을 많이 소요했습니다. 우선 list에 입력값을 받아 sorted함수를 통해서 첫번째 값을 기준으로 오름차순 정렬을 한다음, lambda함수를 사용해서 두번쨰 값 기준으로 정렬을 한번더 해줍니다. 아래 코드는 위에 정렬된 h_o 리스트에서 각 선분의 길이가 철로의 길이(d)보다 긴 값들을 제거해주는 코드입니다. 위의 코드는 파이썬에서 우선순위 큐에 자주사용하는 heapq 를 사용해서 heap 리스트에 h_o_list 리스트값을 하나씩 넣고 heap의 길이의 최대값을 answer에 저장해서 마지막에 최대 카운트를 가져올 수 있는..
[백준]13334 철로 [Python]이 문제는 우선 순위 큐를 활용해서 푸는 문제입니다. 처음에는 어떤 방식으로 큐에 넣어서 가장 많이 포함하는 부분을 구하는지와 두번째 값 기준으로 오름차순 정렬을 하는 부분에서 시간을 많이 소요했습니다. 우선 list에 입력값을 받아 sorted함수를 통해서 첫번째 값을 기준으로 오름차순 정렬을 한다음, lambda함수를 사용해서 두번쨰 값 기준으로 정렬을 한번더 해줍니다. 아래 코드는 위에 정렬된 h_o 리스트에서 각 선분의 길이가 철로의 길이(d)보다 긴 값들을 제거해주는 코드입니다. 위의 코드는 파이썬에서 우선순위 큐에 자주사용하는 heapq 를 사용해서 heap 리스트에 h_o_list 리스트값을 하나씩 넣고 heap의 길이의 최대값을 answer에 저장해서 마지막에 최대 카운트를 가져올 수 있는..
2023.04.18 -
이 문제는 이분탐색을 이용하여 새의 좌표가 사냥꾼 배열 arr=[1,4,6,9] 에서 잡을 수 있는 거리인지 확인하고 잡을 수 있으면 카운트하는 문제입니다. 우선 사냥꾼의 사정거리 L을 이용해서 사냥꾼이 새를 잡을 수 있는 범위를 구합니다. 사정거리의 범위는 L-Y(새의 Y좌표)를 X(새의 X좌표)에서 +, - 했을때가 범위입니다. 예를들어 첫번째 새의 경우 (7,2)니까 사정거리 4일경우 4-2의 값을 X값에 더하고 빼줍니다. 그러면 (5,2) ~ (9,2) 사이의 x좌표값에서는 해당 새를 잡을 수 있게됩니다. 이 부분을 활용해서 반복문으로 새를 호출해서 사냥꾼이 잡을 수 있는 새인지 아닌지 확인합니다. 이분 탐색과 반복문을 통해서 풀이한 코드입니다.
[백준]8983 사냥꾼 [Python]이 문제는 이분탐색을 이용하여 새의 좌표가 사냥꾼 배열 arr=[1,4,6,9] 에서 잡을 수 있는 거리인지 확인하고 잡을 수 있으면 카운트하는 문제입니다. 우선 사냥꾼의 사정거리 L을 이용해서 사냥꾼이 새를 잡을 수 있는 범위를 구합니다. 사정거리의 범위는 L-Y(새의 Y좌표)를 X(새의 X좌표)에서 +, - 했을때가 범위입니다. 예를들어 첫번째 새의 경우 (7,2)니까 사정거리 4일경우 4-2의 값을 X값에 더하고 빼줍니다. 그러면 (5,2) ~ (9,2) 사이의 x좌표값에서는 해당 새를 잡을 수 있게됩니다. 이 부분을 활용해서 반복문으로 새를 호출해서 사냥꾼이 잡을 수 있는 새인지 아닌지 확인합니다. 이분 탐색과 반복문을 통해서 풀이한 코드입니다.
2023.04.17 -
문제를 살펴보면 집의 개수 N, 공유기 개수 C가 있고 N개의 집의 개수가 주어졌을때 공유기 사이의 최대 거리를 구하는 문제입니다. 이 문제에서 중요한 점은 입력으로 받은 값들을 배열에 저장하고 오름차순으로 정렬시킨다음에 start와 end를 최소거리와 최대거리로 설정을하고 시작해야합니다. 우선 start는 시작점인 1로 설정하고 end는 가장큰 9에서 작은1사이의 거리이므로 8이됩니다. -> arr[-1] - arr[0] 위의 코드는 while문 코드인데 처음에 mid값을 start와 end의 중간값으로 설정합니다. 그리고 현재 위치를 의미하는 cur변수에 arr배열의 첫번째 값을 넣습니다. start가 1로 시작하므로 cnt도 1로 시작합니다. (1번집에 공유기를 이미 설치했다고 가정) 이제 for문..
[백준]2110 공유기 설치 [Python]문제를 살펴보면 집의 개수 N, 공유기 개수 C가 있고 N개의 집의 개수가 주어졌을때 공유기 사이의 최대 거리를 구하는 문제입니다. 이 문제에서 중요한 점은 입력으로 받은 값들을 배열에 저장하고 오름차순으로 정렬시킨다음에 start와 end를 최소거리와 최대거리로 설정을하고 시작해야합니다. 우선 start는 시작점인 1로 설정하고 end는 가장큰 9에서 작은1사이의 거리이므로 8이됩니다. -> arr[-1] - arr[0] 위의 코드는 while문 코드인데 처음에 mid값을 start와 end의 중간값으로 설정합니다. 그리고 현재 위치를 의미하는 cur변수에 arr배열의 첫번째 값을 넣습니다. start가 1로 시작하므로 cnt도 1로 시작합니다. (1번집에 공유기를 이미 설치했다고 가정) 이제 for문..
2023.04.17 -
📚스택이란? - 스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(FILO)방식이다. 데이터를 제한적으로 접근할 수 있는 구조이고, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조이다. - 파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없어 리스트 자료형을 사용하여 스택을 구현한다. - push() 메소드는 리스트의 가장 뒤쪽에 삽입하고, pop() 메소드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다. 스택의 구조 스택은 LIFO(Last In First Out) 또는 FILO(First In Last Out)의 데이터 관리 방식을 따른다. 주요 기능으로는 push() , pop() 이 있습니다. 스택의 크기 : 스택에 쌓을 수 있는 데이터의..
[자료구조] 스택, 큐📚스택이란? - 스택은 데이터를 임시 저장할 때 사용하는 자료구조로, 데이터의 입력과 출력 순서는 후입선출(FILO)방식이다. 데이터를 제한적으로 접근할 수 있는 구조이고, 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조이다. - 파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없어 리스트 자료형을 사용하여 스택을 구현한다. - push() 메소드는 리스트의 가장 뒤쪽에 삽입하고, pop() 메소드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다. 스택의 구조 스택은 LIFO(Last In First Out) 또는 FILO(First In Last Out)의 데이터 관리 방식을 따른다. 주요 기능으로는 push() , pop() 이 있습니다. 스택의 크기 : 스택에 쌓을 수 있는 데이터의..
2023.04.14 -
💡이분 탐색 알고리즘이란 이분 탐색 알고리즘은 정렬된 리스트에서 검색 범위를 반으로 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이분 탐색은 배열 내부의 데이터가 정렬(오름차순)되어 있어야만 사용할 수 있는 알고리즘이다. BigO : O(log N) 반드시 정렬된 상태에서 시작해야하므로 로그실행시간을 보장합니다. 구현에 필요한 데이터 Start : data의 처음 값 인덱스 Mid : Start, End 합의 중간 인덱스 End : data의 마지막 값 인덱스 Target : 찾고자 하는 값 data : 오름차순으로 정렬된 리스트 구현 방법 1. 리스트가 정렬된 상태인지 확인합니다. 2. start, end, mid, target 을 확입합니다. 3. 찾고자하는 target이 mid값보다 크면 오른쪽..
[알고리즘] 이분 탐색(Binary Search)💡이분 탐색 알고리즘이란 이분 탐색 알고리즘은 정렬된 리스트에서 검색 범위를 반으로 줄여 나가면서 검색 값을 찾는 알고리즘입니다. 이분 탐색은 배열 내부의 데이터가 정렬(오름차순)되어 있어야만 사용할 수 있는 알고리즘이다. BigO : O(log N) 반드시 정렬된 상태에서 시작해야하므로 로그실행시간을 보장합니다. 구현에 필요한 데이터 Start : data의 처음 값 인덱스 Mid : Start, End 합의 중간 인덱스 End : data의 마지막 값 인덱스 Target : 찾고자 하는 값 data : 오름차순으로 정렬된 리스트 구현 방법 1. 리스트가 정렬된 상태인지 확인합니다. 2. start, end, mid, target 을 확입합니다. 3. 찾고자하는 target이 mid값보다 크면 오른쪽..
2023.04.14 -
위의 문제는 입력한 N의 개수만큼 N*N의 데이터를 입력하면 h 높이 (1~100)에 따라 물에 잠기지 않는 안전한 영역의 최댓값을 구하는 문제입니다. 우선 n을 입력하고 최대값을 넣어줄 ans라는 값과 2차원 배열로 데이터를 입력하는 방법입니다. h 높이에 따라서 최대값을 구해야하므로 범위를 1이상 101미만으로 for문을 돌려줍니다. for문을 돌려줄때 최대값을 return 받아서 ans로 넘겨줘서 반복할 때마다 가장 높은 max값을 뽑아주는 방식으로 구현합니다. 아래 코드는 위의 코드에서 호출한 solve(h) 함수입니다. 안전 영역 값을 카운트해줄 cnt 를 0으로 초기화해줍니다. 그리고 이중 for 문으로 전체 입력받은 행렬을 값으로 불러올 수 있도록 해줍니다. v[i][j] 값이 0 이라는 말..
[백준]2468 안전영역 [Python]위의 문제는 입력한 N의 개수만큼 N*N의 데이터를 입력하면 h 높이 (1~100)에 따라 물에 잠기지 않는 안전한 영역의 최댓값을 구하는 문제입니다. 우선 n을 입력하고 최대값을 넣어줄 ans라는 값과 2차원 배열로 데이터를 입력하는 방법입니다. h 높이에 따라서 최대값을 구해야하므로 범위를 1이상 101미만으로 for문을 돌려줍니다. for문을 돌려줄때 최대값을 return 받아서 ans로 넘겨줘서 반복할 때마다 가장 높은 max값을 뽑아주는 방식으로 구현합니다. 아래 코드는 위의 코드에서 호출한 solve(h) 함수입니다. 안전 영역 값을 카운트해줄 cnt 를 0으로 초기화해줍니다. 그리고 이중 for 문으로 전체 입력받은 행렬을 값으로 불러올 수 있도록 해줍니다. v[i][j] 값이 0 이라는 말..
2023.04.13 -
재귀함수란 - 재귀함수란, 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. 즉, 함수의 정의에서 함수 자신을 참조하는 것입니다. - 재귀함수는 보통 문제를 작은 부분 문제로 분할하여 해결할 수 있을 때 사용됩니다. 이때, 재귀함수는 각각의 부분 문제를 해결하는 데에도 같은 함수를 호출하게 됩니다. - 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)과 피보나치수열(Fibonacci) 입니다. 재귀함수의 장단점 장점 - 코드가 간결하고 이해하기가 쉽다. - 반복문을 사용하지 않아도 동일한 결과를 얻을 수 있다. 단점 - 함수를 호출할 때마다 스택 메모리에 쌓이기 때문에, 메모리를 많이 사용한다. - 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다. - 반복문을 사..
[알고리즘] 재귀함수(Recursion function), 꼬리재귀함수(Tail call recursion)재귀함수란 - 재귀함수란, 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. 즉, 함수의 정의에서 함수 자신을 참조하는 것입니다. - 재귀함수는 보통 문제를 작은 부분 문제로 분할하여 해결할 수 있을 때 사용됩니다. 이때, 재귀함수는 각각의 부분 문제를 해결하는 데에도 같은 함수를 호출하게 됩니다. - 이러한 재귀함수의 가장 대표적인 사용 예제는 팩토리얼(Factorial)과 피보나치수열(Fibonacci) 입니다. 재귀함수의 장단점 장점 - 코드가 간결하고 이해하기가 쉽다. - 반복문을 사용하지 않아도 동일한 결과를 얻을 수 있다. 단점 - 함수를 호출할 때마다 스택 메모리에 쌓이기 때문에, 메모리를 많이 사용한다. - 깊이가 너무 깊어지면 스택 오버플로우가 발생할 수 있다. - 반복문을 사..
2023.04.09 -
복잡도에 대해서 1. 크게 시간 복잡도(Time Complexity)와 공간 복잡도로 나눌 수 있다. 2. 알고리즘의 성능 평가 및 효율성을 나타내는 척도이다. 3. 동일한 기능을 수행하는 알고리즘이 있을때 복잡도가 낮을수록 좋은 알고리즘이라 말한다. 1. 시간 복잡도 - 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수의 총량을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 즉, 입력 크기가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가량을 나타내는 것입니다. 시간 복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악..
[알고리즘] 시간 복잡도, 공간 복잡도, 빅오(Big-O) 표기법복잡도에 대해서 1. 크게 시간 복잡도(Time Complexity)와 공간 복잡도로 나눌 수 있다. 2. 알고리즘의 성능 평가 및 효율성을 나타내는 척도이다. 3. 동일한 기능을 수행하는 알고리즘이 있을때 복잡도가 낮을수록 좋은 알고리즘이라 말한다. 1. 시간 복잡도 - 시간 복잡도(Time Complexity)는 알고리즘이 실행되는 동안 수행하는 기본적인 연산 횟수의 총량을 나타내며, 입력 크기에 대한 함수로 표현됩니다. 즉, 입력 크기가 증가함에 따라 알고리즘이 실행되는 데 걸리는 시간의 증가량을 나타내는 것입니다. 시간 복잡도를 표기하는 방법 Big-O(빅-오) ⇒ 상한 점근 Big-Ω(빅-오메가) ⇒ 하한 점근 Big-θ(빅-세타) ⇒ 그 둘의 평균 위 세 가지 표기법은 시간 복잡도를 각각 최악..
2023.04.09