https://www.acmicpc.net/problem/20206 20206번: 푸앙이가 길을 건너간 이유 첫째 줄에는 정수 A, B, C (-10,000 ≤ A, B ≤ 10,000, -100,000 ≤ C ≤ 100,000)가 주어진다. 해당 숫자들은 좌표 평면 상에서 Ax+By+C=0 형태로 표현되는 푸앙이가 지나가는 직선 상의 경로을 나타낸다. (단 www.acmicpc.net # 조건 x축과 y축과 평행한 직사각형 형태로 이루어진 위험지역 푸앙이는 직선 상의 경로를 따라 흑석동을 통과 푸앙이가 위험 지역을 지나가는지 여부를 알아내어, 해당 지역을 지나가지 못하도록 조치를 취하라 A,B,C (-10,000 expression2 and abs(expression1) < abs(expression2..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net # 조건 모든 사람들은 최대 6단계 이내로 서로 아는 사람으로 연결 케빈 베이컨 게임은 임의의 두사람이 최소 몇 단계 만에 이어질 수 있는지 계산 유저의 수 N(0

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net # 조건 크기가 2^N x 2^N 배열을 Z모양으로 탐색 왼쪽위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래로 탐색하면 된다. N>1 인 경우, 배열을 크기가 2^(N-1) x 2^(N-1)로 4등분 한 후 재귀적 순서대로 방문 r행 c열을 몇 번쨰로 방문하는지 출력 # 접근 방법 및 Solution 2^(N-1) x 2^(N-1) 로 나눠서 생각 해준다. 결국 1, 2, 3, 4, 분면에 따..

목차 최소 신장 트리 Prim 알고리즘 KRUSKAL 알고리즘 1. 최소 신장 트리(Minimum Spanning Tree) 그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 간선의 가중치의 합이 최소여야 한다. 사이클이 포함되어서는 안된다. 사용 사례 통신망, 도로망, 유통망에서 길이, 구축 비용, 전송 시간 등을 최소로 구축하려는 경우 표현 그래프 간선들의 배열 인접 리스트 부모 자식 관계와 가중치에 대한 배열 트리 2...

지금까지 여러 자료 구조를 알아보았고, 아마 이번에 배우는 그래프가 마지막일 것이다! 목차 그래프란? 그래프 유형 그래프 표현 서로소 집합 1. 그래프란? 그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계를 표현 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조 IVI : 정점의 개수 IEI : 그래프에 포함된 간선의 개수 무향 그래프 - IVI 개의 정점을 가지는 그래프는 최대 IVI (IVI - 1) / 2 간선이 가능 유향 그래프 - IVI 개의 정점을 가지는 그래프는 최대 IVI (IVI - 1) 간선이 가능 선형 자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이 2. 그래프 유형 1. 무향 그래프..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net # 조건 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성 0

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net # 조건 사무실은 1x1 크기의 정사각형으로 나누어져 있는 N x M 크기의 직사각형으로 나타낼 수 있다. 총 K개의 CCTV가 있는데 5종류가 존재 한 쪽 방향 서로 반대방향인 두 방향 - 상하, 좌우 서로 직각인 두 방향 - 좌상, 좌하, 우상, 우하 세 방향 감시 네 방향 검사 검사할 수 있는 방향에 있는 칸 전체를 감시 가능 벽은 통과하지 못한다. 지도에서 0은 빈 칸, 6은 벽..

https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net # 조건 자연수 A를 B번 곱한 수를 알고 싶은데, 구하려는 수가 매우 커질 수 있으므로 C로 나눈 나머지를 구하여라 A, B, C는 2,147,483,647 이하의 자연수이다. # 접근 방법 일반적인 곱셈을 활용한다면 시간초과가 날 것이다. 분할 정복을 이용하여 지수를 짝수와 홀수 일 때를 나눠준다. 짝수인 경우 - 지수가 10이라면 A^10 = A^5 * A^5 홀수인 경우 A^5 = A^2 * A^2 * A b가 홀수 = 2^9 == 2^4 2^4 2 즉 ..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com # 조건 N x N 모양의 지역에 디저트 카페가 모여있다. 칸의 숫자는 디저트의 종류를 뜻하며 카페들 사이에는 대각선 방향으로만 이동 가능 대각선으로 카페 투어를 떠난 후 다시 처음 카페로 돌아오면 된다. 이때, 한 번 먹은 종류의 디저트 카페는 갈 수 없고, 왔던 길도 돌아갈 수 없다. # 접근 방법 #1 dfs dfs를 이용하여 사각형을 그려주며 탐색할 수 있다. 회전 방향을 정하고, 카페와 디..