코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - 소수 (백준 2581)

문제 출처: https://www.acmicpc.net/problem/2581

 

2581번: 소수

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.  단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

www.acmicpc.net

풀이

에라토스테네스의 체를 이용하면 되고, 20행에서 최솟값을 비교하는 min변수를 사용함으로써 소수의 최솟값을 구하기 위해 또 m부터 n까지 수 중 가장 작은 수를 구하기 위해 반복문을 돌려야 하는 불필요 연산을 방지할 수 있습니다. 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
int arr[10001];
int main()
{
    int m, n, sum = 0;
    arr[0] = 1, arr[1] = 1;
    for (int i = 2; i <= 10001; i++)
        for (int j = i * i; j <= 10001; j += i)
        {
            if (arr[j] == 1)continue;
            arr[j] = 1;
        }
    cin >> m >> n;
    int min = 10001;
    for (int i = m; i <= n; i++) {
        if (arr[i] == 0)
        {
            sum += i;
            if (min > i)min = i;
        }
    }
    if (sum) {
        cout << sum << endl;
        cout << min << endl;
    }
    else
        cout << -1 << endl;
 
    return 0;
}
 cs

 

결과

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 1292  (0) 2021.03.25
코딩 테스트 준비 1단계 기본기 - 백준 1978  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2693  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2609  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2309  (0) 2021.03.24

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - 쉽게 푸는 문제 (백준 1292)

문제 출처: https://www.acmicpc.net/problem/1292

 

1292번: 쉽게 푸는 문제

첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다.

www.acmicpc.net

풀이

처음에 약간 헷갈렸던 게 a,b가 각각 1,1000일 때 길이가 1000인 배열만으로 충분할까? 였는데 

즉, 1, 22, 333, 4444  -- -- -식으로 가다보면 배열길이 1000이 한참 모잘라서 문제가 될 것 같았지만

되게 멍청한 생각이었던게.. a,b가 1,1000이면 첫번째 부터 1000번째 인덱스 까지만 구하면 되므로 상관이 없습니다.

14행을 주석처리 하고 제출하면 인덱스 범위를 초과할 수 있으므로 fail이 뜰 수 있으니 이것만 조심하면 될 것 같습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;
int arr[1001];
int main()
{
    int a, b, sum = 0, k = 0;
    cin >> a >> b;
    int i, j = 0;
    for (i=1; i <=1000; i++)
    {
        for (j=1; j <=i; j++)
        {
            arr[k] = i;
            if (k >= 1000)break;
            k++;
        }
    }
    for (int i=a-1;i<b;i++)
    {
        sum += arr[i];
    }
    cout << sum << endl;
    return 0;
}
 cs

 

결과

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 2581  (0) 2021.03.25
코딩 테스트 준비 1단계 기본기 - 백준 1978  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2693  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2609  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2309  (0) 2021.03.24

 

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - 소수 찾기 (백준 1978)

문제 출처: https://www.acmicpc.net/problem/1978

 

1978번: 소수 찾기

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

www.acmicpc.net

풀이

초보자 입장에서 풀고 한 단계 더 나아가 소수찾기 알고리즘 원픽 에라토스테네스의 체를 이용하여 풀어보았습니다.

결과적으로 30행에서 반복문의 arr[j]는 모두 소수가 아니기 때문에 이를 체크 해줌으로써 쉽게 소수를 걸러낼 수 있습니다.

에라토스테네스의 체에 대한 개념은 아래 링크를 통해 학습할 수 있습니다.

https://jow1025.tistory.com/12

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
using namespace std;
int arr[1001];
int main()
{
    int t, i, num, cnt = 0;
    cin >> t;
    while (t--)
    {
        cin >> num;
            //솔루션1: 입력범위가 작으면 이대로 풀자.
        /*if (num > 1) {
            for (i = 2; i < num; i++)
            {
                if (num % i == 0)
                    break;
            }
            if (i == num)cnt++;
        }*/
 
        //솔루션 2: 입력범위가 크다싶으면 그냥 에라토스테네스의체 쓰자.
 
        //0과 1은 소수가 아니므로 1값으로 체크
        arr[0] = 1, arr[1] = 1;
        for (int i = 2; i < 1001; i++)
        {
            for (int j = i * i; j < 1001; j += i)
            {
                //소수가 아닌 경우 체크
                 arr[j] = 1;
            }
        }
        if (arr[num] == 0)cnt++;
    }
    cout << cnt << endl;
    return 0;
}
 cs

 

