코테 대비 python, c 대강 정리

알고리즘/코테 준비

코테 대비 python, c 대강 정리

이게될까 2024. 3. 23. 02:03

728x90

import sys
sys.setrecursionlimit(10000)  # 재귀 호출 깊이 한계를 10000으로 설정


dp = [[0 for _ in range(m)] for _ in range(n)] # 리스트 행렬 만들기 n * m

graph = [[0] * (n + 1) for _ in range(n + 1)]  # 올바른 2차원 리스트 초기화


numbers = list(map(int, input().split()))  # 한 줄의 숫자들을 입력받음

num = [list(map(int, input().strip().split())) for _ in range(n)]  # 행렬 입력받기

import sys

# input 함수를 sys.stdin.readline으로 재정의
input = sys.stdin.readline

# n을 입력받음
n = int(input().strip())

# 한 줄에 n개의 정수를 입력받아 dp 리스트에 저장
dp = list(map(int, input().strip().split()))

def DFS(start):
    stack = [start]
    visit[start] = True
    while stack:
        node = stack.pop()
        for next_node in graph[node]:
            if not visit[next_node]:
                visit[next_node] = True
                stack.append(next_node)

# 전역변수 함수에서의 사용

count = 0  # 전역 변수

def increment():
    global count  # count를 전역 변수로 참조하겠다고 명시
    print(count)  # 이제 여기서의 count는 전역 변수 count를 참조
    count += 1

increment()


# 리스트 사용 예시

fruits = ['apple', 'banana']
fruits.insert(1, 'orange')  # 1번 인덱스에 'orange'를 삽입
print(fruits)
#['apple', 'orange', 'banana']

stack = [1, 2, 3]
last_item = stack.pop()  # 마지막 요소인 3을 제거하고 반환
print(last_item)
print(stack)

#3
#[1, 2]

queue = [1, 2, 3]
first_item = queue.pop(0)  # 첫 번째 요소인 1을 제거하고 반환
print(first_item)
print(queue)

#1
#[2, 3]

리스트 몇개 더

파이썬의 list 객체는 유연하고 다양한 기능을 제공합니다. 여기 10가지 주요 기능과 각 기능이 어떤 상황에서 사용되는지에 대해 설명합니다.

1. `append()`

리스트의 끝에 항목을 추가합니다. 스택의 구현이나 단순히 리스트에 요소를 추가할 때 사용됩니다.
fruits = ['apple'] fruits.append('banana')

2. `extend()`

다른 리스트의 모든 요소를 현재 리스트의 끝에 추가합니다. 두 리스트를 합칠 때 사용됩니다.
fruits = ['apple', 'banana'] others = ['orange', 'grape'] fruits.extend(others)

3. `remove()`

리스트에서 값과 일치하는 첫 번째 항목을 제거합니다. 특정 값을 찾아 제거할 때 사용됩니다.
fruits = ['apple', 'banana', 'cherry'] fruits.remove('banana')

4. `index()`

리스트에서 요소의 위치를 찾습니다. 특정 요소의 인덱스를 알고 싶을 때 사용됩니다.
fruits = ['apple', 'banana', 'cherry'] index = fruits.index('banana')

5. `count()`

리스트에서 요소의 개수를 반환합니다. 특정 값이 리스트에 몇 번 등장하는지 세고 싶을 때 사용됩니다.
numbers = [1, 2, 2, 3] count = numbers.count(2)

6. `sort()`

리스트의 요소를 정렬합니다. 기본적으로 오름차순으로 정렬하며, reverse=True 옵션으로 내림차순 정렬도 가능합니다.
numbers = [3, 1, 4, 1] numbers.sort()

7. `reverse()`

리스트의 요소의 순서를 반대로 뒤집습니다. 순서를 뒤집고 싶을 때 사용됩니다.
numbers = [1, 2, 3] numbers.reverse()

8. `copy()`

