본문 바로가기

Algorithms/simulation90

비밀편지 비밀편지 제한시간: 1000 ms 메모리제한: 32 MB ​병현이는 지은이에게 문자 A, B, C, D, E, F, G, H 로 쓰여진 편지를 날마다 보내는데, 컴퓨터로 보내는 비밀편지로, 한 문자마다 0 또는 1인 숫자 여섯 개를 사용하여 보낸다. 둘 사이의 약속은 다음과 같다.​ A 000000​ B 001111 C 010011 D 011100 E 100110 F 101001 G 110101 H 111010 병현이가 어느 날 001111000000011100 을 보내면 지은이는 이것을 BAD로 이해하게 된다. 그런데 둘 사이에 약속이 잘 만들어져 있기 때문에, 통신에 문제가 생겨서 한 문자를 표시하는 여섯 숫자 중 어느 한 숫자만 틀리게 오는 경우, 지은이는 원래 보내려는 문자를 알아 낼 수가 있다... 2020. 1. 9.
Square Square 제한시간: 0 ms 메모리제한: 0 MB 아래 코드를 분석하여 정사각형의 개수를 구하는 recoq함수를 작성하시오. //--------------user.cpp--------------- int recog(unsigned char image[64][64]) { int ans = 0; return ans; } //--------------main.cpp--------------- #include const int SIZE = 64; int COUNT, SCORE; int seed = 1117; unsigned char image[SIZE][SIZE]; extern int recog(unsigned char image[SIZE][SIZE]); static int pseudo_rand(void) .. 2020. 1. 9.
연속부분합 찾기 연속부분합 찾기 제한시간: 1000 ms 메모리제한: 32 MB N개의 정수를 담고 있는 배열이 주어졌을 때, 여기서 가능한 연속 부분합을 구하는 프로그램을 작성하라. 여기서 연속 합이라는 것은 배열에서 연속된 숫자들을 선택해서 합하였을 때의 값을 말한다. 아무 배열도 택하지 않는 경우도 연속된 배열합에 포함됨을 유의하자. 입력의 첫 번째 줄에는 정수 N(1≤N≤105)가 입력된다. 그리고 그 다음 줄에는 N개의 배열에 담긴 숫자가 순서대로 입력된다. 숫자의 범위는 -100이상 100이하의 정수다. 입력에 대한 가장 큰 연속 부분합을 출력한다. 4 1 2 -2 4 5 10 3 -4 0 1 7 -4 13 -9 8 -3 17 #include #define MAX 10 // 100005 int N, arr[M.. 2020. 1. 9.
기수정렬(Radix Sort) 기수정렬(Radix Sort) 제한시간: 3000 ms 메모리제한: 256 MB N개의 정수가 담긴 배열 A가 주어진다. ( 1 2020. 1. 9.
책꽂이 만들기 책꽂이 만들기 제한시간: 1000 ms 메모리제한: 128 MB 지헌이는 책꽂이를 만들려고 한다. 책꽂이의 설계도를 작성하고 보니 길이가 L1, L2, ..., LN(1≤Li≤50000)인 N(1≤N≤20000)개의 널빤지가 필요하다는 사실을 알았다. 지헌이는 목재상에서 필요한 크기(L1+L2+...+LN)의 널빤지를 구입했으나 필요한 크기로 자르기 위해서는 톱이 필요했다. 지헌이는 아무리 찾아 보아도 톱이 없다는 것을 알고 절망에 빠졌다. 이런 모습을 지켜보던 종현이는 지헌이에게 자신이 톱을 빌려줄테니 그 대가로 널빤지를 자를 때마다 그 널빤지의 길이만큼의 비용을 지불하라고 했다. 예들 들어 길이가 10인 널빤지를 둘로 나누게 되면 10의 비용을 지불하라는 것이다. 지헌이는 자신의 어려움에 처해 있다는.. 2020. 1. 9.
5 Problem C : 루빅의 사각형 4*4 격자판에 1~16까지 정수 번호가 매겨진 16개 타일 타일을 정사정적으로 돌려 놓기 위해 타일을 움직이는 순서를 출력하는 프로그램을 작성 - dfs - 가치치기 - 완성하기 위한 step 이 존재하는데, 최소한 몇 개는 맞아야 한다, 아닌 경우 return - dfs() : step 을 파라미터로 받음 - okcnt() : 현재까지 돌린 타일과 정상 타일과 비교해서 몇 개나 맞는지 확인 - rotate() : 배열 이동하는 것 간편하게 함수 만들음 #include int tile[6][6], ans = 8; struct data { int rc, num, cnt; } moving[10], moveans[10]; // 원하는 그림과 얼마나 같은지 int okcnt() { int cnt = 0; fo.. 2019. 11. 13.
7 Problem B : Bit_ImageMap2 영문 대문자 100개로 이루어진 STR배열 문자를 복원할 수 있도록 100*100 MAP 공간에 비트 형태로 저장하는 encode() 함수 설계 랜덤으로 생성된 200*200 IMG 이미지의 임의의 위치에 복사한 후, 노이즈 1을 1/3 확률로 넣음 그리고 4개의 bit씩 묶어서 그 합을 100*100 CNT 에 보관함 이 CNT 배열을 분석하여, 최초 저장된 STR 문자 배열을 복원하는 decode()함수 작성 - encode() : STR배열을 받아서 4*4을 1로 만드는 패딩을 만든다음에, 하나의 캐릭터를 받아서 3*5배열에 정상bit를 넣고 3*1을 1로 만들음 - 그리고 임의의 IMG 가 생성된 뒤에 오프셋된 위치에 encode를 통한 MAP을 붙이고 난 뒤 - 새로운 노이즈 1이 들어가게 됨 .. 2019. 11. 13.
7 Problem A : Bit_ImageMap1 가로 세로 각각 256개의 bit로 이루어진 imagemap이 있음 이 imagemap 내에 0~14 사이의 정수 4096개를 저장하는 encode() 함수를 설계 변환된 imagemap 이미지는 노이즈에 의해 0 또는 1로 변경 될 수 있고, 90, 180, 270도 회전 가능, 가로 또는 세로 방향으로 대칭 변경 가능하다 이 imagemap 데이터를 분석하여, 최초 저장된 4096개 정수를 반환하는 decode() 함수를 작성 - encode : data[4096]을 입력 받아 4개 비트에 저장하는데, 각 모서리는 0을 그리고 나머지 3개는 정상 비트를 입력 - 패턴찾기에 사용할 0과 1을 넣음 - 노이즈, 회전, 플립 - decode : 먼저 패턴을 찾는다 압축한 좌표로 패턴을 찾아서 회전을 했는지.. 2019. 11. 13.
6 Problem B : 개미마을4 이 차원 배열에서 개미가 대피소로 대피하는 것 - 각 개미들이 가장 가까운 곳을 dest 에 저장, 다른 곳으로 이동 했을 때의 차이를 저장 - 저장 할 때 minheap 을 구현하여 저장함 - go : 만약 대피소가 넘치면, 추가 비용을 비교하여 이동시킴 - gogo : 비교이동 한 후 새로운 값을 힙에 대입 - step : 이동 하는 것 구현, 방향, 그리고 다른 개미를 만났을 때 구현 #include #include #define MAXN 1000 enum { right, down, left, up }; static int N, MoveCount, AnsCount, MaxShelter; static char MAP[MAXN + 1][MAXN + 1], userMAP[MAXN + 1][MAXN + 1.. 2019. 11. 12.

티스토리툴바