devBB 메모장

백준 온라인 저지(BOJ) 24444번 알고리즘 수업 - 너비 우선 탐색 1 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방www.acmicpc.net* 사용언어 : C언어, C++ 1. 문제graph 를 BFS(너비 우선 탐색)으로 탐색할 때 1번 정점부터 N번 정점까지 방문한 순서를 출력 (인접 정점은 오름차순으로 방문) 2. 풀이BFS 함수 구현은 문제에 적혀있는 의사 코드만으로 충분히 설명이 ..

백준 온라인 저지(BOJ) 24480번 알고리즘 수업 - 깊이 우선 탐색 2 https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 graph 를 DFS(깊이 우선 탐색)으로 탐색할 때 1번 정점부터 N번 정점까지 방문한 순서를 출력 (인접 정점은 내림차순으로 방문) 2. 풀이 앞서 풀어본 24479번 문제와 거의 유사한 코드로 구현하였..

백준 온라인 저지(BOJ) 24479번 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 graph 를 DFS(깊이 우선 탐색)으로 탐색할 때 1번 정점부터 N번 정점까지 방문한 순서를 출력 (인접 정점은 오름차순으로 방문) 2. 풀이 재귀적 접근을 활용하는 DFS 를 구현하여 풀면 됩니다. D..

백준 온라인 저지(BOJ) 1427번 소트인사이드 https://www.acmicpc.net/problem/1427 1427번: 소트인사이드 첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 배열이 아닌 숫자를 입력받고 각 자리수를 내림차순으로 정렬하여 출력 입력 N 은 1,000,000,000보다 작거나 같은 자연수 2. 풀이 n % 10 연산자를 활용하여 입력받은 숫자를 한 자리 씩 배열에 저장합니다. 이후 배열을 정렬한 뒤 출력하면 됩니다. 입력 N 은 최대 10억이므로 int 형 변수로 충분히 처리가 되고 자리수의 개수도 최대 10이므로 배열의 사이즈도 10이면 됩니다. ..

백준 온라인 저지(BOJ) 2884번 알람 시계 https://www.acmicpc.net/problem/2884 2884번: 알람 시계 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, www.acmicpc.net * 사용언어 : Python 파이썬 1. 문제 알람 시간 H, M 에서 45분을 앞당겼을 때의 시간을 출력 2. 풀이 입력받은 시간의 45분 전 시간을 24시간 표현 기준으로 출력하면 됩니다. 우선 M 에서 45를 뺍니다. 이 때 M 이 양수이면 그대로 H 와 M 을 출력합니다. (ex. 1시 50분 -> 1시 5분) 만약 M 이 음수이면 M 에 60을 더하..

백준 온라인 저지(BOJ) 14681번 사분면 고르기 https://www.acmicpc.net/problem/14681 14681번: 사분면 고르기 점 (x, y)의 사분면 번호(1, 2, 3, 4 중 하나)를 출력한다. www.acmicpc.net * 사용언어 : Python 파이썬 1. 문제 x, y 를 입력받고 어느 사분면에 속하는지 출력 (x, y 는 0 이 아닌 정수) 2. 풀이 if ~ else 문으로 케이스를 나눈 뒤 출력하면 됩니다. 처음에 if ~ else 안에 다시 if ~ else 를 넣어서 4개 케이스를 처리했다가 print 문이 4번 나오는게 싫어서 삼항 연산자를 사용하여 약간 간결하게 구현했습니다. (파이썬 삼항 연산자도 연습해볼 겸) 3. 코드 # 14681_사분면 # 312..

백준 온라인 저지(BOJ) 10989번 수 정렬하기 3 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 10,000 이하의 자연수 N 개(최대 10,000,000개)를 정렬한 결과를 출력 2. 풀이 정렬 대상의 범위(숫자)가 적을 경우 속도가 빠른 Counting Sort 를 이용하여 풀었습니다. 처음에는 과거에 계수 정렬을 배웠던 내용을 되짚어보면서 count 배열, 입력 배열, 정렬 배열 총 3개를 선언하고 풀어봤는데..

백준 온라인 저지(BOJ) 2753번 윤년 https://www.acmicpc.net/problem/2753 2753번: 윤년 연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력하는 프로그램을 작성하시오. 윤년은 연도가 4의 배수이면서, 100의 배수가 아닐 때 또는 400의 배수일 때이다. 예를 들어, 2012년은 4의 배수이면서 www.acmicpc.net * 사용언어 : Python 파이썬 1. 문제 연도가 주어졌을 때, 윤년이면 1, 아니면 0을 출력 윤년은 연도가 4의 배수이면서, 100의 배수가 아니어야 하지만 400의 배수는 윤년 2. 풀이 이러한 유형의 문제는 조건문의 순서를 잘 정하는 것이 중요합니다. 왜냐하면 반복되는 조건문(if ~ elif ~ elif ~ ... ~ else) 중 ..

백준 온라인 저지(BOJ) 9498번 시험 성적 https://www.acmicpc.net/problem/9498 9498번: 시험 성적 시험 점수를 입력받아 90 ~ 100점은 A, 80 ~ 89점은 B, 70 ~ 79점은 C, 60 ~ 69점은 D, 나머지 점수는 F를 출력하는 프로그램을 작성하시오. www.acmicpc.net * 사용언어 : Python 파이썬 1. 문제 시험 점수를 입력받고 점수 별로 등급을 출력 (ex. 90~100점은 A, 80~89 점은 B, ...) 2. 풀이 if ~ elif ~ else 문을 사용하여 등급을 출력합니다. 3. 코드 # 9498_시험 성적 # 31256KB40ms score = int(input()) if score >= 90: print('A') eli..

백준 온라인 저지(BOJ) 25305번 커트라인 https://www.acmicpc.net/problem/25305 25305번: 커트라인 시험 응시자들 가운데 1등은 100점, 2등은 98점, 3등은 93점이다. 2등까지 상을 받으므로 커트라인은 98점이다. www.acmicpc.net * 사용언어 : C언어, C++ 1. 문제 N 명의 시험 점수가 주어졌을 때 그 중 K 명이 상을 받는 경우 가장 낮은 사람의 점수(커트라인)를 출력 2. 풀이 N 개의 점수를 배열에 입력받고 정렬한 뒤 k 번째, 즉 index 로는 k - 1 자리에 있는 점수를 출력하면 됩니다. 크기가 1,000인 작은 사이즈의 문제라서 어떤 정렬을 사용해서 구현해도 충분히 통과할 수 있을 것 같습니다. 저는 시간복잡도가 nlogn ..