리스트의 얕은 복사본을 만듭니다. 기존 리스트를 변경하지 않고 복사본을 작업할 때 사용됩니다.
original = [1, 2, 3] copied = original.copy()

9. `clear()`

리스트의 모든 요소를 제거합니다. 리스트를 초기화하고 싶을 때 사용됩니다.
fruits = ['apple', 'banana', 'cherry'] fruits.clear()

10. `len()`

리스트의 요소 개수를 반환합니다. 리스트의 길이(크기)를 알고 싶을 때 사용됩니다. len()은 리스트 메서드가 아니지만, 리스트와 함께 자주 사용됩니다.
fruits = ['apple', 'banana', 'cherry'] length = len(fruits)

각 기능은 특정 상황에서 리스트를 효과적으로 조작할 수 있도록 도와줍니다. 데이터 구조를 구현하거나 데이터를 처리할 때 이러한 기능들을 적절히 활용할 수 있습니다.

힙 구현!!

파이썬의 heapq 모듈은 힙 큐 알고리즘, 즉 우선순위 큐를 제공합니다. 힙은 모든 부모 노드가 자식 노드보다 작거나 같은(최소 힙) 또는 크거나 같은(최대 힙) 이진 트리입니다. 파이썬의 heapq 모듈은 기본적으로 최소 힙을 구현합니다.

주요 기능과 사용 방법

heapq.heappush(heap, item): 힙에 새로운 요소를 추가합니다.
heapq.heappop(heap): 힙에서 가장 작은 요소를 제거하고 반환합니다.
heapq.heappushpop(heap, item): 새 요소를 힙에 추가한 후, 가장 작은 요소를 제거하고 반환합니다. 이는 heappush를 따라 heappop을 호출하는 것보다 더 효율적입니다.
heapq.heapify(x): 리스트 x를 즉시 힙으로 변환합니다. 이 연산은 O(N) 시간에 수행됩니다.
heapq.heapreplace(heap, item): 힙에서 가장 작은 요소를 제거하고 반환한 후, 새 요소를 추가합니다. heappop을 따라 heappush을 호출하는 것보다 더 효율적입니다.
heapq.nlargest(n, iterable, key=None): 데이터에서 n개의 가장 큰 요소들로 구성된 리스트를 반환합니다.
heapq.nsmallest(n, iterable, key=None): 데이터에서 n개의 가장 작은 요소들로 구성된 리스트를 반환합니다.

예제

import heapq

# 빈 힙 생성
heap = []

# 힙에 요소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print(heap)  # 출력: [1, 3, 7, 4]

# 힙에서 가장 작은 요소 제거 및 반환
print(heapq.heappop(heap))  # 출력: 1
print(heap)  # 출력: [3, 4, 7]

# 리스트를 힙으로 변환
nums = [4, 1, 7, 3, 8, 5]
heapq.heapify(nums)
print(nums)  # 출력: [1, 3, 5, 4, 8, 7]

# n개의 가장 작은 요소들 찾기
print(heapq.nsmallest(3, nums))  # 출력: [1, 3, 4]

# n개의 가장 큰 요소들 찾기
print(heapq.nlargest(3, nums))  # 출력: [8, 7, 5]

최대 힙 구현하기

파이썬의 heapq 모듈은 최소 힙만을 직접 지원합니다. 최대 힙을 구현하려면, 각 값에 대해 튜플을 사용하고 값의 부호를 바꾸는 방법을 사용할 수 있습니다. 예를 들어, 원래 값을 -로 곱한 값을 우선순위로 사용합니다.

heap = []
heapq.heappush(heap, (-1, "Johannes"))
heapq.heappush(heap, (-5, "Nikolaus"))
heapq.heappush(heap, (-3, "Dorothea"))

print(heapq.heappop(heap)[1])  # 출력: Nikolaus

heapq 모듈을 활용하면 효율적으로 우선순위 큐를 구현할 수 있으며, 다양한 알고리즘과 자료 구조에서 유용하게 사용됩니다.

