helloahram

트리 Tree 노드들이 나무 가지처럼 연결된 비선형 계측적 자료 구조 트리 구조를 왜 사용하는가?선형 데이터 구조로는 계층형 구조를 나타낼 수 없기 때문에 트리의 구조는 '데이터 저장'의 의미보다는'저장된 데이터를 더 효과적으로 탐색'하기 위해 사용한다  트리의 구조 노드 Node트리를 구성하고 있는 기본 요소노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있다 간선 Edge노드와 노드 간의 연결선루트 노트 Root Node트리 구조에서 부모가 없는 최상위 노드부모 노드 Parent Node자식 노드를 가진 노드자식 노드 Child Node부모 노드의 하위 노드 형제 노드 Sibling Node같은 부모를 가지는 노드깊이 Depth루트에서 어떤 노드까지의 간선 Edge 수높이 Height어떤 노..

18258 큐2 시간 초과 떠서 해결 방안을 찾아보다가 deque 를 공부해 보기로 했다 덱 dequeDouble-Ended Queue, 양쪽에서 요소를 추가하거나 제거할 수 있는 자료 구조 Python 에서는 collections 모듈에서 제공되며, 스택과 큐의 기능을 모두 가지고 있다from collections import dequequeue = deque('Hello')print(queue)# 실행 결과# deque(['H', 'e', 'l', 'l', 'o']) list.pop() 과 deque.popleft() 의 차이  pop() - list 에서 제일 마지막을 제외한 특정 인덱스의 원소를 삭제하기 위해서는그 원소 뒤의 모든 원소들을 한 칸씩 앞으로 옮겨야 하기 때문에 시간 복잡도 O(n) ..

1. 문제정수를 저장하는 큐를 구현한 다음, 입력으로 주어진 명령을 처리하는 프로그램을 작성하시오  2. 알고리즘 분류* 자료 구조* 큐 3. 접근 방식큐 개념 정리 와 스택 개념 정리 도 했겠다, Stack 문제 풀이와 비슷하게 하면 되지 않을까? LIFO 인지 FIFO 인지만 구분하면 되니까! + 라고 생각했지만, 시간 초과가 떠서 검색해 보니Queue 용도로 사용할 때는 deque 를 쓰는 게 좋다고 해서 deque 에 대해 공부했다 deque 개념 정리 4. 전체 코드첫번째 시도 10828 Stack 과 같은 개념으로 큐를 구현했다# 정수를 저장하는 큐를 구현한 다음,# 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오# push x - 정수 x 를 큐에 넣는 연산# pop - 큐에서 가장 ..

1. 문제정수를 저장하는 스택을 구현하고, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오 2. 알고리즘 분류* 구현 * 자료 구조* 스택 3. 접근 방식키워드 공부하면서 Stack 개념 에 대해 정리해 둔 것이 도움이 되었다그리고 pop() 을 만들 때 그대로 .pop() 을 써도 되지만, 이왕 만드는 거 다른 방법으로 만들어 보고 싶어서stack[-1] 을 다른 변수 lastpang 에 저장하고, stack[-1] 을 del 로 지운 후,그 변수 lastpang 을 출력하는 방식으로 구현해 보았다def pop(): # print(stack.pop() if stack else -1) if stack: lastpang = stack[-1] del stack[-1..

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