본문 바로가기

삼성전자 알고리즘

(65)
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. 꼭 알아야 하는 유형 1. 링크드리스트 동적할당을 정적할당으로 구현 --메인 밖에서 선언 typedef struct _node { int x; struct _node *next = nullptr; }NODE; NODE arr[1000 * 1000 + 10];//문제에서 나올 수 있는 모든 노드의 수(배열을 할당할 주소값으로 사용) int cnt = 0; --메모리 할당 NODE *newNode = &arr[cnt++]; --메모리 해제 cnt = 0; 2. 링크드리스트를 활용하여 만든 해시테이블(설정) const int MAX = 1 x = x; //Case 1 : 무작정 맨 앞에 연결 하는 방법 newNode->next = cur->next;//맨 앞에 노드 연결 cur->next = newNode;//해시연결해주기 //C..
15. 3203 : 꿀벌의 여행 DFS문제 1) 생각할 문제 -패턴의 시작 위치를 어떻게 결정할 것인가? -패턴의 시작 위치가 결정되었다면 각 벌들은 패턴의 어느 위치로 이동시킬 것인가? -이동하는 과정에서 동시에 같은 위치로 이동하게 되면 어떻게 처리할 것인가? 2) 시작 위치의 결정 -시작 위치로 결정할 수 있는 범위 (0,0) ~ ( 100 - height, 100 - width ) -위의 범위 중 꿀벌의 위치와 전혀 겹치지 않는 곳은 최적의 결과가 나올 수 없다. -모든 위치에 대해 최대 이동 꿀벌의 이동거리가 최소인 점을 찾는다. ㄱ 패턴 범위 지정시 벌에 하나라도 겹치는 것이 유리하다. 가장 멀리 가는 벌이 총 이동 시간의 기준이 됨. 꽃과 벌이 매칭 가능한 경우의 수 = 7! (5040) 테스트케이스에 따라 부담스러울 수 ..
21. C++ Programming 1. 데이터 처리, 복합데이터형 2. 루프와 관계 표현식, 분기 구문과 논리 연산자 3. 함수의 활용, 메모리 모델과 이름 공간 4. 객체와 클래스 5. 클래스와 동적 메모리 대입 6. 클래스의 상속, 프렌드 7. 예외, 기타 사항 8. String 클래스와 표준 템플릿 라이브러리 9. 입력, 출력, 파일 10. 엔디안 11. 함수 오버로딩 규칙 12. 인라인 함수 13. 레퍼런스 14. 구조체 15. 동적할당 16. 형변환 static_cast, reinterpret_cast
7. 5052 전화번호 목록 원본 출처 : https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net 문제 풀이 : #include #include #define NUM(X) ((X)-'0') typedef struct ..
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 (..