결과

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 2581  (0) 2021.03.25
코딩 테스트 준비 1단계 기본기 - 백준 1292  (0) 2021.03.25
코딩 테스트 준비 1단계 기본기 - 백준 2693  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2609  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2309  (0) 2021.03.24

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - N번째 큰 수 (백준 2693)

문제 출처: https://www.acmicpc.net/problem/2693

 

2693번: N번째 큰 수

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 배열 A의 원소 10개가 공백으로 구분되어 주어진다. 이 원소는 1보다 크거나 같고, 1,000보

www.acmicpc.net

풀이

이런 간단한 문제를 풀 때는 배열을 선언하여 매 tc마다 memset으로 0으로 초기화 해주기, comp 함수로 내림차순 정렬하기, 벡터를 이용하여 sort함수에

greater<int>()인자로 내림차순 정렬하기 등 간단한 연습을 해두면 좋을 것 같습니다. 

처음 제출한 코드가 52ms가 나오길래 10,11행을 추가하고 20행 endl을 '\n'으로 바꿔주니 0ms가 나왔습니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
bool comp(const int a, const int b)
{
    return a > b;
}
using namespace std;
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    int t;
    cin >> t;
    int arr[10];
    for (int i = 0; i < t; i++)
    {
        for (int j = 0; j < 10; j++)
            cin >> arr[j];
        sort(arr, arr + 10, comp);
        cout << arr[2] << '\n';
    }
    return 0;
}
 cs

 

결과

 

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 1292  (0) 2021.03.25
코딩 테스트 준비 1단계 기본기 - 백준 1978  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2609  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2309  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 10870  (0) 2021.03.24

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - 최대공약수와 최소공배수 (백준 2609)

문제 출처: https://www.acmicpc.net/problem/2609

 

2609번: 최대공약수와 최소공배수

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

www.acmicpc.net

풀이

최대공약수는 유클리드 호제법으로 구하고 최소공배수는 n과 m을 곱한 값을 최대공약수로 나눈값입니다.

유클리드 호제법은 유용하고 코드가 간단하니 외워두시는 게 좋을 것 같습니다.

 

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;
int GCD(int a, int b);
int main()
{
    int n, m;
    cin >> n >> m;
    //최대공약수->유클리드 호제법
    //최대공배수-> (n*m)/최대공약수
    int gcd = GCD(n, m);
    cout << gcd << endl;
    cout << (n * m) / gcd << endl;
    return 0;
}
int GCD(int a, int b)
{
    int c;
    while (b)
    {
        int c = a % b;
        a = b;
        b = c;
    }
    return a;
}
 cs

 

결과

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 1978  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2693  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2309  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 10870  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2460  (0) 2021.03.23

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - 일곱 난쟁이 (백준 2309)

문제 출처: https://www.acmicpc.net/problem/2309

 

2309번: 일곱 난쟁이

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

www.acmicpc.net

풀이

예전에 풀면서 다음에 다시 한번 풀어봐야 겠다고 생각해놨던 문제인데 이번에 다시 풀게 되었습니다.

그때나 지금이나 문제를 보자마자 무작위로 7개씩 조합해서 100이 되는지를 조사하면 되겠다고 접근하다가 갑자기

정신을 차리고(왜 그때랑 똑같이 삽질하는 거지...) 풀이를 생각해 냈습니다.

9명의 난쟁이중 7명의 키를 조합해서 100이 되는지를 검증하는 것 보다(반복문7개쓸건가??..) 

9명 난쟁이의 키 총 합에서 두 명의 키를 뺀 값이 100이 될 때 그 두명을 제외시켜주는 것이  좋습니다.

단, 주의 해야할 점은 2중 반복문 안에서 두명을 검출하고 반복문을 탈출해야합니다.

2중 반복문으로 2명을 검출하고 break문을 걸어주지 않으면 101로 설정 해 둔 두 난쟁이의 키값이 또다른 100을 찾는 7명의 키조합 연산에 사용되어 7명이 구해지지 못하는 경우가 발생할 수도 있습니다.

