이게 맞나? 싶다

선형 탐색 = i번째 상태를 탐색한 후 다음 i+1번째 탐색 상태가 한가지일 때 선형 탐색법 = 순차 탐색, 이분 탐색 비선형 탐색 = i번째 상태 탐색 후 다음 i+1번째 상태가 2개 이상일 때 ex) 트리, 그래프 비선형 탐색법 = DFS, BFS 1. 그래프의 구현 그래프의 구현은 크게 인접 행렬과 인접 리스트로 나눌 수 있다. 입력으로 정점(n), 간선(m)이 주어지고 m개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호와 가중치가 입력으로 주어질 때 1) 인접 행렬의 구현 2차원 배열을 이용해 표현한다. 최대 정점 수에 맞춰 2차원 배열을 선언하고 각 배열의 칸에 연결된 정보를 저장한다. 모든 정점을 탐색하는 데 O(nm) 인접행렬 소스코드 n, m = map(int, input().split())..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 풀이 # 최단거리이므로 큐 자료구조 사용 from collections import deque # 도시수, 도로수, 거리, 출발도시번호 입력 n,m,k,x = map(int, input().split()) # 각 도시가 어느 도시와 이어져있는지 표시를 위해 2차원 리스트 graph = [[] for _ in range(n+1..

https://www.acmicpc.net/problem/18406 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 풀이 n = input() # 숫자 입력받음 length = len(n) # 길이 구함 sum1, sum2 = 0, 0 # 왼쪽, 오른쪽 # 0~길이//2번 인덱스 값을 수로 바꿔 합 구함 for i in n[:length//2]: sum1 += int(i) # 문자열 길이//2~끝 인덱스 값을 수로 바꿔 합 구함 for i in n[length//2:]: sum2 += int(i) # 왼쪽 오른쪽 값이 같다면 if sum1==sum2: print..

https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 풀이 #include int main() { char str[6]; // 0을 입력시 종료 while (scanf("%s", str) && str[0] != '0') { int len = 0; int flag = 1; // 문자열의 길이 계산 while (str[len] != '\0') len++; // ex) 5자리 수일때 앞에서 두번째 자리까지만 보면 됨 for (int i = 0; i < len / 2; i..

https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 풀이 수식 풀이 (본인 풀이) #include int main() { int t, h, w, n; int room; scanf("%d", &t); // t만큼 반복 for (int i = 0; i < t; i++) { scanf("%d %d %d", &h, &w, &n);// 입력 // 꼭대기 층을 원하는 손님일 경우 if (n % h == 0 && h * w != n) room = ..

https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 풀이 #include int main() { int arr[8]; int flag = 3;// ascending=1, descending=2, mixed=3 // 8개 음계 입력 받기 for (int i = 0; i < 8; i++) { scanf("%d", &arr[i]); } // 첫번째 음계부터 차례로 비교 for (int i = 0; i < 8; i..

https://www.acmicpc.net/problem/2475 2475번: 검증수 컴퓨터를 제조하는 회사인 KOI 전자에서는 제조하는 컴퓨터마다 6자리의 고유번호를 매긴다. 고유번호의 처음 5자리에는 00000부터 99999까지의 수 중 하나가 주어지며 6번째 자리에는 검증수가 들 www.acmicpc.net 풀이 #include int main() { int arr[5]; int sum = 0;// 합 for (int i = 0; i < 5; i++) { scanf("%d", &arr[i]);// 각각 입력받음 arr[i] = arr[i] * arr[i];// 각각 제곱 sum += arr[i];// 모든 숫자 합 } printf("%d\n", sum % 10);// 나머지 출력 return 0; }

https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 #include #include int main() { int n, x;// n= 명령횟수, x = push X의 X해당 char command[6];// 명령어 int stack[10001] = {};// 스택에 대한 배열 scanf("%d", &n);// 명령 횟수 입력 // i = 초기값, j = 인덱스값 int i = 0, j = -1; while (i < n) { ..

https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 반복문 이용 #include int main() { int n; scanf("%d", &n); int fac = 1; for (int i = 1; i = 1) return n * fac(n - 1);// fac(10) = 10*fac(9) else return 1;//n이 0일때는 1 }

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 #include #include int main() { int k, n; scanf("%d", &k); int* arr = (int*)malloc(k * sizeof(int)); int sum = 0; int c = 0; for (int i = 0; i < k; i++) { scanf("%d", &n);// n 입력 if (n != 0) {//n이 0이 아닐..