helloahram

1. 문제나무의 수 n, 필요한 길이 m, 나무들의 높이 배열이 주어졌을 때,최소 m 미터를 가지고 가기 위해 절단기에 설정할 수 있는 높이의 최대값을 구하는 프로그램 2. 알고리즘 분류* 이분 탐색* 매개 변수 탐색  3. 접근 방식매개 변수 탐색와 이분 탐색을 통해서 접근했다수 찾기 문제에서는 x == A[mid] 로 특정 숫자의 존재 여부를 확인했지만 나무 자르기 문제에서는 gets >= m 을 기준으로 필요한 최소 길이를 얻을 수 있는지 확인했다  4. 전체 코드 # 나무의 수 n, 필요한 길이 m, 나무들의 높이 배열이 주어졌을 때 # 적어도 m 미터를 가지고 가기 위해 절단기의 최대 높이를 구하는 문제n, m = map(int, input().split())trees = list(map(int..

2805 나무 자르기 문제에서 매개 변수 탐색을 이용해서 풀었기에 정리해본다 매개 변수 탐색 Parametric Search최적화 문제를 결정 문제로 풀 수 있는 알고리즘으로,조건을 만족하는 최소값 또는 최대값을 찾는 방법  * 최적화 문제 - 어떤 알고리즘의 최적 솔루션을 찾는 문제 * 결정 문제 - 답이 이미 결정되어 있다고 보고 문제를 푸는 방식  이분 탐색과의 차이점이분 탐색 공부 자료 이분 탐색은 배열에서 Target 과 일치하는 값을 찾으면 바로 함수를 종료한다반면, 매개 변수 탐색은 함수를 종료하지 않고 모든 배열을 탐색하며조건을 만족하는 가장 크거나 작은 값을 찾는다 1. 어떤 시점까지 조건을 만족하지만 그 후로 만족하지 않는 경우, 조건을 만족하는 최대값 찾기 2. 어떤 시점까지 조건을 ..

1920 수 찾기 문제를 풀다가 이분 탐색이 분류에 있길래 정리해본다 이분 탐색 Binary Search 정렬되어 있는 리스트 또는 배열에서 탐색 범위를 절반씩 좁혀가며원하는 값 Target 의 존재 위치/ 존재 여부를 찾는 알고리즘  이분 탐색 특징 단계마다 탐색 범위를 반으로 나누기 때문에 시간 복잡도는 O(logN) 이다 단, 배열이 정렬되어 있어야만 사용 가능하다는 단점이 있다  Quick Sort 와 유사한 접근 방법을 사용해서, Pivot 대신 mid 값을 계산하여left 로 탐색 범위의 왼쪽 경계, right 로 탐색 범위의 오른쪽 경계를 설정하고찾는 대상과 mid 값을 비교하여 left, right, mid 값을 변경하며 범위를 줄인다 * Quick Sort 공부 자료 이분 탐색 코드백준 ..

1. 문제 n 개의 정수 a[] 와 m 개의 정수 arr[] 가 주어졌을 때,arr[] 의 각 정수 X 가 a[] 안에 존재하는지 찾는 프로그램 2. 알고리즘 분류* 자료 구조 * 정렬 * 이분 탐색 * 해시를 사용한 집합과 맵  3. 접근 방식얼마 전에 ㅅㅎ님과 스터디하면서 같이 공부했던 이분 탐색과Quick Sort, Merge Sort 에서 배운 left, right 를 활용해 보기로 했다이분 탐색을 진행하기 전에 순서 정렬 먼저 하기! sort() sorted() 공부 자료 https://helloahram.tistory.com/entry/TIL-sorted 4. 전체 코드# m 개의 정수 X 가 n 개의 정수 a [] 안에 존재하는지 찾는 프로그램 # n, a, m, arr 입력 받기 N = ..

9663 N-Queen 을 풀다가 알고리즘 분류에 백트래킹이 있길래 한 번 개념을 정리해 본다 백트래킹 BackTracking재귀적으로 문제를 하나씩 풀어가면서 현재 재귀를 통해 확인 중인 노드 (상태) 가제한된 조건에 위배되는지 판단하고, 만약 해당 노드가 제한된 조건을 위배한다면 그 노드를 제외 (포기) 하고 다음 단계로 나아가는 방식 쉽게 말해, 현재 상태에서 가능한 모든 다음 상태를 탐색하다가조건에 맞지 않는 상태를 발견하면 그 상태를 배제하고,이전의 상태로 돌아가서 다른 가능한 경우를 탐색하는 방식이다  백트래킹 문제는 DFS (Depth-First Search 깊이 우선 탐색) 로 접근할 수 있다 DFS 는 그래프나 트리의 모든 노드를 깊이 있게 탐색하며조건에 맞지 않으면 바로 이전 상태로 ..

