helloahram

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. 문제돌아온 아홉 명의 난쟁이 중에서, 키의 합이 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

1181 단어 정렬을 풀면서 sorted() 개념을 정리한다 sorted()데이터를 정렬하는 가장 기본적인 파이썬 내장 정렬 함수* 데이터 ; 리스트, 튜플, 문자열, 딕셔너리 함수 포맷sorted(iterable, key=None, reverse=False)sorted(정렬할 데이터)sorted(정렬할 데이터, reverse 파라미터)sorted(정렬할 데이터, key 파라미터)sorted(정렬할 데이터, key 파라미터, reverse 파라미터) 파라미터1) 정렬할 데이터 ; Iterable 한 데이터 이어야 한다 2) Reverse 파라미터오름차순으로 정렬할지 내림차순으로 정렬할지 정할 . 수있다Default 는 reverse=False  3) Key 파라미터어떤 것을 기준으로 정렬할 것인가? so..

큐 Queue 스택과 같이 데이터를 임시 저장하는 자료 구조First In First Out 선입선출 FIFO 구조   일상 예시, 카페에서 계산하고 커피를 받는 줄 Buffer (완충기억기) - 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역 컴퓨터 장치들 사이에서 data 를 주고 받을 때, 각 장치 사이에서 존재하는속도 차이나 시간 차이를 극복하기 위해 임시 기억 자치의 자료 구조로 Queue 를 사용한다    큐 작업Enqueue 큐에 데이터를 추가하는 작업Dequeue 데이터를 꺼내는 작업Front 데이터를 꺼내는 쪽Rear 데이터를 넣는 쪽  배열로 큐 구현하기디큐를 할 때 배열에서 2번째 이후의 모든 원소를 하나씩 앞으로 옮긴다 인큐 처리 복잡도..

하노이의 탑을 풀기 전에 재귀 함수의 개념 먼저 정리한다  재귀 Recursive 반복 Iterative   재귀 함수 Recursion Function 자기 자신을 다시 호출해 작업을 수행하는 방식자신의 로직을 내부적으로 반복단, '함수 자신' 이 아니라 자기 자신과 똑같은 함수'를 호출하는 것이다! 혼동 주의반복문으로 구현 가능한 로직은 모두 재귀함수로 구현이 가능하고 그 반대도 가능하다  * Base Case 더 이상 문제를 쪼갤 필요가 없는, 종료 조건에 도달한 경우* Recursive Case 문제를 작은 문제들로 나누어 해결하는 과정   + 09/18 WED 나중에 읽어봐야지 https://velog.io/@eddy_song/you-can-solve-recursion 예시01 팩토리얼 함수 1..

병합 정렬일단 반으로 나누고, 나중에 합쳐서 정렬한다  1. 하나의 리스트를 두 개의 균등한 크기로 분할하고 2. 분할된 부분 리스트들을 정렬해서 3. 정렬된 부분 리스트들을 합친다  퀵 정렬과의 차이점 병합 정렬 Merge Sort퀵 정렬 Quick Sort시간 복잡도최악의 경우에도 O(N* logN) 보장 최악의 경우 O(N^2)진행 방법 정확히 반절씩 나눈다 피벗 값에 따라서 편향되게 분할할 가능성이 있다공간 복잡도메모리 활용 비효율적(기존의 데이터를 담을 추가적인 배열 공간 필요)  Merge Sort 를 Python 으로 구현해보기  1번 방식mergeSortdef mergeSort(a): # a 의 길이가 1 이하이면 끝 if len(a)  Mainif __name__ == "__m..