helloahram

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명 중에# 일곱 난쟁이를 찾아서 오름..

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) ..