실제로 아래 코드에서 24행과 28행을 주석처리하면 틀리게 됩니다.

 

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<algorithm>
using namespace std;
int arr[9];
int main()
{
    int i,j, sum = 0;
    for (int i = 0; i < 9; i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    //총합에서 2개의 난쟁이 키를 뺀 값이 100일 때 그 2명 제외
    // 키가 100을 넘지않으므로 2개 검출 한 난쟁이의 키를 -1 or 101로 조절
    for ( i = 0; i < 9; i++)
    {
        for ( j = 0; j < 9; j++)
        {
            if (i != j)
            {
                if (sum - arr[i] - arr[j] == 100)
                {
                    arr[i] = 101, arr[j] = 101;
                    break;
                }
            }
        }
        if (arr[i] == 101 && arr[j] == 101)break;
    }
    sort(arr, arr + 9);
    for (int i = 0; i < 7; i++)
        cout << arr[i] << endl;
    return 0;
}
 cs
 
 
  

 

결과

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 2693  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2609  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 10870  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2460  (0) 2021.03.23
코딩 테스트 준비 1단계 기본기 - 백준 10818  (0) 2021.03.23

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - 피보나치수 5 (백준 10870)

문제 출처: https://www.acmicpc.net/problem/10870

 

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가

www.acmicpc.net

풀이

일반적인 풀이로 풀고 예전에 피보나치 최적화 관련 글을 업로드 했던 적이 있어서(https://jow1025.tistory.com/101)

dp로도 풀어보았습니다. (벌써 업로드 한지 1년이 넘었네요 시간 참;;;)

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
using namespace std;
int dp[21];
int func(int n);
int func_dp(int n);
int main()
{
    int n;
    cin >> n;
    /* func: 일반적인 풀이
       func_dp: dp를 이용한 풀이*/
    //cout << func(n) << endl;
    cout << func_dp(n) << endl;
 
    return 0;
}
//일반적인 풀이
int func(int n)
{
    if (n == 0) return 0;
    if (n == 1 || n == 2)return 1;
    return func(n - 1) + func(n - 2);
}
int func_dp(int n)
{
    if (n == 0) return 0;
    if (n == 1 || n == 2)return 1;
    //값이 담겨있으면 바로 반환
    if (dp[n] != 0)
        return dp[n];
    return dp[n] = func_dp(n - 1) + func_dp(n - 2);
 
}
 
 cs

 

결과

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 2609  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2309  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 2460  (0) 2021.03.23
코딩 테스트 준비 1단계 기본기 - 백준 10818  (0) 2021.03.23
코딩 테스트 준비 1단계 기본기 - 백준 3460  (2) 2021.03.23

 

코딩테스트 대비를 위해 도움이 될만한 문제 추천 블로그가 있어서 이 단계대로 코테를 준비합니다.

참조 사이트: http://covenant.tistory.com/224

 

코딩테스트 대비를 위한 백준 문제 추천

코딩테스트 대비를 위한 백준 문제 추천 끝 없는 훈련만이 실전에서 흐트럼없이 정답을 향해서 움직일 수 있습니다. (Photo by Specna Arms on Unsplash) 작년 한 해 수많은 코딩테스트를 직접 경험하고

covenant.tistory.com

Part 1 준비운동 - 지능형 기차2 (백준 2460)

문제 출처: https://www.acmicpc.net/problem/2460

 

2460번: 지능형 기차 2

최근에 개발된 지능형 기차가 1번역(출발역)부터 10번역(종착역)까지 10개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다.

www.acmicpc.net

풀이

한번의 연산(타고 내림) 후 현재 기차 내부의 총원을 구하기 위한 num변수와 10회 연산 중에서 가장 많은 기차 내부의 인원을 구하기 위한 max변수를 선언하여

가볍게 풀 수 있습니다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int main()
{
    int in, out;
    int max = 0, num = 0;
    //max: 기차에 가장많이 있는 사람 판별
    //num: 기차에 있는 사람의 수
    for (int i = 0; i < 10; i++) {
        cin >> out >> in;
        num = num + (in - out);
        //한번 내리고 타고 나서 사람 수 파악
        if (num > max)
            max = num;
    }
    cout << max << endl;
    return 0;
}
 cs

 

결과

저작자표시

'문제풀이(BOJ)' 카테고리의 다른 글

코딩 테스트 준비 1단계 기본기 - 백준 2309  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 10870  (0) 2021.03.24
코딩 테스트 준비 1단계 기본기 - 백준 10818  (0) 2021.03.23
코딩 테스트 준비 1단계 기본기 - 백준 3460  (2) 2021.03.23
코딩 테스트 준비 1단계 기본기 - 백준 2501  (0) 2021.03.23

+ Recent posts

티스토리툴바