본문 바로가기
반응형

분류 전체보기1067

BOJ 4913 : 페르마의 크리스마스 정리 알고리즘 문제 전체 링크 www.acmicpc.net/problem/4913 1,000,000의 크기의 수를 매번 소수 판단할 수 없으므로 에라토스테네스의 체를 이용하여 메모해둔다. 그리고 매번 L과 U에 포함된 소수의 개수와 소수 중 제곱수의 수를 셀 수 없으므로 아래와 같이 메모한다. #define MAX (1000000) int L, U; int prime[MAX + 100]; int primeSum[MAX + 100]; int squreSum[MAX + 100]; int main() { makePrime(); /* 에라토스테네스의 체 */ squreSum[2] = primeSum[2] = 1; for (int i = 3; i = 1 : L이 자연수인 경우 (U는 항상 L보다 크다) 2) L이 음수.. 2021. 3. 19.
C++ ofstream을 이용한 FILE 출력 C, C++ 전체 링크 C++에서 파일을 출력하는 방법 중 하나는 ofstream이다. ofstream은 fstream header와 namespace std를 선언하면 쓸 수 있다. 먼저 ofstream type 변수를 하나 선언한다. open 메서드를 이용하여 출력할 파일명을 넣는다. 파일명이 없다면 새로 파일을 만들지만, 솔루션 탐색기에는 따로 추가해야한다. 출력할 파일이 정해졌으면 " 2021. 3. 18.
BOJ 18139 : Rush Hour Puzzle (해시, 2차원 배열 탐색) 삼성 B형 전체 링크 www.acmicpc.net/problem/18139 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 내용을 번역해서 요약하면 아래와 같다. 1) 6 x 6 board에서 자동차가 최대 10개 존재한다. 2) 자동차는 1칸씩 움직이며, 길이가 2 또는 3이다. 3) 1번 자동차가 exit로 탈출해야 한다. 4) exit는 항상 3번째 줄의 오른쪽 끝이다. 따라서 1번 자동차는 항상 3번째 줄에 가로로 존재한다. 5) 최대 10칸까지 움직인다. 그 이상 움직여도 1번 자동차가 exit로 탈출 못하면 -1을 출력한다.. 2021. 3. 18.
BOJ 17142 : 연구소 3 (삼성 SW TEST A형) A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/1152 (A형 문제집) www.acmicpc.net/problem/17142 연구소 문제와 다른 점은 벽을 세우는 것이 아니고, 바이러스를 M개 선택해야하는 것이다. 바이러스의 선택 → DFS 경우의 수 : 조합 문제 바이러스의 확산 → 토마토 문제를 같이 조합해서 풀면 된다. 먼저 문제를 풀기 편하게 input을 받으면서 MAP을 재변경하자.벽(1)과 바이러스(2)를 그대로 두면, 바이러스가 몇초 뒤에 퍼지는지 셀 때, 구분하기 까다롭다.따라서 벽은 -1로, 바이러스는 -2로 표시하자.또한, 바이러스는 따로 배열에 저장해두자.typedef struct st{ .. 2021. 3. 17.
BOJ 7569 : 토마토 (3차원) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7569  BOJ 7576 토마토는 2차원에서 토마토가 퍼져나갔다.이번 문제는 3차원에서 토마토를 만들어가면 된다. 2차원에서는 4방향으로 토마토를 큐에 담았지만,3차원에서는 좌표의 높이(h)에 대해 위, 아래 토마토를 추가해주면 된다.즉, 총 6방향으로 BFS가 퍼져 나간다./* 순서대로 왼쪽, 위, 오른쪽, 아래 */int dr[] = { 0, -1, 0, 1 };int dc[] = { -1, 0, 1, 0 };void BFS(){ for (int h = 1; h rp) { QUEUE out = queue[rp++]; for (int i = 0; i  그리고 inp.. 2021. 3. 17.
BOJ 7576 : 토마토 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 알고리즘 문제 전체 링크 www.acmicpc.net/problem/7576  미로 탐색 문제에서 BFS를 이용하여 거리를 계산하였다. 같은 방법을 토마토 문제에서 적용할 수 있다.토마토를 모두 넣고 미로 탐색과 같은 방식으로 BFS를 적용하면, 토마토가 상자를 꽉 채우게 된다.토마토가 상자를 꽉 채우는 것은.각 토마토가 상자에서 최소로 가능 경로를 모든 토마토에 대해 실행하면 된다. 다음과 같은 5 x 5 상자(MAP)에 토마토가 있다고 가정하자.편의상(경계 조건을 신경쓰지 않기 위해) MAP의 주변은 -1로 만든다. 이제 모든 토마토를 queue에 담는다. 참고로 토마토 문제의 경우는 미로 탐색과는 달리 visit이 필요가 없다.상자.. 2021. 3. 16.
BOJ 6588 : 골드바흐의 추측 알고리즘 문제 전체 링크 www.acmicpc.net/problem/6588 어떤 숫자가 소수의 합으로 이루어져 있는지 판단해야 한다. 매번 소수 판단 함수를 사용하면, 비용이 많이 들어 time out이 나기 때문에, 주어진 n = 1000000이하의 수에 대해 모두 소수인지 미리 구해둔다. 즉, 에라토스테네스의 체를 이용하여 소수를 먼저 만든다. 그리고 primeNumber에는 prime을 check하여 실제 소수 값을 순서대로 적어둔다. 주어진 요구사항은, n을 만들 수 있는 방법 중 b - a가 가장 큰 값을 출력해야 하므로, 가장 작은 소수 2, 즉 primeNumber[st = 0]부터 시작하면서 n - primeNumber[st]가 소수인지 판단한다. primeNumber[st]가 소수이고 .. 2021. 3. 16.
에라토스테네스의 체 - 소수 판단 C, C++ 전체 링크 어떤 수 하나를 소수 판단할 경우는 링크에서 for문을 돌면서 판단할 수 있다. 하지만 매번 숫자를 소수 판단하면 비용이 많이 들기 때문에, memoization 기법으로, 특정 숫자가 소수인지 미리 체크해두면 편하다. 이때, 사용하는 알고리즘이 에라토스테네스의 체 이다. 배열 prime[]은 소수인 경우 0, 소수가 아닌 경우 1로 표시하자. 이제 1 ~ 50의 경우 소수를 판단하는 원리를 알아보자. 먼저, 1은 소수가 아니므로 지운다. prime[1] = 1 이제부터 에라토스테네스의 체가 시작된다. 에라토스테네스의 체에 걸려있지 않다면, 소수다. 현재 2는 에라토스테네스의 체에 걸려있지 않으므로, 소수이다. 그리고 2 부터 2칸씩 모두 소수가 아니므로 지운다. prime[2 *.. 2021. 3. 16.
scanf로 문자열과 공백 받기 C, C++ 전체 링크 아래와 같은 input.txt가 있다고 하자. 문자열은 보통 c에서 scanf로 받지만 공백이 있는 경우는 까다롭다. scanf에 더이상 읽을 파일이 없을 경우 -1(EOF : End of File)을 return하기 때문에 txt의 끝은 알 수 있지만, input은 공백을 기준으로 file 입력을 끊어버린다. #include int main(void) { char input[100]; while(scanf("%s", input) != EOF) { printf("%s\n", input); } return 0; } 공백을 기준으로 input에 read 되는 것을 알 수 있다. 이러한 점을 방지하기 위해, scanf에 " %[^\n\r]" 옵션을 넣어주면, 공백을 무시하고 한 줄을 입.. 2021. 3. 16.
반응형

티스토리툴바