[SISS/C언어 스터디] 25-1학기 8주차 스터디 - 그래프, 추가 과제

[SISS/C언어 스터디] 25-1학기 8주차 스터디 - 그래프, 추가 과제

: 8주차 (5/19~5/25) 프로그래머스 지정 1문제 (그래프)- https://school.programmers.co.kr/learn/courses/30/lessons/49190

 

방의 개수

---

# 방의 개수.py

def solution(arrows):
    # 8방향 벡터(북쪽부터 시계 방향)
    dx = [-1, -1, 0, 1, 1, 1, 0, -1]
    dy = [0, 1, 1, 1, 0, -1, -1, -1]

    # 방문 노드, 간선 저장 집합
    node_visited = set()
    edge_visited = set()

    # 시작 위치
    x, y = 0, 0
    node_visited.add((x, y))

    answer = 0

    for dir in arrows:
        # 방향 당 2번 이동 (중간 노드로 교차점 인식)
        for _ in range(2):
            nx = x + dx[dir]
            ny = y + dy[dir]

            # 간선 정보(양방향이므로 정렬)
            edge = ((x, y), (nx, ny))
            edge_rev = ((nx, ny), (x, y))

            # 기방문 노드가 새로운 간선을 지난 경우
            if (nx, ny) in node_visited and edge not in edge_visited:
                answer += 1  # 새로운 방(도형)이 생김

            # 노드 및 간선 방문 표시
            node_visited.add((nx, ny))
            edge_visited.add(edge)
            edge_visited.add(edge_rev)

            # 현재 위치 갱신
            x, y = nx, ny

    return answer

방의 개수

 

1629

---

• 분할정복

→ https://www.acmicpc.net/problem/1629

// 1629.c

#include <stdio.h>

long long a, b, c, k;

// 거듭제곱 (a^b % c)
long long power(long long b) {
    // 지수가 0이면 1
    if (b == 0) return 1;

    // 지수가 1이면 a % c 반환
    if (b == 1) return a % c;

    // b를 2로 나누도록 재귀 이용
    k = power(b / 2) % c;

    // 지수가 짝수일 경우 - (a^(b/2))^2 % c
    if (b % 2 == 0) return (k * k) % c;

    // 지수가 홀수일 경우 - (a^(b/2))^2 * a % c
    return ((k * k) % c * a) % c;
}

int main(void) {
    scanf("%lld %lld %lld", &a, &b, &c);
    printf("%lld\n", power(b));

    return 0;
}