용용코딩

https://www.acmicpc.net/problem/1978

• 문제

• 문제풀이

처음에는 숫자를 입력받아 2부터 자기자신 전 까지 0으로 나누어 떨어지는 값을 제외하고 개수를 세어주면 소수의 개수가 된다.

두번째로는 에라토스테네스의 체를 사용했다. i번째 수열을 i로 설정했고 합성수를 0으로 만들어 0이 아니라면 개수를 세어주도록 하였다.

• 코드 1

using System.IO.Pipes;
using System.Text;

namespace ConsoleApp7
{
    internal class Program
    {      
        static void Main(string[] args)
        {    
            int N = int.Parse(Console.ReadLine());
            string[] arr = Console.ReadLine().Split();
            int cnt;
            int ans = 0;
            for(int i=0; i<N; i++)
            {
                cnt = 0;
                int num = int.Parse(arr[i]);
                if (num == 1) continue;
                for(int j = 2; j < num; j++)
                {
                    if(num%j==0) cnt++;
                }
                if (cnt == 0)
                {
                    ans++;
                }
            }
            Console.WriteLine(ans);
        }
    }
}

• 코드 2

using System.Text;

namespace ConsoleApp7
{
    internal class Program
    {
        public static StringBuilder sb = new StringBuilder();
        public static int count = 0;
        static void CalcPrime(int num)
        {
            int[] temp = new int[num + 1];
            for (int i = 2; i <= num; i++)
            {
                temp[i] = i;
            }
            for (int i = 2; i <= num; i++)
            {
                if (temp[i] == 0) continue;
                for (int j = i + i; j <= num; j += i)
                {
                    temp[j] = 0;
                }
            }
            if (temp[num] != 0)
            {
                count++;
            }
        }
        static void Main(string[] args)
        {         
            int N = int.Parse(Console.ReadLine());
            string[] arr = Console.ReadLine().Split();
            for(int i=0; i<N; i++)
            {
                int num = int.Parse(arr[i]);
                if (num == 1) continue;
                CalcPrime(num);
            }
            Console.WriteLine(count);
        }
    }
}

• 후기

항상 함수를 만들어보려고 하는데 생각보다 익숙치 않다.

https://www.acmicpc.net/problem/1978

• 문제

• 문제풀이

처음에는 숫자를 입력받아 2부터 자기자신 전 까지 0으로 나누어 떨어지는 값을 제외하고 개수를 세어주면 소수의 개수가 된다.

두번째로는 에라토스테네스의 체를 사용했다.

• 코드 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#define _CRT_SECURE_NO_WARNINGS

int main()
{
    int N;
    int arr[1000];
    int count;
    int d = 0;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        count = 0;
        scanf("%d",&arr[i]);
        if (arr[i] == 1) continue;
        for (int j = 2; j < arr[i]; j++) {
            
            if (arr[i] % j == 0) {
                count++;
            }
           
        }
        if (count == 0) {
            d++;
        }
    }
    printf("%d", d);
}

• 코드 2

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <math.h>
#define _CRT_SECURE_NO_WARNINGS

int a[1000001];
int number = 1000001;
void primeNumberSieve() {

	for (int i = 2; i <= number; i++) {
		a[i] = i;
	}

	for (int i = 2; i <= number; i++) {
		if (a[i] == 0) continue; 

		for (int j = 2 * i; j <= number; j += i) {
			a[j] = 0;
		}
	}

	
}
int main(void)
{

	
	int count = 0;
	int N;
		
	scanf("%d", &N);
	int input = 0;
	primeNumberSieve();
	for (int i = 1; i <= N; i++) {
		scanf("%d", &input);
		if (input == 1) continue;
		for (int i = 0; i < number; i++) {
			if (a[i] == input) {
				count++;
			}
		}

	}
	printf("%d", count);

}

• 후기

소수를 구하는 법을 알게되었다. 그럼 다수는 버려야하나? 약간 기찻길 문제

에라토스테네스의 체란?

• 소수를 판별하는 알고리즘.
• 소수들을 대량으로 빠르게 구할 수 있는 알고리즘이다.

에라토스테네스의 체의 원리

단일 숫자의 소수 여부를 확인하는 가장 기초적인 방법은 소인수분해를 통해 약수의 개수를 확인하는 것이다.
에라토스테네스의 체는 1부터 N까지의 소수를 알고 싶을 때 사용하기 좋은 방법으로 N보다 작은 자연수 K의 몫과 나머지 중 하나는 N의 제곱근보다 작거나 같다는 성질을 이용하는 것이다.
N의 제곱근보다 작은 수의 배수만 모두 확인하면 N까지 소수가 아닌 수를 전부 지울 수 있게 된다. 

대량으로 소수를 한번에 판별해야 할 경우 '에라토스테네스의 체'를 이용한다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
3. 2부터 시작하여 남아있는 수를 모두 출력한다.

에라토스테네스의 체

• C언어

#include <stdio.h>

int number = 100000;
int sieve[1000001];

