분류 전체보기
-
에라토스테네스의 체알고리즘 2020. 7. 16. 22:11
에라토스테네스의 체 - 개념 : 소수(prime number)를 판별하는 알고리즘 소수? '양의 약수를 두 개만 가지는 지연수' = '1과 자기자신' - 원리 : 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여 해당하는 값을 넣어주고, 이후에 하나씩 지워가는 방법 1. 배열을 생성하여 초기화한다.2. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이미 지워진 수라면 배수를 확인하지 않고 다음 수로 넘어간다. (2를 제외한 모든 2의 배수를 지움 3을 제외한 모든 3의 배수를 지움 4를 제외한 모든 4의 배수를 지움 ... 이런식) 3. 2부터 시작하여 남아있는 수를 모두 출력한다. - 구현 코드 123456789101112131415161718192021222324252627#inclu..
-
[백준] 1016번 제곱 ㄴㄴ수문제 풀이 2020. 7. 16. 19:24
1016 제곱 ㄴㄴ 수 문제어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. 입력첫째 줄에 min과 max가 주어진다. min은 1보다 크거나 같고, 1,000,000,000,000보다 작거나 같은 자연수이고, max는 min보다 크거나 같고, min+1,000,000보다 작거나 같은 자연수이다. 출력첫째 줄에 [min,max]구간에 제곱ㄴㄴ수가 몇 개인지 출력한다. 풀이)에라토스테네스의 체 방법을 사용하였고제곱수가 아닌 수를 찾는 것이 아닌, 1보다 큰 제곱수로 나누어 떨어지지 않는 수를 찾으면 되는 문제이다. 핵심은min과 max의 범위가 크므로..
-
[백준] 13901번 로봇문제 풀이 2020. 7. 15. 21:10
13901번 로봇 문제해빈이는 로봇을 좋아한다. 로봇을 가지고 놀던 해빈이는 로봇에게 계속해서 명령을 내려 움직이는 대신 이동할 방향을 미리 지정하여 로봇이 알아서 움직이도록 하였다. 이 로봇은 다음과 같은 규칙을 가지고 움직인다.- 로봇은 사용자가 지정한 방향을 일직선으로 움직인다.- 이동 중 벽이나 방문한 지역, 장애물을 만날 경우 로봇은 사용자가 지정한 다음 방향으로 움직인다.- 사용자가 지정한 다음 방향이 없다면 맨 처음 방향으로 돌아가서 위의 과정을 반복한다.- 로봇이 움직일 수 없을 경우 동작을 멈춘다. 입력으로 방의 크기와 장애물의 개수, 각 장애물들의 위치, 로봇의 시작 위치, 이동 방향의 순서가 주어졌을 때 로봇이 멈추는 위치를 출력하시오. 위치 (0, 0)은 왼쪽 위를 가리키며 방의 크..
-
[백준] 14620번 꽃길문제 풀이 2020. 7. 14. 19:40
14620번 꽃길 문제2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양이 된다.꽃을 심을 때는 주의할 점이있다. 어떤 씨앗이 꽃이 핀 뒤 다른 꽃잎(혹은 꽃술)과 닿게 될 경우 두 꽃 모두 죽어버린다. 또 화단 밖으로 꽃잎이 ..
-
[백준] 14923번 미로 탈출문제 풀이 2020. 7. 14. 18:34
14923 미로탈출 풀이)bfs를 이용해서 푼 문제이다.예전에 풀었던 벽 부수기 문제(2206번)랑 같은 방법으로 풀면 된다. 지팡이를 사용하지 않았던 경로와 지팡이를 사용한 경로가 중간에 같은 위치에서 만났을 때를 잘 처리해주면 된다.둘 중 하나가 방문 체크를 하면 나머지 하나의 경로는 더이상 탐색을 하지 못하기 때문이다. => 방문 체크 배열을 3중 배열로 두고 처리한다.bool visited[1001][1001][2];// visited[y][x][0] : 아직 지팡이를 사용하지 않고 (ny,nx)에 방문// visited[y][x][1] : 이미 지팡이를 사용하고 (ny,nx)에 방문 주의점우리가 보통 문제 풀 때 행을 y 열을 x로 입력 받았는데, 여기서 입력으로 주어지는 변수들을 보면행을 Hx..
-
[백준] 13537번 수열과 쿼리1문제 풀이 2020. 7. 13. 18:39
13537 수열과 쿼리1 문제길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. 입력첫째 줄에 수열의 크기 N (1 ≤ N ≤ 100,000)이 주어진다.둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)셋째 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.넷째 줄부터 M개의 줄에는 쿼리 i, j, k가 한 줄에 하나씩 주어진다. (1 ≤ i ≤ j ≤ N, 1 ≤ k ≤ 109) 출력각각의 쿼리마다 정답을 한 줄에 하나씩 출력한다. 풀이)수열의 길이도 10만까지 되며, 쿼리의 수도 10만까지 주..
-
lower_bound & upper_bound 함수잡다한 지식 2020. 7. 12. 17:47
헤더에 정의되어 있는 함수 1. lower_bound : 범위 안의 원소들 중, value보다 작지 않은(크거나 같은) 첫번째 원소의 위치를 반복자로 반환이진탐색(binary search) 기반의 탐색법(이진탐색 기반이므로, 범위 안의 원소들은 정렬된 상태여야 한다.) 사용법 lower_bound(범위 시작 위치, 범위 마지막 위치, value) 2. upper_bound : 범위 안의 원소들 중, value보다 큰 첫번째 원소의 위치를 반복자로 반환이진탐색 기반의 탐색법 사용법upper_bound(범위 시작 위치, 범위 마지막 위치, value) 사용코드 예시) vector 사용 123456789101112131415161718192021222324#include #include #include usi..
-
[백준] 11048번 이동하기문제 풀이 2020. 7. 11. 18:14
11048 이동하기 문제준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오. 입력첫째 줄에 미로의 크기 N, M이 주어진다. (1 ≤ N, M ≤ 1,000)둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지..