코딩 테스트를 준비할 때 파이썬의 다양한 내장 함수와 모듈을 알고 있으면 효과적으로 문제를 해결할 수 있습니다. 여기 코딩 테스트에 유용한 파이썬의 함수와 모듈을 몇 가지 추천드립니다:

1. 리스트와 관련된 함수

sorted(), list.sort(): 리스트를 정렬할 때 사용합니다. sorted()는 새로운 리스트를 반환하고, list.sort()는 리스트 자체를 정렬합니다.
reversed(), list.reverse(): 리스트의 요소 순서를 뒤집습니다.
enumerate(): 반복 가능한 객체를 인덱스와 함께 순회할 때 사용합니다.
zip(): 여러 개의 반복 가능한 객체를 병렬로 루핑할 때 사용합니다.

2. 문자열 처리 함수

str.split(): 문자열을 특정 구분자로 나누어 리스트를 반환합니다.
str.join(): 문자열 리스트를 하나의 문자열로 병합할 때 사용합니다.
str.strip(): 문자열의 양쪽 끝에서 공백이나 특정 문자를 제거합니다.

3. 수학 관련 함수와 모듈

math 모듈: sqrt(), factorial(), gcd(), pow() 등 수학 연산을 위한 다양한 함수를 제공합니다.
abs(): 절대값을 반환합니다.
min(), max(): 시퀀스의 최소값, 최대값을 반환합니다.
sum(): 시퀀스의 모든 요소의 합을 반환합니다.

4. 자료구조 관련 모듈

collections 모듈: deque, Counter, defaultdict 등의 다양한 자료구조를 제공합니다.
heapq 모듈: 힙 큐(우선순위 큐)를 구현하는 함수를 제공합니다.
itertools 모듈: 반복자를 생성하는 유용한 함수(combinations, permutations, product 등)를 제공합니다.

5. 입출력 관련

input(): 사용자 입력을 받습니다.
print(): 값을 출력합니다. sep, end, file 등의 인자로 출력 형식을 지정할 수 있습니다.
sys.stdin.readline(): 한 줄의 입력을 받습니다. 대량의 데이터를 빠르게 입력받아야 할 때 유용합니다.

6. 기타 유용한 기능

map(), filter(): 시퀀스의 모든 항목에 함수를 적용하거나 특정 조건에 맞는 항목만 필터링합니다.
lambda: 익명 함수를 생성합니다. 간단한 함수를 인자로 전달할 때 유용합니다.
list comprehension, dict comprehension: 리스트나 딕셔너리를 간결하게 생성할 수 있는 방법입니다.

코딩 테스트를 준비하면서 이러한 함수와 모듈들을 숙지하고 연습 문제를 통해 활용해보는 것이 좋습니다. 문제의 유형과 요구 사항에 따라 적절한 도구를 선택하여 효율적으로 해결 방법을 찾아내는 것이 중요합니다.

collections.deque는 양쪽 끝에서 빠르게 추가 및 삭제 연산을 할 수 있는 자료구조입니다. "덱(deque)"은 "Double-Ended Queue"의 약자로, 스택과 큐의 기능을 모두 가지고 있어 다양한 상황에서 유용하게 사용될 수 있습니다.

deque의 주요 메서드

append(x): 덱의 오른쪽 끝에 x를 추가합니다.
appendleft(x): 덱의 왼쪽 끝에 x를 추가합니다.
pop(): 덱의 오른쪽 끝 요소를 제거하고 반환합니다.
popleft(): 덱의 왼쪽 끝 요소를 제거하고 반환합니다.
extend(iterable): 반복 가능한 객체의 모든 요소를 덱의 오른쪽 끝에 추가합니다.
extendleft(iterable): 반복 가능한 객체의 모든 요소를 덱의 왼쪽 끝에 추가합니다. 주의할 점은 추가되는 요소들의 순서가 반대로 된다는 것입니다.
rotate(n=1): 덱을 n만큼 오른쪽으로 회전합니다(n이 음수면 왼쪽으로 회전).
clear(): 덱의 모든 요소를 제거합니다.
count(x): 덱에서 x 값의 요소 개수를 반환합니다.
remove(value): 덱에서 value 값을 가진 첫 번째 요소를 제거합니다.