void Sieve() {

    // 1. 배열을 생성하여 초기화한다.
    for(int i=2;i<=number;i++) {
        sieve[i] = i;
    }

    // 2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다.
    // (지울 때 자기자신은 지우지 않고, 이미 지워진 수는 건너뛴다.)
    for(int i=2;i<=number;i++) {
        if(sieve[i]==0) continue; // 이미 지워진 수라면 건너뛰기

        // 이미 지워진 숫자가 아니라면, 그 배수부터 출발하여, 가능한 모든 숫자 지우기
        for(int j=2*i;j<=number; j+=i) {
            sieve[j] = 0;
        }
    }

    // 3. 2부터 시작하여 남아있는 수를 모두 출력한다.
    for(int i=2;i<=number;i++) {
        if(sieve[i]!=0) printf("%d ", sieve[i]);
    }
}

int main(void) {
    Sieve();
    return 0;
}

• C#

internal class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            SIEVE(10000);
            void SIEVE(int num)
            {
                int[] sieve = new int[num + 1];
                for (int i = 2; i <= num; i++)
                {
                    sieve[i] = i;
                }
                for (int i = 2; i <= num; i++)
                {
                    if (sieve[i] == 0) continue;
                    for (int j = i + i; j <= num; j += i)
                    {
                        sieve[j] = 0;
                    }
                }
                for(int i = 2; i <= num; i++)
                {
                    if (sieve[i] != 0)
                    {
                        sb.Append(sieve[i]+" ");
                    }
                }
            }
            Console.WriteLine(sb.ToString());

        }
    }

예제 문제

https://www.acmicpc.net/problem/2960

• 문제

• 문제풀이

에라토스테네스의 체를 알아야한다.

• 코드 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <math.h>
#define _CRT_SECURE_NO_WARNINGS

int cnt = 0;
int sieve[1001]; // 0이면 소수, 1이면 합성수

int Sieve(int n, int k)
{
	for (int i = 2; i <= n; i++)
	{
		if (sieve[i] == 0)
		{
			cnt++;
			if (cnt == k)
				return i;

			for (int j = i * i; j <= n; j += i)
			{
				if (sieve[j] == 0) {

					sieve[j] = 1;
					cnt++;
					if (cnt == k)
						return j;
				}
			}
		}
	}
}

int main()
{
	int N, K;

	scanf("%d %d", &N, &K);

	printf("%d\n", Sieve(N, K));

}

• 후기

에라토스테네스의 체를 풀어볼 수 있었다.

https://www.acmicpc.net/problem/13335

• 문제

• 문제풀이

트럭을 줄세우는 큐와 다리 큐를 만들어준다. 다리 위에는 0을 채워넣고 대기줄의 첫번째 트럭의 무게와 다리위에 놓여진 무게의 합이 무게하중 L보다 작거나 같다면 대기줄의 트럭을 다리큐에 옮겨준다. 만약 다리 큐의 개수가 w를 넘어간다면 Dequeue로 한개를 제거해준다. 반대로 무게의 합이 L보다 크다면 먼저 맨앞을 Dequeue해주고 다시한번 체크를 하여 L보다 작다면 트럭을 넣어주고 그렇지 않다면 0을 넣어준다. 마찬가지로 다리 큐의 수가 w를 넘어간다면 Dequeue를 해준다. 만약 마지막 트럭이 다리 위에 올라간다면 while문을 break해주고 시간에 다리의 칸수만큼 더해 출력해준다.

예제 입력 1

결과

예제입력 2

결과

예제입력 3

결과

• 코드 1

using System.Text;

namespace yongyong2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            Queue<int> bridge = new Queue<int>();
            Queue<int> waiting = new Queue<int>();
            
            string[] input = Console.ReadLine().Split();
            int n = int.Parse(input[0]);
            int w = int.Parse(input[1]);
            int L = int.Parse(input[2]);
            //int[] arr = new int[10000]; 확인용
            int time = 0;
            string[] weight = Console.ReadLine().Split();
            for(int i = 0; i < weight.Length; i++)
            {
                waiting.Enqueue(int.Parse(weight[i]));//줄 세워 놓음
            }
            for(int i=0; i<w; i++)
            {
                bridge.Enqueue(0);//다리위를 0으로 채움
            }
            while (true)
            {
                time++;
                if(waiting.Peek()+bridge.Sum()<=L)
                {
                    bridge.Enqueue(waiting.Dequeue());
                    if(bridge.Count()>w)
                    {
                        bridge.Dequeue();
                    }
                }
                else if (waiting.Peek() + bridge.Sum() > L)
                {
                    bridge.Dequeue();
                    if (bridge.Sum() + waiting.Peek() <= L)
                    {
                        bridge.Enqueue(waiting.Dequeue());
                    }
                    else
                    {
                        bridge.Enqueue(0);
                    }
                    if (bridge.Count() > w)
                    {
                        bridge.Dequeue();
                    }
                }
                /*for(int i=0;i<bridge.Count();i++)
                {
                    arr=bridge.ToArray();
                    Console.Write(arr[i]);
                }
                Console.WriteLine();*/ //다리에 올라간거 확인작업
             
                if (!waiting.Any())
                {
                    break;
                }
                
            }
            Console.WriteLine(time+w);//마지막 차가 올라가면 거리만큼 더해주기
            
        }
    }
}

