Algorithm with C/ETC
-
A* 알고리즘Algorithm with C/ETC 2021. 3. 19. 22:11
내용은 책 1권, 5권, 7권에서 발췌. A* 알고리즘의 역사는 너비 우선 탐색에서 시작한다. 너비 우선 탐색은 트리에서 한 노드의 모든 자식 노드를 점검한 후에 트리의 다음 수준으로 내력가는 방식이다. 현재 수준의 자식 노드들에서 목표를 발견하지 못하면 자식 노드들을 한 수준 더 전개해서 검색을 진행한다. 구현 환경은 Microsoft Visual Studio 2008 A*의 이론에 대해서는 다른 블로그에 자세히 설명되었으므로 여기서는 구현의 목적에 초점을 두도륵 한다. 필요한 자료구조 힙(최소힙), 연결 리스트이며, 기존의 힙은 최대 힙으로 구현을 하였는데, 최소 힙을 만드려면 부등호의 방향만 변경하면 된다. designatedroom87.tistory.com/27?category=871993 최대 ..
-
Kaprika수 구하기(4자리 수에 대해서만)Algorithm with C/ETC 2020. 10. 29. 19:41
문제 Kaprika 수란? 예를 들어 네 자리 숫자 2025의 가운데를 갈라보면 20과 25의 두개의 숫자가 생긴다. 이 두개의 숫자를 더하면 45이고, 45를 제곱하면 2025가 되어 원상태로 되돌아간다. 이러한 성질을 갖는 수를 Kaprika수 라고 한다. 또 81은 가운데를 잘라보면 8 과 1로 갈라지고, 더하면 9가 되고 다시 제곱하면 81로 돌아간다. 그러므로 81은 두 자리 숫자의 Kaprika수가 되는 것이다. 네 자리 kaprika 수를 구하는 프로그램을 만들자. 구현방법 이 문제에서 첫 번째로 필요한 기능은 해당하는 수가 네 자리 수인지를 판단할 수 있어야 한다. 이 기능을 담당할 함수의 이름을 GetNumberDigit 라고 하자. 매개변수는 현재의 수이다. GetNumberDigit함..
-
요술 사각형Algorithm with C/ETC 2020. 10. 27. 19:15
문제 N X N 정방 행렬에서 행의 합, 열의 합, 대각선의 합이 모두 같은 값을 갖는 프로그램을 작성하라. 입력 설계 정방 행렬의 크기 N을 받아들인다. 출력 설계 N = 3 N = 5 처리 조건 입력 자료 N은 반드시 홀수이며, 짝수일 경우는 에러 문구를 출력시킨다. 문제 힌트 Case1. 첫째 행의 중앙에 1을 넣는다. Case2. 현재의 위치(x,y)에서 배열의 대각선을 살펴본 다음, 그곳에 이미 다른 수가 있으면 현재의 위치 아래 칸에 수를 넣는다. Case3. 만일 정방 행렬의 크기를 벗어 나게되면, 정방 행렬이 연결된 것으로 생각해서 그 곳에 넣는다. n = 3 일 경우, 변수 테이블은 아래와 같다. 구현 소스 파일 프로그램 실행결과
-
배열에 중복 없이 랜덤으로 숫자 저장하기Algorithm with C/ETC 2020. 10. 20. 08:51
문제에 대해서 생각을 해보자. 처음에 배열에 아무 것도 저장이 되어 있지 않다면 해당하는 수를 바로 배열의 [0]번째 인덱스 요소에 저장 한다. 문제는 바로 [1]번째 인덱스에 저장을 할 때이다. 우선 임시 변수에 랜덤 수를 저장을 하고 있다가, [0]번째 요소와 비교를 해본다. 비교해서 값이 같으면 중복된 수 이므로 저장을 하면 안되며, 반대인 경우에는 바로 [1]번째 인덱스에 값을 저장한다. 그리고, [1]번째 인덱스까지 데이터가 저장이 된 후에는 이 임시변수와 0번, 1번 인덱스에 저장된 데이터들과 모두 비교를 통해 중복의 여부를 확인해야 한다. 즉, 중첩 반복문을 써야한다는 사실을 알 수 있다. 프로그램 실행결과 소스 파일
-
비트 연산자 문제Algorithm with C/ETC 2020. 10. 17. 08:52
문제 비트 이동 연산을 이용하여 문자 4개를 받아서 하나의 unsigned int형의 변수 안에 저장하는 프로그램을 작성하라. 첫 번째 문자는 unsigned int형 변수의 비트 0 부터 7 까지에 저장이 되고, 두 번째 문자는 비트 8부터 15 까지. 세 번째 문자는 비트 16에서 비트 23까지 네 번째 문자는 비트 24 부터 비트 31까지에 저장된다. 결과로 생성되는 정수값은 16진수로 출력하도록 한다. 비트 이동 연산과 비트 OR연산을 사용하라. 입력 첫 번째 문자:a 두 번째 문자:b 세 번째 무자:c 네 번째 문자:d 출력 결과값: 64636261 구현 프로그램 실행결과 소스 코드 더보기 #include #defineMAX4//문자 배열의 길이 #defineBITS_PER_BYTE8//1바이트..
-
달팽이 배열Algorithm with C/ETC 2020. 9. 21. 17:41
문제 아래와 같이 데이터를 저장하도록 프로그래밍 하자. 구현 프로그램 실행결과 소스 파일 여기까지만 해도 괜찮지만, 다이나믹한 출력을 위해 아래의 두 함수를 추가해보자. Gotoxy함수에서 COORD 자료형을 쓰기위해서는 Windows.h를 include 해야한다. 콘솔 화면 창의 좌측 상단이 (0,0)이고 우측으로 갈수록 x좌표값이 커지고 아래로 갈수록 y좌표값이 커진다. 위의 두 함수는 이차원 배열에 데이터를 저장할 때 호출하도록 한다. 위의 함수에서 4를 곱하는 부분이 있는데, 열의 간격을 넓히기 위함이다. 열의 간격을 넓히지 않으면 숫자와 숫자 사이가 붙기 때문이다. 적당한 수를 곱하거나 더해서 간격을 준 것이다. 프로그램 실행결과 소스 파일 조금 다른 방식
-
Matching System - 파티원 조직Algorithm with C/ETC 2020. 9. 12. 23:21
1. 문제 2. 문제 해결 전에 해야할 것 의 문제를 해결 하기 전에 다음과 같은 문제에 대한 답을 해보자. 아래와 같이 숫자들이 정의되어있다고 하자. 1, 4, 7, 2, 5, 8, 3, 6, 9, 10, 11 첫 번째 그룹 11 10 1 두 번째 그룹 9 8 5 세 번째 그룹 7 6 4 3 2 위와 같이 3개의 그룹이 있으며, 각 그룹에 위와 같이 값들이 저장되어있다고 하자. 그러면, 위의 그룹의 특징이 눈에 보이는가? 1그룹의 숫자 합 = 2그룹 숫자 합 = 3그룹 숫자 합 임을 알 수 있다. 각 그룹의 각 각의 합은 22이다. 그리고, 위의 숫자의 총합은 66이다. (1부터 11까지의 합이므로.) 숫자 총합 / 3 = 22 위와 같은 프로그램을 작성해보자. 힌트는 아래와 같다. ..
-
통신 연구소Algorithm with C/ETC 2020. 9. 9. 00:07
1. 문제 N사 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여, 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어, 높이가 6,9,5,7,4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향( 왼쪽 방향 )으로 동시에 레이저 신호를 발사한다고 하자. 그러면 ㉠..