deque 사용 예제

from collections import deque

# deque 생성
d = deque()

# 요소 추가
d.append(1)  # 덱의 오른쪽 끝에 요소 추가
d.appendleft(2)  # 덱의 왼쪽 끝에 요소 추가
print("요소 추가 후:", d)

# 요소 제거
d.pop()  # 덱의 오른쪽 끝 요소 제거
d.popleft()  # 덱의 왼쪽 끝 요소 제거
print("요소 제거 후:", d)

# 요소 추가 (여러 개)
d.extend([1, 2, 3])  # 오른쪽 끝에 여러 요소 추가
d.extendleft([4, 5, 6])  # 왼쪽 끝에 여러 요소 추가, 추가되는 순서는 6, 5, 4가 됩니다.
print("여러 요소 추가 후:", d)

# 회전
d.rotate(1)  # 오른쪽으로 1만큼 회전
print("회전 후:", d)

# 요소 개수 세기
print("1의 개수:", d.count(1))

# 요소 제거
d.remove(1)  # 요소 1 제거
print("1 제거 후:", d)

# 덱 초기화
d.clear()
print("초기화 후:", d)

deque는 양쪽 끝에서 요소의 추가 및 제거가 빈번하게 발생하는 경우에 리스트보다 훨씬 효율적입니다. 예를 들어, 슬라이딩 윈도우, BFS(너비 우선 탐색) 알고리즘 구현 등에 자주 사용됩니다.

너비 우선 탐색(Breadth-First Search, BFS)은 그래프에서 가장 가까운 노드부터 차례대로 탐색하는 알고리즘입니다. deque를 사용하여 BFS를 구현하면, 큐(Queue)의 성질을 활용하여 각 노드를 효율적으로 탐색할 수 있습니다. 여기서는 간단한 그래프에 대한 BFS 구현 예를 들겠습니다.

예제 그래프

이 예제에서는 그래프를 인접 리스트 형태로 표현합니다. 그래프는 다음과 같이 주어진다고 가정합니다:

graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [2],
    5: [2],
    6: [3],
    7: [3]
}

이 그래프는 노드 1이 노드 2와 3에 연결되어 있고, 노드 2는 노드 4와 5에, 노드 3은 노드 6과 7에 각각 연결되어 있는 형태입니다.

BFS 구현

from collections import deque

def bfs(graph, start):
    # 방문한 노드를 추적하는데 사용할 딕셔너리
    visited = {node: False for node in graph}

    # BFS 큐 초기화 및 시작 노드 설정
    queue = deque([start])
    visited[start] = True

    # 큐가 빌 때까지 탐색 계속
    while queue:
        # 큐에서 하나의 노드를 추출
        node = queue.popleft()
        print(node, end=' ')

        # 추출된 노드에 인접한 노드들을 탐색
        for neighbor in graph[node]:
            if not visited[neighbor]:
                # 방문하지 않은 인접 노드를 큐에 추가하고 방문 처리
                queue.append(neighbor)
                visited[neighbor] = True

# 그래프 정의
graph = {
    1: [2, 3],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [2],
    5: [2],
    6: [3],
    7: [3]
}

# BFS 실행
bfs(graph, 1)

이 코드는 graph 내에서 시작 노드 1부터 BFS를 수행합니다. BFS는 queue를 사용하여 레벨별로 노드를 탐색하고, 방문하지 않은 인접 노드를 큐에 추가합니다. 각 노드가 큐에서 추출될 때, 해당 노드는 방문 처리되고 그 노드의 번호가 출력됩니다. 이 방식으로 모든 노드를 너비 우선 순서대로 방문할 수 있습니다.

C언어

