코후닝

알고리즘 분류: 자료 구조, 해시를 사용한 집합과 맵 문제 링크: https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 【 풀이 】 C++ STL인 map 자료구조를 이용하면 쉽게 해결할 수 있다. mapm 위와 같이, key와 value를 pair 형식으로 저장하는 자료구조이다. 파이썬을 공부했다면 딕셔너리를 생각하면 되는데, 딕셔너리처럼 키를 통해 키에 해당하는 값에 접근할 수 있다. 즉 찾고자 하는 사이트 주소를 ..

알고리즘 분류: 구현, 브루트포스 알고리즘 문제 링크: https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 【 풀이 】 주어진 배열요소 모두를 일정한 높이로 만드는 데 걸리는 최소 시간과 땅의 높이를 구하는 문제이다. 이 문제는 브루트포스 알고리즘을 이용하여 생각보다 간단히 해결할 수 있다. 즉 3중 for 문으로, 첫 for문은 모든 높이의 경우에 대해서, 두번째/세번째 for문은 주어진 배열에서 검증하면 된다. remove(배열 요소가 설정된..

알고리즘 분류: 구현, 문자열 문제 링크: https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 【 풀이 】 앞으로 읽으나 뒤로 읽으나 똑같은 문자열인지 판단하는 문제이다. 문자열의 절반까지만 반복을 설정하고, 앞과 뒤가 같은 문자이면 횟수를 카운트하면 된다. 그 횟수가 문자열의 절반과 크기가 같다면 '1'을 출력하고, 아니라면 '0'을 출력한다. 【 코드 】 #include #include using namespace std; int main(void) { string s; cin >> s; int c..

알고리즘 분류: 이분 탐색, 매개 변수 탐색 문제 링크: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 【 풀이 】 2805번과 비슷하게 구할 수 있는 문제이다. 2023.05.06 - [백준 [BAEKJOON]] - [백준] 2805번: 나무 자르기 [C++] [백준] 2805번: 나무 자르기 [C++] 알고리즘 분류: 이분 탐색, 매개 변수 탐색 문제 링크: https://www.acmicpc.net/probl..

알고리즘 분류: 이분 탐색, 매개 변수 탐색 문제 링크: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 【 풀이 】 자를 수 있는 나무의 마지노선 길이를 구하는 문제이다. 이분 탐색으로 구하면 쉽게 해결할 수 있다. start(최소 길이, 즉 0), end(최대 길이, 즉 배열에서의 최댓값) 두 변수를 이용해서 mid(중간값)를 설정하고 배열 요소에서 mid를 뺀 값을 모두 더한 값을 저장한다. 모두 더..

알고리즘 분류: 수학 문제 링크: https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 【 풀이 】 N! 의 뒤에서부터 처음 0이 아닌 수가 나올 때까지 0의 개수를 구하는 문제이다. 딱 보자마자 N! 을 구하여 저장한 후, 문자열로 변환시킨 후 맨뒤에서부터 0의 개수를 세는 알고리즘을 생각했다.그러나 N이 20 언저리를 넘어가는 순간부터 답이 이상해진다. 이는 N의 범위가 500까지이므로 파이썬이 아닌 이상 가장 큰 자료형으로도 N! 을 담을 수 없기 때문이다. (저장한 값이 중간에 잘려버림) 따라서 N! 을 소인수 분해하여 해결해야..