순간을 기록으로

https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을..

문제 수 N개가 주어졌을 때 , i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하세요. 입력 첫째 줄에 수의 개수 N과 구해야 하는 횟수 N이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지의 합을 출력한다. 분석 데이터 갯수는 10만 개이고, 구간 합을 구해야 하는 횟수도 최대 10만 번이다. 즉 최악의 경우 시간 복잡도는 O(n^2). 연산이 10만^2번, 100억이 되어 100초가 걸린다. 제한시간이 0.5초이므로 단순히 이중 for문으로 문제를 풀 수 없다. 이 문제를 풀기 위해서는 구간합 알고리즘을 이용해야 ..

안녕하세요 루미너스입니다! 오늘은 프로그래머스 고득점 Kit 해시 문제를 풀어봤습니다. 문제 https://programmers.co.kr/learn/courses/30/lessons/42576# 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 첫 번째 풀이 - List 이용, 시간초과 import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { // 참가자 명단을..

안녕하세요 luminous13입니다. 이번에는 백준 수정렬하기1 2750번 문제를 풀어보도록 하겠습니다. 문제 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 데이터를 오름차순으로 정렬하는 문제입니다. 사실 정렬을 Arrays.sort()를 이용하여 쉽게 정렬할 수 있지만 이번에는 직접 정렬을 구현하면서 문제를 풀어보도록 하겠습니다. 여러 정렬 알고리즘 중 하나를 선택해야 합니다. 데이터 크기를 보니 최대 1,000이 올 수 있습니다. 데이터 크기가 크..

분석 * 이번 문제는 수 나열에서 부분 합을 여러번 구하는 문제다. * 배열의 구간 합을 구해야 될때에는 합 배열을 이용하면 시간복잡도를 O(n)에서 On(1)로 줄일 수 있다. * 합 배열 공식:S[i] = S[i-1] + arr[i] * [i,j] 구간 합 공식: S[j] - S[i-1] * 배열의 사이즈를 1 추가하여 인덱스가 1이 첫 번째 원소로 설정해야 합배열 첫 번째 원소도 규칙있게 구할 수 있다. * * 이번 문제에서 만약 합 배열을 이용하지 않고 이중 for문을 사용하면 수의 갯수*횟수이 연산횟수가 된다. * 100,000*100,000 = 10,000,000,000 이다. 즉 100억번 연산을 하게되고 시간은 100초가 소요될것이다. * 따라서 합배열을 사용해야하는 문제다. 수도코드 * ..

알고리즘의 성능 좋은 알고리즘이란 무엇일까? 상황에 따라 좋은 알고리즘에 대한 정의가 달라지겠지만 일반적으로 좋은 알고리즘이란 성능이 좋은 알고리즘이라고 할 수 있다. 그렇다면 알고리즘의 성능을 평가할 수 있는 지표는 무엇이 있을까? 알고리즘 성능을 평가할 수 있는 지표는 공간과 시간이 있다. 이 알고리즘이 수행하는데 얼마나 적은 메모리 공간을 차지하는가? - 공간 복잡도 이 알고리즘이 수행하는데 얼마나 빠른가? - 시간 복잡도 현대 기술이 발전과 함께 메모리 성능 발전도 이뤄지게 되었고, 따라서 상대적으로 성능 평가 지표 중 하나인 공간복잡도에 대한 중요성이 낮아졌다. 따라서 시간 복잡도(=얼마나 빠른가?)가 더 중요한 지표가 되었다. 그렇다면 알고리즘이 얼마나 빠른지, 즉 시간복잡도는 어떻게 알 수 ..

개요 알고리즘 문제를 풀다 보면 반복적인 규칙이 있는 문제가 있습니다. 이런 문제들은 재귀 함수를 이용해서 풀 수도 있고, 반복문을 이용해서 풀 수 있습니다. 대표적인 문제가 팩토리얼 문제입니다. 입력으로 순서가 주어지면 팩토리얼 값을 구하는 방법은 다음과 같이 재귀함수를 이용해서 풀 수 있고 반복문을 이용해서 풀 수 있습니다. 팩토리얼 문제를 푸는 2가지 방법 - 재귀, 반복문 public class Solution { public static int factorialUsingRecursion(int num) {// 재귀 if (num == 0) return 1; else return num * factorialUsingRecursion(num - 1); } public static int factor..

문제 숫자 N을 입력하면 원소의 갯수가 N개인 피보나치 수열을 출력하는 프로그램을 작성하세요 풀이1 - 재귀함수 이용하기 피보나치는 바로 앞 두 원소를 더해서 새로운 원소값을 설정합니다. 식으로 표현하면 다음과 같습니다. f(n) = f(n-2) + f(n-1) (단, n>=2, f(1)=1, f(2)=1) 따라서 첫 번째 원소나 두 번째 원소라면 재귀를 탈출하고 그게 아니라면 앞 두 원소를 더하는 과정으로 문제를 풀면 됩니다. 재귀함수는 보통 if-else구문으로 푸나 여기서는 if-elseif-else 구조로 문제를 풀겠습니다. 두 조건을 합춰 if-else로 만들어도 상관은 없습니다. import java.util.Scanner; public class Main { public static int ..