본문 바로가기

삼성전자 알고리즘/정올

(17)
3138 : 암호 테이블 복원 // user 부분================================================================ int map[35][35], hint[5000][2][2], chk[5000]; int hn, empty, N, M; char q[4][4]; void encode(char b[][65]) { int i, j; for (i = 0; i
3240 : 회원 참여도 분석1 //회원 참여도 //생각할 문제 //참여도가 가장 높은 회원과 가장 낮은 회원을 빠른 시간에 찾아내야 한다. //쿼리가 있을 때마다 순차 탐색을 하면 O(N^2)으로 시간 초과 //이진 탐색을 하기 위해서는 자료 추가 및 제거마다 정렬을 해야 하므로 역시 의미가 없다. //힙(heap): 완전 이진트리를 이용하여 부모가 항상 크거나(max heap) 항상 작도록(min heap) 자료를 구성하면 최대값 또는 최소값이 항상 루트에 위치하게 된다. //인덱스트리 or 세그먼트 트리 : 이진트리로 특정 구간의 자식 중 큰 값(max tree)또는 작은값(min tree)을 넣어서 루트에 최대값 또는 최소값이 위치하도록 구성되는 자료 구조 //힙이나 인덱스 트리 등 모두 부모만 따라서 갱신하면 되므로 자료를 추..
16. 3181 : 족보 만들기 1. data node 생성 struct data { char name[13]; data* parent, * next, * child; data() { parent = next = child = NULL; } data(char na[], data* pa, data* ne, data* ch) { strcpy(name, na), parent = pa, next = ne, child = ch; } }*root, *cur; 2. strcmp 문자열 비교 함수 int strcmp(const char* s, const char* t) { while (*s && *s == *t) ++s, ++t; return *s - *t; } 3. mystrcpy 문자열 복사 함수 /// 문자열 dest에 문자열 src를 복사 v..
15. 3203 : 꿀벌의 여행 DFS문제 1) 생각할 문제 -패턴의 시작 위치를 어떻게 결정할 것인가? -패턴의 시작 위치가 결정되었다면 각 벌들은 패턴의 어느 위치로 이동시킬 것인가? -이동하는 과정에서 동시에 같은 위치로 이동하게 되면 어떻게 처리할 것인가? 2) 시작 위치의 결정 -시작 위치로 결정할 수 있는 범위 (0,0) ~ ( 100 - height, 100 - width ) -위의 범위 중 꿀벌의 위치와 전혀 겹치지 않는 곳은 최적의 결과가 나올 수 없다. -모든 위치에 대해 최대 이동 꿀벌의 이동거리가 최소인 점을 찾는다. ㄱ 패턴 범위 지정시 벌에 하나라도 겹치는 것이 유리하다. 가장 멀리 가는 벌이 총 이동 시간의 기준이 됨. 꽃과 벌이 매칭 가능한 경우의 수 = 7! (5040) 테스트케이스에 따라 부담스러울 수 ..
14. 1133 : Uniqueness 원본 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=413&sca=50&sfl=wr_subject&stx=UNIQUENESS&sop=and JUNGOL | Uniqueness > 문제은행 제한시간: 1000 ms 메모리제한: 64 MB 해결횟수: 683 회 시도횟수: 2137 회 N개의 문자열이 주어졌을 때, 동일한 문자열이 존재하는지 판단하는 프로그램을 작성하라. 문자열이란 사이에 공백이 없는 연속된 알파벳 소문자열을 뜻한다. 문자열의 길이는 최소 1글자, 최대 20글자이다. 입력되는 문자열의 개수는 2개 이상 10,000개 이하이다. www.jungol.co.kr 문제 풀이 : #include #include #define MAX (..
13. 1726 : 구간의 최대값1 문제 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=999&sca=50&sfl=wr_hit&stx=1726&sop=and JUNGOL | 구간의 최대값1 > 문제은행 제한시간: 1000 ms 메모리제한: 128 MB 해결횟수: 1300 회 시도횟수: 3132 회 입력의 첫번째 줄에는 수열을 이루는 원소의 갯수 N(1≤N≤50,000)과 구간의 갯수 Q(1≤Q≤200,000)가 공백을 사이에 두고 입력된다. 그 다음 N개의 줄에는 순서대로 서있는 원소의 숫자가 한줄에 하나씩 입력되는데, 이는 1이상 1,000,000이하이다. 그 다음 Q개의 구간의 시작 인덱스와 끝 인덱스 A, B가 공백을 사이에 두고 www.jungol.co.kr 문제 ..
12. 1141 : 불쾌한 날 원본 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=50&sfl=wr_subject&stx=%EB%B6%88%EC%BE%8C%ED%95%9C+%EB%82%A0&sop=and JUNGOL | 불쾌한 날 > 문제은행 제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 1866 회 시도횟수: 13585 회 농부 시현이의 N(1≤N≤80,000)마리의 소들은 "bad hair day"를 맞이하였다. 각 소들이 자신들의 촌스런 머리 모양을 부끄러워 하자, 시현이는 소들이 다른 소들의 머리 모양을 얼마나 알 수 있는지를 알고자 했다. i번째 소들은 키가 hi(1≤hi≤1,000,000,000) 이며, 동쪽(오른쪽)을 바라보고 ..
11. 1318 : 못생긴 수 원본 출처 : http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=597&sca=50&sfl=wr_subject&stx=%EB%AA%BB%EC%83%9D%EA%B8%B4&sop=and JUNGOL | 못생긴 수 > 문제은행제한시간: 1000 ms 메모리제한: 32 MB 해결횟수: 559 회 시도횟수: 1548 회 못생긴 수란, 소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 하며, 이를 수열로 늘어놓으면 다음과 같다. 1, 2, 3, 4, 5, 6, 8, 9, 10, 12... 이는 처음나오는 10개의 못생긴 수이며, 편의상 1을 포함하도록 하자. 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하라.jungol...