• 후기

왜 처음에 이걸 스택으로 풀려고 했을까

https://www.acmicpc.net/problem/1874

• 문제

• 문제풀이

1부터 n까지 Push를 해주면서 "+\n"를 입력해주고 만약 스택을 체크했을 때 배열로 받아주었던 입력값과 같다면 Pop과 "-\n"를 입력해준다. 끝까지 진행을 했을 때 스택에 수가 남아있다면 NO를 입력해주고 아니라면 stringbuilder로 입력받은 문자를 출력해준다.

• 코드 1

using System.Text;

namespace ConsoleApp7
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            Stack<int> stack = new Stack<int>();
            int count = 0;
            int N = int.Parse(Console.ReadLine());
            int[] input=new int[N];
            Queue<int> queue = new Queue<int>();
            for(int i=0;i<N;i++)
            {
                input[i]=int.Parse(Console.ReadLine());
                
                
            }
            for(int i = 1; i <= N; i++)
            {
                stack.Push(i);
                sb.Append("+\n");
                while (stack.Any() && stack.Peek() == input[count])
                {
                    stack.Pop();
                    sb.Append("-\n");
                    count++;
                }
            }
            if (stack.Any())
            {
                Console.WriteLine("NO");
            }
            else
            {
                Console.WriteLine(sb.ToString());
            }
        }
    }
}

• 후기

힌트를 보고 그려보니 쉽게 풀 수 있었다

https://www.acmicpc.net/problem/2493

• 문제

• 문제풀이

탑의 번호를 나타내는 스택과 탑의 높이를 나타내는 스택을 생성해준다.

그후 첫번째 입력받았던 탑의 개수인 N번만큼 반복문을 만들어준다.

탑의 번호를 나타내야해서 1부터 N까지 반복문을 만들었다.

첫번째는 6이다.

스택에는 아무것도 없으니 출력에 "0"을 쌓아주고 스택에 넣어준다.

출력: 0

num스택 :1

towerlevel 스택:6

두번째는 9인데 6과 비교했을때 9가 더 크기때문에 이전의 스택들을 Pop해준다. 이후 (2,9)를 Push해주었다.

출력: 0 0

num스택 :2

towerlevel 스택:9

세번째는 5이다. 9와 비교했을 때 9가 더 크기때문에 9의 순서인 2를 출력해주고 (3,5)를 Push한다.

출력: 0 0 2

num스택 :2 3

towerlevel 스택9 5

네번째는 7이다. 7은 5와 비교했을 때 5가 더 작기때문에 스택을 Pop해주고 2를 출력해준다. 이후 (4,7)을 스택에 넣어준다.

출력: 0 0 2 2

num스택 :2 4

towerlevel 스택:9 7

마지막은 4이다. 7과 비교했을 때 7이 더 크기때문에 7의 순서인 4를 출력해주고 (5,4)를 Push해준다.

출력: 0 0 2 2 4

num스택 :2 4 5

towerlevel 스택:9 7 4

• 코드 1

using System.Text;

namespace YongYong2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();
            Stack<int> towerlevel = new Stack<int>();
            Stack<int> num= new Stack<int>();
            int N = int.Parse(Console.ReadLine());
            int Top = 0;
            string[] input=Console.ReadLine().Split();

            for(int i=1; i<=N; i++)
            {
                Top = int.Parse(input[i-1]);
                while (towerlevel.Any())//스택에 숫자가 있다면 탑의 높이 출력
                {
                    if (towerlevel.Peek() > Top)
                    {
                        sb.Append(num.Peek()+" ");
                        break;
                    }
                    towerlevel.Pop();
                    num.Pop();
                }
                if (!towerlevel.Any())//스택에 숫자가 없다면 0출력
                {
                    sb.Append("0 ");
                }
                towerlevel.Push(Top);
                num.Push(i);
            }
            Console.WriteLine(sb.ToString());
        }
    }
}

• 후기

그림판 꿀잼

https://www.acmicpc.net/problem/17827

• 문제

• 문제풀이

만약 입력받는 수 K가 N보다 작다면 K번째 배열을 출력하고 만약 N보다 큰 수가 나온다면 V전까지를 빼고 나머지를 구한뒤 다시 V를 넣고 배열을 출력해준다.

• 코드 1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>



int main() {
    int n, m, v, x;
    scanf("%d %d %d", &n, &m, &v);
    int* arr = new int[n];
    
    for (int i = 0; i < n; i++) {
        scanf("%d",&arr[i]);
    }
    for (int i = 0; i < m; i++) {
        int q;
        scanf("%d", &q);
        if (q < n) {
            printf("%d\n", arr[q]);
        }
        else {
            int round = n - v + 1;
            q -= v - 1;
            printf("%d\n", arr[q % round + v - 1]);
        }
    }
    return 0;
    
}

• 후기

태블릿에 노가다로 그려보면서 풀었더니 손이 아프다