#define _CRT_SECURE_NO_WARNINGS 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

int main(){
    char a[100];
    char b[100];
    int c;

    // gets() 예제: 보안상 사용을 권장하지 않음.
    // gets(a); // 띄어쓰기 포함 한 줄 전체를 입력 받음

    // fgets() 사용 예제: 안전하게 한 줄 입력 받기
    printf("fgets()로 입력: ");
    fgets(a, sizeof(a), stdin); // stdin에서 최대 sizeof(a)-1 글자를 읽어 a에 저장

    // scanf() 사용 예제: 공백 전까지 문자열 입력 받기
    printf("scanf()로 문자열 입력: ");
    scanf("%s", b); // 공백, 탭, 개행 문자 전까지만 입력 받음
    getchar(); // scanf() 뒤에 남은 개행 문자 제거

    // getchar() 사용 예제: 한 문자 입력 받기
    printf("하나의 문자 입력: ");
    c = getchar(); // 한 문자 입력 받기

    printf("fgets()로 입력받은 문자열: %s\n", a);
    printf("scanf()로 입력받은 문자열: %s\n", b);
    printf("getchar()로 입력받은 문자: %c\n", c);

    return 0;
}

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드(왼쪽 자식과 오른쪽 자식)를 가질 수 있는 트리 구조입니다. 이진 트리는 다양한 형태가 있으며, 특히 이진 탐색 트리(BST), 균형 이진 트리(AVL 트리, 레드-블랙 트리 등), 힙(최소 힙, 최대 힙) 등이 자주 사용됩니다. 이진 트리는 효율적인 탐색과 정렬, 데이터 조직화에 유용하게 사용됩니다.

큐 (Queue)

큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out) 특성을 가진 자료구조입니다. 큐는 데이터를 임시 저장하는 데 사용되며, 대기열 관리, 너비 우선 탐색(BFS) 알고리즘, 캐시 구현 등에 활용됩니다. 큐는 일반적으로 enqueue 연산으로 데이터를 추가하고, dequeue 연산으로 데이터를 제거합니다.

우선순위 큐 (Priority Queue)

우선순위 큐는 각 요소가 우선순위와 함께 큐에 추가되며, 높은 우선순위를 가진 요소가 먼저 제거되는 자료구조입니다. 이는 일반 큐의 FIFO 특성과는 다르게, 요소의 우선순위에 따라 순서가 결정됩니다. 우선순위 큐는 힙을 사용하여 구현할 수 있으며, 다익스트라 알고리즘, 허프만 코딩, 이벤트 기반 시뮬레이션 등에 사용됩니다.

덱 (Deque)

덱(deque)은 양쪽 끝에서 데이터를 추가하거나 제거할 수 있는 자료구조로, Double-Ended Queue의 약자입니다. 덱은 스택과 큐의 기능을 합친 형태로 볼 수 있으며, LIFO(Last In First Out) 스택 연산과 FIFO 큐 연산 모두 가능합니다. 덱은 슬라이딩 윈도우, 팰린드롬 검사, 스크롤 구현 등 다양한 상황에서 사용될 수 있습니다.

이러한 자료구조들은 알고리즘과 소프트웨어 개발에서 데이터를 효율적으로 관리하고 조작하는 데 필수적인 요소입니다. 각각의 특성과 용도를 이해하는 것은 복잡한 문제를 해결하는 데 중요한 역할을 합니다.

저작자표시

'알고리즘 > 코테 준비' 카테고리의 다른 글

코테준비 - 우선순위 큐 (1)	2024.03.22
코테 준비 - 그래프 1 (1)	2024.03.22
코테준비 - 분할정복 (1)	2024.03.22
코테 준비 - 구현 1 (0)	2024.03.22
코테 준비 - DP 2 실버 1 까지 (0)	2024.03.21

현재글코테 대비 python, c 대강 정리

인공지능, 자율주행에 관심있는 공대생의 일기장...?

Today :
Yesterday :

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30

공대생 도전 일지