본문 바로가기

알고리즘/BAEKJOON17

[백준] 15965번 K번째 소수: 에라토스테네스의 체 최적화 해보기 - C++ 들어가며 알고리즘 문제해결을 하다 보면 소수와 관련한 문제를 자주 만나볼 수 있습니다. 오늘은 소수판별법 중 하나인 에라토스테네스의 체를 몇 가지 방법으로 최적화해보겠습니다.K번째 소수 자연수 K가 주어지면 K번째 소수를 출력하는 간단한 문제이지만 K의 범위가 최대 50만이기 때문에 시간초과가 나오기 쉬운 문제입니다.풀이방법 기본적인 에라토스테네스의 체 알고리즘은 다음과 같습니다. 소수의 배수들을 제거해 나가면서 소수의 후보를 줄이는 방식입니다.#include #include using namespace std;int main(){ vector prime(500001); // 소수를 담는 배열. 처음엔 비어있음. int prime_num = 1; // 첫번째 소수를 입력할 차례. int limit = 7.. 2025. 2. 14.
[백준] 10986번 나머지 합 : 맞왜틀 - C++ 들어가며 맞왜틀, 맞는데 왜 틀려라는 뜻으로 코딩을 하다 보면 자신도 모르게 맞왜틀을 외치게 될 때가 있습니다. 경험상 보통 99.99%는 제가 틀린 것이지만요. 이런 맞왜틀을 마주칠 때 점검해 봐야 할 것은 무엇이 있을까요?변수명 확인: 똑같은 변수명을 함수 내외에서 선언하거나, 변수명을 헷갈려서 다르게 사용하는 경우도 있습니다.세미콜론: 여기서 세미콜론은 안 붙인 경우가 아니라 붙인 경우입니다. 안 붙이면 컴파일 에러가 뜨지만 while이나, for 뒤에 붙이게 되면.. 컴파일 에러도 안 뜨고 잘 안 보여서 찾기도 어렵습니다.오버플로우 & 언더플로우: int는 대충 21억 long long은 약 9*10^18까지가 범위입니다. 유형에 맞는 자료형을 써야 합니다. 오늘 제가 한 실수는 3번 오버플로우였.. 2024. 12. 3.
[백준] 1504번 특정한 최단 경로 : 다익스트라 - C++ 1504번 특정한 최단 경로 노드 n개가 주어질 때 시작점에서 v1, v2를 모두 경유하여 끝점으로 가는 최단경로를 구하는 문제입니다. 가능한 경우의 수는 두 가지뿐입니다. 첫 번째, 시작점 - v1 - v2 - 끝점. 두 번째, 시작점 - v2 - v1 - 끝점. 두 경로중 거리가 더 짧은 경로를 출력하면 됩니다. 시작점에서 v1, v2까지의 최단거리와 v1, v2사이의 최단거리, v1, v2에서 끝점사이의 최단거리를 구하면 됩니다.풀이방법 처음에는 학교에서 배운 다익스트라를 그대로 적용하여 distance배열을 업데이트 하는 방식을 사용했습니다. 하지만 distance배열에서 최솟값을 찾고 업데이트를 하는 과정이 오래 걸려 시간초과가 발생했습니다.// 시간초과 코드#include #include us.. 2024. 11. 18.
[백준] 14500번 테트로미노 - C++ 테트로미노 N x M 크기의 보드에 정사각형 4개로 이루어진 블록을 무작위로 배치했을 때 블록에 가려진 정수의 합이 가장 큰 경우의 값을 찾는 문제입니다. 어떻게 풀어야 하나.. 고민하다가 아이디어가 당장 안 떠올라서 노가다 - 멋있는 말로 브루트 포스 - 로 풀었습니다.풀이방법 그림과 같이 엑셀에 모든 블록의 경우의 수를 정리해 보니까 19가지의 블록을 최대 500 x 500의 보드에 배치하는 것이기 때문에 시간제한 2초 안에 성공할 수 있을 것 같아서 브루트포스를 선택했습니다. 그림과 같이 블록들을 가로 x 세로의 크기대로 분류하면 총 5가지의 유형으로 분류할 수 있습니다. 유형별로 2중 for문을 돌리고 for문 안에서 공통된 블록은 한 번만 계산함으로써 최대한 연산을 줄였습니다.코드#include.. 2024. 11. 9.
[백준] 7576번 토마토 - C++ 토마토 위 그림과 같은 상자에 한 칸에 하나씩 토마토가 들어있고 익은 토마토는 하루 만에 인접한 토마토를 익게 만든다고 했을 때 모든 토마토가 익는데 걸리는 일수를 구하는 문제입니다.입력 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M, N ≤ 1,000이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.토마토가 하나 이상 있는 경우만 .. 2024. 11. 4.
[백준] 1074번 Z - C++ Z 위 그림과 같이 주어진 보드를 z모양으로 순회할 때 r행 c열에는 몇 번째로 방문하는지 출력하는 문제입니다. 행, 열 번호와 방문 순서는 모두 0부터 시작합니다.입력첫째 줄에 정수 N, r, c가 주어진다.출력r행 c열을 몇 번째로 방문했는지 출력한다.제한1 0 예제 입력2 3 1예제 출력11풀이 방법1. 현재 보드를 좌상단의 좌표x, y와 보드의 size로 표현한다. size=2^z2. count = 03. 현재 보드에서 c, r의 위치가 좌상단, 좌하단, 우상단, 우하단 중 어디인지 알아낸다.4. n>1일 경우, 위치에 따라 count변수에 0, size*size/2, size*size/4, size*size/4*3을 더한다.5. n=1일 경우, 위치에 따라 count변수에 0, 2, 1, 3을 .. 2024. 11. 3.

티스토리툴바