본문 바로가기

프로그램820

백트래킹(Backtracking, 되추적) 모든 경우의 수를 전부 고려하는 알고리즘. 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘 방식으로 깊이우선탐색(Depth First Search, DFS)과 너비우선탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search/Heuristic Search)이 있다. 모든 경우의 수를 고려해야 하는 문제라면 일반적으로 DFS가 편리하다. 그러나 DFS를 절대 쓰면 안 되는 경우가 있는데, 트리의 깊이가 무한대가 될 때이다. 미로찾기에서 루프(회로)가 발생하는 경우, DFS는 이 가지를 탈출할 수 없게 된다. 물론 중복검사를 막기 위한 장치를 넣을 수도 있지만, 그럴 바에는 BFS가 편하다. 또 분기점 없이 길이만 죽어라 긴 길이.. 2024. 12. 3.
C++ 126제] 어서와! C++은 처음이지! CHAPTER 11. PROGRAMMING EXERCISE 1. p475 2) p475 출처 : 반크_반크 20년 백서 ● + 연산자를 중복 정의하여서 다음과 같은 연산이 가능하도록 하라. 참고풀이]#define _CRT_SECURE_NO_WARNINGS #include  using namespace std; class Point {    int x, y; public:    Point(int px = 0, int py = 0)    {       x = px; y = py;    } //생성자 함수    int getX() { return x; } //접근자    int getY() { return y; }    void setX(int px) { x = px; } //설정자    void setY(int py) { y = py; }    ~Point() {} //소멸자 함수 }; cla.. 2024. 12. 2.
C언어 195제] 2004년 한국정보올림피아드 지역본선 중등/고등부 1번 최대공약수와 최소공배수 출처 : 반크_백제역사 유적지구와 이스탐블 역사지구 문제]두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 예제 입력 1  24 18 예제 출력 1  6 72 출처 : 백준_2609번 참고 알고리즘 : 유클리드 호제법참고풀이]#define _CRT_SECURE_NO_WARNINGS #include  //유클리드 호제법 사용 //최대공약수 구하기 int GCD(int a, int b) {    return (b == 0) ? a : G.. 2024. 11. 30.
C언어 194제] NPC Lv2. 달팽이2 출처 : 반크_백제역사 유적지구와 이스탐블 역사지구 문제]M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다.ㅇ                    위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 그려진 칸에 닿아서 더 이상 이동할 수 없게 되면, 시계방향으로 선을 꺾어서 그려나간다.ㅇ→↘↗↘↓↑↓↓↑끝↓↖←↙ 위의 표는 선을 그려 나간 모양을 나타낸 것이다. 선이 꺾어진 부분은 대각선으로 나타내었다. 표의 모든 칸이 채워질 때까지, 선을 몇 번 꺾게 될까? 입력 첫째 줄에 M과 N이 빈 칸을 사이에 두고 주어진다. (2 ≤ M, N ≤ 100) 출력 첫째 줄에 표의 모든 칸이 채워질 때까지 선이 꺾어.. 2024. 11. 30.
C언어 193제] 조건에 맞는 암호를 만드시오. 출처 : 반크_백제역사 유적지구와 이스탐블 역사지구 문제]자연수를 입력받아 다음 규칙에 따라 암호를 만들어 출력하는 프로그램을 작성하시오. 각 숫자는 다음 표와 같이 바뀌어 암호가 된다. 입력 예 (input.txt) 9887 출력 예 (output.txt) GOOD 참고 알고리즘]암호화/복호화 참고풀이]#include  int main() {    int N;//입력된 숫자를 저장할 변수를 선언.     int insu;//작업할 때 N을 대신할 변수를 선언     //숫자들과 대칭되는 문자배열을 선언한다.    char ch[10]={'Y','B','K','E','A','R','N','D','O','G'};    int a;//반복변수     int mok;    int jari;     scanf(.. 2024. 11. 29.
C언어 192제] 평범한 배낭 출처 : 반크_백제역사 유적지구와 이스탐블 역사지구 문제]이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸.. 2024. 11. 28.
유클리드 호제법 유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않으나(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다). 정수론을 배우게 된다면 가장 먼저 나올 확률이 높은 공식이다. 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 최대공약수(GCD)란? - 두 수의 공통된 "약수 중에서 가장 큰 수"를 의미합니다. 최소공배수(LMC)란? .. 2024. 11. 27.
암호화/복호화 1. 개요암호기술은 중요한 정보를 읽기 어려운 값으로 변환하여 제 3자가 볼 수 없도록 하는 기술입니다. 암호기술의 안전성은 수학적인 원리에 기반하며, 보안에 있어서 중요한 정보를 직접적으로 보호하는 원천기술 입니다. 암호기술을 통해 보호하고자 하는 원본 데이터를 평문(plaintext)라고 하며, 평문에 암호기술을 적용한 것을 암호문(ciphertext)라고 합니다. 이렇게, 평문에 암호기술을 적용하여 암호문으로 변환하는 과정을 암호화라고 하며, 다시 평문으로 복원하는 과정을 복호화라고 합니다. 암호화하기 위해서는 암호 키(key)가 필요하며, 키가 있어야만 암호문을 복호화할 수 있습니다. 그렇게 때문에 암호 키는 비밀(secret)로 유지되어야 하며 제3자가 알 수 없어야 합니다.  암호기술을 이용하.. 2024. 11. 26.
C언어 191제] 2002년 Waterloo's local Programming Contests D번 평균은 넘겠지 출처 : 반크_세계유산 경복궁 문제]대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. 입력 첫째 줄에는 테스트 케이스의 개수 C가 주어진다. 둘째 줄부터 각 테스트 케이스마다 학생의 수 N(1 ≤ N ≤ 1000, N은 정수)이 첫 수로 주어지고, 이어서 N명의 점수가 주어진다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다. 출력 각 케이스마다 한 줄씩 평균을 넘는 학생들의 비율을 반올림하여 소수점 셋째 자리까지 출력한다. 정답과 출력값의 절대/상대 오차는 10-3이하이면 정답이다. 예제 입력 1  5 5 50 50 70 80 100 7 100 95 90 80 70 60 50 3 70 90 80 3 70 90 81 9 100 .. 2024. 11. 25.
C언어 190제] 2011년 한국정보올림피아드 시․도지역본선 초등부 2번, 고등부 1번 나는 학급회장이다. 출처 : 반크_세계유산 경복궁 문제]N명의 학생들이 모인 초등학교 반에서 학급회장 선거를 하려고 한다. 그 중 3명이 회장후보로 나왔고, 이들에 대한 선호도를 N명의 학생들 각각에게 적어내도록 하였다. 세 명의 후보는 후보 1번, 후보 2번, 후보 3번이라 한다. 모든 학생은 3명의 후보 중에서 가장 선호하는 후보에게는 3점, 두 번째로 선호하는 후보에게는 2점, 가장 선호하지 않는 후보에게는 1점을 주어야 한다. 3명의 후보에 대한 한 학생의 선호 점수는 모두 다르며, 1점, 2점, 3점이 정확히 한 번씩 나타나야 한다. 후보의 최종 점수는 학생들로부터 받은 자신의 선호도 점수를 모두 더한 값이 된다. 그러면 3명의 후보 중 가장 큰 점수를 받은 후보가 회장으로 결정된다. 단, 점수가 가장 큰 후보가 .. 2024. 11. 25.
C언어 189제] 2010/2011 COCI 크로아티아 정보학 공개 경쟁 #2 1번 달팽이는 올라가고 싶다. 출처 : 반크_세계유산 경복궁 문제]땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B 출력 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 예제 입력 1  2 1 5 예제 출력 1  4예제 입력 2  5 1 6 예제 출력 2  2예제 입력 3  100 99 1000000000 예제 출력 3  999999901 출처 : 백준_2869번 참고풀이1].. 2024. 11. 25.
C++ 125제] 어서와! C++은 처음이지! CHAPTER 11. PROGRAMMING EXERCISE 1. 1) p475 출처 : 반크_반크 20년 백서 ● 위의 프로그램을 컴파일할 수 있도록 생성자, 접근자, 설정자 등의 함수를 추가하라.참고풀이]#define _CRT_SECURE_NO_WARNINGS #include  using namespace std; class Point {    int x, y; public:    Point(int px = 0, int py = 0)    {       x = px; y = py;    } //생성자 함수    int getX() { return x; } //접근자    int getY() { return y; }    void setX(int px) { x = px; } //설정자    void setY(int py) { y = py; }    ~Point() {} //소멸자 .. 2024. 11. 23.
반응형