1. 문제N X N 체스판에서 N 개의 퀸이 서로를 공격할 수 없도록배치하는 경우의 수를 구하는 문제 ( 1   2. 알고리즘 분류* 브루트포스 알고리즘* 백트래킹 3. 접근 방식 체스판을 2차원 배열로 구성하고, 퀸은 가로/ 세로/ 대각선 모두 이동 가능하기 때문에각 열에서 퀸이 배치될 수 있는 행 위치를 정한 뒤, 이동 가능한 대각선의 규칙을 찾아서로 다른 퀸들이 충돌하지 않도록 배치한다  정리하자면,i 열 (Column) 에 퀸을 하나씩 배치하는 방식으로 시작해서 각 퀸이 위치한 j 행 (Row) 과 대각선을 확인해야 한다 ↙↗ 대각선의 경우 i + j 값이 동일하다 ↘↖ 대각선의 경우 i - j 값이 동일하다 (코드에서는 음수를 방지하기 위해 n-1 를 더한다) 그리고 모든 대각선의 길이는 2..

컴퓨터 시스템은 하드웨어와 시스템 소프트웨어로 구성되며, 이들이 함께 작동하여 응용프로그램을 실행한다모든 컴퓨터 시스템은 유사한 기능을 수행하는 유사한 하드웨어와 소프트웨어 컴포넌트를 가지고 있다1.1 정보는 비트와 컨텍스트로 이루어진다소스 프로그램은 0 과 1 로 표시되는 비트들의 연속이며, Byte 라는 8 bit 단위로 구성된다 각 바이트는 프로그램의 텍스트 문자를 나타낸다 아스키 코드들로만 구성된 프로그램 == 텍스트 파일, 다른 모든 파일은 바이너리 파일이라고 부른다  hello.c 프로그램은 연속된 바이트들로 파일에 저장되고,각 바이트들은 특정 문자에 대응되는 정수 값을 가진다 (ex. 문자 i 는 아스키 코드 105)# hello.c Program#include int main(){ prin..

1. 문제돌아온 아홉 명의 난쟁이 중에서, 키의 합이 100인 일곱 난쟁이를 구하여 오름차순으로 출력하는 프로그램 2. 알고리즘 분류* 브루트포스 알고리즘* 정렬 3. 접근 방식itertools 의 combination 을 알게 되어 조합을 이용하였다 Permutation 과 Combination 개념 정리  [TIL] itertools 순열 조합 구하기 Python일곱 난쟁이에서 조합이 필요하다고 해서 itertools 를 공부한다  순열 - 순서를 고려하여 뽑는 경우의 수 서로 다른 n 개에서 r 개를 선택하여 일렬로 나열하는 경우의 수조합 - 순서를 생각하지helloahram.tistory.com 4. 전체 코드# 일곱 난쟁이 키의 합이 100 일 때, 돌아온 9명 중에# 일곱 난쟁이를 찾아서 오름..

2309 일곱 난쟁이에서 조합이 필요하다고 해서 itertools 를 공부한다  순열 - 순서를 고려하여 뽑는 경우의 수 서로 다른 n 개에서 r 개를 선택하여 일렬로 나열하는 경우의 수조합 - 순서를 생각하지 않고 뽑는 경우의 수서로 다른 n 개에서 순서를 생각하지 않고 r 개를 택하는 경우의 수 중복 순열 Permutation with Repetition중복 가능한 n 개에서 r 개를 택하여 일렬로 나열하는 경우의 수 중복 조합 Combination with Repetition중복 가능한 n 개에서 순서를 생각하지 않고 r 개를 택하는 경우의 수 순열과 조합 예제 import itertoolschars = ['A', 'B', 'C']p = itertools.permutations(chars, 2) ..

1.  문제N개의 단어를 아래와 같이 정렬하는 프로그램을 작성하시오1. 길이가 짧은 것부터2. 길이가 같으면 사전 순으로단, 중복된 단어는 하나만 남기고 제거한다 단어의 개수 1  2. 접근 방식Python 내장 함수 sort() or sorted() 사용 + sorted() 포스팅  3. 전체 코드# 1. 길이가 짧은 것부터# 2. 길이가 작으면 사전 순으로# 알파벳 소문자로 이루어진 N개의 단어 정렬 (1