열이의 개발블로그

https://www.acmicpc.net/problem/2866 2866번: 문자열 잘라내기 첫 번째 줄에는 테이블의 행의 개수와 열의 개수인 R과 C가 주어진다. (2 ≤ R, C ≤ 1000) 이후 R줄에 걸쳐서 C개의 알파벳 소문자가 주어진다. 가장 처음에 주어지는 테이블에는 열을 읽어서 문자 www.acmicpc.net 문제 분석 R개의 행과 C개의 열로 이루어진 테이블에서 열을 기준으로 단어를 만들어 총 R의 길이를 갖는 C개의 단어를 만든 후 단어들의 중복 여부를 확인한다. 처음에는 동일한 문자열이 존재하지 않는 입력이 주어지고 다음 연산부터는 가장 위의 행을 지운, 즉 단어의 첫 번째 문자를 없앤 단어들의 중복 여부를 판단한다. 단어들 중 중복이 없다면 count를 1 증가, 중복이 있다면..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 문제 분석 예은이의 위치에 따라 수색범위 안에서 방문할 수 있는 지역을 모두 탐색한 뒤, 그 지역에서 얻을 수 있는 아이템들의 합을 구하는 문제이다. 플로이드-워셜 대표적인 문제라고 볼 수 있을 것 같다. [플로이드-워셜 알고리즘] 하지만 알고리즘 분류를 보기 전에는 그래프 탐색만으로 충분히 풀 수 있어 보여서 그래프 탐색을 이용한 풀이를 작성하고자 한다. 우선, 모든 노드를 탐색하면서 그 노드에서 출..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 분석 N을 자기 자신보다 작거나 같은 제곱수들의 합으로 몇 개의 제곱수를 더해야 하는지 나타내는 문제 13을 예로 들면 13 = 3² + 2²이므로 2가 출력된다. 핵심은 자기 자신보다 작은 제곱수 중 가장 큰 제곱수를 빼면서 개수를 세면 된다. 하지만 가장 큰 제곱수를 뺀 뒤 또 제곱수를 찾아 빼는 연산을 반복한다면 시간 초과가 날 것이다. 다이나믹 ..

https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 분석 단순 N 페이지까지 반복하면서 페이지를 문자열로 변환 후 각 페이지에 존재하는 숫자만큼 등장 횟수를 누적하기가 기본적인 알고리즘일테지만 이 문제의 N의 범위는 10억 이하이기 때문에 시간 초과(시간 복잡도: O(n²))가 나오게 된다. 수학적인 접근이 필요한데 이는 백준 사이트의 최백준님의 자료를 참고하여 해결했다. 우선 각 자릿수 별로 등장 횟수를 쪼개서 생각해야 한다. 위의 자료에서는 1~N 페이지가 아닌 A~B 페이지를 기준으로 설명하였기 때문에 ..

https://www.acmicpc.net/problem/2417 2417번: 정수 제곱근 정수가 주어지면, 그 수의 정수 제곱근을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 분석 문제 그대로 정수가 주어지면, 그 정수의 제곱근을 구하는 문제이다. n의 범위가 (0 ≤ n < 2⁶³)이므로 범위가 넓기 때문에 하나하나 다 탐색하여 제곱근을 찾기에는 시간이 부족하다. 그렇기 때문에 이분 탐색 알고리즘을 사용하여 시간을 줄여 문제를 해결하자 코드 더보기 n = int(input()) start, end = 0, n result = 0 while start

https://www.acmicpc.net/problem/4158 4158번: CD 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 상근이가 가지고 있는 CD의 수 N, 선영이가 가지고 있는 CD의 수 M이 주어진다. N과 M은 최대 백만이다. 다음 줄 www.acmicpc.net 문제 분석 상근이와 선영이가 가지고 있는 CD의 수는 각각 N, M개이며 이는 최대 1,000,000(백만)이다. 처음엔 상근이가 가지고 있는 CD와 선영이가 가지고 있는 CD를 set 자료구조를 활용하여 교집합을 구하면 풀릴 것이라고 생각하였지만 입력 범위가 커 시간 초과가 났다. 풀이 방법은 다양하겠지만 3개의 풀이 방법을 설명하려고 한다. 1. set 자료구조를 활용하여 in을 통한 개수..

2022.01.02 가입 후 4일만에 실버 5 달성 2022.01.19 실버 4 달성 2022.01.21 실버 3 달성 2022.02.01 실버 2, 레이팅 2 달성 2022.02.22 실버 1 달성 2022.05.24 골드 5 달성 2022.08.10 골드 4 달성 2022.08.19 골드 3 달성 2022.09.23 골드 2 달성 2022.10.27 골드 1 달성 2022.11.08 500문제 SOLVED

https://www.acmicpc.net/problem/14264 14264번: 정육각형과 삼각형 첫째 줄에 정육각형 한 변의 길이 L이 주어진다. (1 ≤ L ≤ 1,000,000, L은 정수) www.acmicpc.net 문제 분석 위의 그림은 같이 정육각형에 각 다른 3개의 대각선을 그렸을 때 4개의 삼각형이 나오는 경우 중 가장 작은 삼각형이 최대일 때 나오는 경우이다. 빨간색으로 표시된 삼각형은 정삼각형이고 정삼각형의 넓이 공식을 이용하면 쉽게 해결할 수 있다. 코드 더보기 #include #include int main(){ double l; scanf("%lf", &l); printf("%.9lf", sqrt(3)*pow(l,2)/4); }

https://www.acmicpc.net/problem/2577 2577번: 숫자의 개수 첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다. www.acmicpc.net 문제 분석 세 자리 수 세 개를 입력한 뒤 모두 곱한 후 나온 수가 0부터 9까지의 수를 몇 번씩 쓰였는지를 나타내는 문제이다. 코드 진행 방향 0부터 9까지 쓰인 개수를 담을 배열을 만든 뒤 입력받은 수들의 곱을 10씩 나누어가며 나머지를 계산해 나머지의 배열 순서에 값을 하나씩 더해준다. 코드 더보기 #include int main(){ int a, b, c, result; int arr[10]={0}; scanf("%d", &a); scanf("..

https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 분석 정렬의 문제로 보여진다. 하지만 정렬로 푸는 방법과 배열을 한 번 돌면서 최소와 최대를 골라내는 방법의 시간 차이가 조금 있었기 때문에 최소와 최대를 각각 구하는 방법으로 풀었다. 코드 진행 방향 n개의 배열을 생성한 뒤 배열을 차례로 입력받고 첫 번째로 입력받은 배열의 수를 max, min에 넣어준다. 그 후 배열의 수가 max보다 크면 max를 바..