본문 바로가기

#자바#JAVA#알고리즘#DoIt#기본 알고리즘#

정보처리기사 실기 Daily 문제 17 출처 : [2021년 제2회 기사 실기 출제예상 문제] (6과목) 프로그램밍 언어 활용 - 65 : 네이버 카페 (naver.com) ​ 다음은 링크드 리스트를 이용하여 스택을 구현한 프로그램이다. 밑줄에 들어갈 키워드를 쓰시오.` ​ tyepdef struct node { int data; //저장 데이터 struct node *next; // 노드의 다음 주소를 저장할 포인터 변수 }Node; ​ void push(Node *head, int data) { Node *end = (Node *)malloc(sizeof(Node)); //malloc 함수를 이용하여 메모리 할당하여 노드를 하나 생성 end -> ____(1)____ = head->next; // head의 next 값을 end의 end의.. 더보기
[자바 Do It! 알고리즘]Chapter08 리스트(포인터로 연결 리스트 만들기) (3) 앞의 LinkedList 의 함수들을 이용한 연결리스트 프로그램(LinkedListTester) 입니다. ​ 번호를 입력하고 이름을 입력해야 하는데.. 번호가 왜 안나오는지 모르겠습니다.. ​ 더보기
[자바 Do It! 알고리즘]Chapter08 리스트(포인터로 연결 리스트 만들기) (2) 이어서.. (연결리스트는 설명이 기네요.. 요즘 학원진도도 많이 나가서, 알고리즘은 천천히 나가겠습니다. 동빈나 게시판도 해야해서..) ​ 연결 리스트가 비어 있는지 판단하는 방법 head == null // 연결 리스트가 비어 있는지 확인합니다. ​ 노드가 1개인 연결리스트를 판단하는 방법 head.next == null // 노드가 1개인지 확인합니다. ​ 노드가 2개인 연결리스트를 판단하는 방법 head.next.next == null // 노드가 2개인지 확인합니다. ​ 꼬리 노드인지 판단하는 방법 p.next == null // p가 가리키는 노드가 꼬린 ㅗ드인지 확인합니다. ​ [검색을 수행하는 search 메서드] 1. search 메서드는 어떤 조건을 만족하는 노드를 검색합니다. 2. 검색.. 더보기
[자바 Do It! 알고리즘]Chapter08 리스트(포인터로 연결 리스트 만들기) [포인터로 연결 리스트 만들기] 1. 연결 리스트에 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면 삽입,삭제 시 모든 데이터를 밀고 당기는 문제를 해결할 수 있습니다. class Node { E data; // 데이터 Node next; // 다음 노드를 가리키는 포인터 } 2. 데이터용 필드인 data와는 별도로 자기 자신과 같은 클래스형의 인스턴스를 참조하기 위한 참조용 필드 next를 가집니다. 일반적으로 이런 클래스 구조를 자기 참조(self-referential)형이라고 합니다. 3. Node는 제네릭으로 구현되므로 데이터 형 E는 임의의 클래스형이 허용됩니다. 4. 필드 data 형인 E는 참조형입니다. 노드 형이 클래스 Node 형인 연결 리스트를 클래스 Link.. 더보기
[자바 Do It! 알고리즘]Chapter08 리스트(선형 리스트) 리스트는 데이터를 순서대로 나열한 자료구조입니다. 여기서는 가장 간단한 리스트 구조를 가지고 있는 선형 리스트에 대해 살펴보겠습니다. ​ [선형리스트] 1. 리스트의 데이터는 노드(node) 또는 요소(element)라고 합니다. 각각의 노드는 데이터와 다음 노드를 가리키는 포인터를 가지고 있습니다. 처음과 끝에 있는 노드는 특별히 각각 머리 노드(head node), 꼬리 노드(tail node) 라고 합니다. 또한 하나의 노드에 대해 바로 앞에 있는 노드를 앞쪽 노드(predecessor node), 바로 뒤에 있는 노드를 다음 노드(successor node)라고 합니다. [배열로 선형 리스트 만들기] class Person { int memNo; //회원번호 String name; // 이름 St.. 더보기
[자바 Do It! 알고리즘]Chapter07 문자열 검색 (Boyer-Moore법) Boyer-Moore법은 브루트-포스법을 개선한 KMP법보다 효율이 더 우수하기 때문에 실제로 문자열 검색에 널리 사용하는 알고리즘입니다. ​ [Boyer-Moore법] 1. 패턴의 마지막 문자부터 앞쪽으로 검사를 진행하면서 일치하지 않는 문자가 있으면 미리 준비한 표에 따라 패턴을 옮길 크기를 정합니다. 2. 텍스트 안에서 패턴에 들어 있지 않은 문자를 찾으면 해당 위치까지의 문자는 건너뛸 수 있습니다. ​ 3. 이렇게 패턴의 길이를 n이라고 하면 현재 검사하고 있는 텍스트의 문자 위치로부터 '다음에 검사할 패턴의 마지막 문자 위치'가 n만큼 떨어질 수 있도록 패턴을 옮기면 됩니다. 4. Boyer-Moore 알고리즘도 각각의 문자를 만났을 때 패턴을 옮길 크기를 저장할 표(건너뛰기 표)를 만들어야 합.. 더보기
[자바 Do It! 알고리즘]Chapter07 문자열 검색 (KMP법) [KMP 법] 1. KMP법은 브루스-포스법과 달리, 검사했던 위치 결과를 버리지 않고 이를 효율적으로 활용하는 알고리즘입니다. 2. 텍스트와 패턴의 겹치는 부분을 찾아내어 검사를 다시 시작할 위치를 구합니다. 이런 방법으로 패턴을 최소의 횟수로 옮겨 알고리즘의 효율을 높입니다. 3. 하지만 몇 번째 문자부터 다시 검색을 시작할 지 패턴을 이동시킬 때 마다 다시 계산해야 한다면 높은 효율을 기대할 수 없습니다. 그래서 '몇 번째 문자부터 다시 검색할지'에 대한 값을 미리 '표'로 만들어 이 문제를 해결합니다. 1) 표를 작성할 때는 패턴 안에서 중복되는 문자의 나열을 먼저 찾아야 합니다. 이 과정에서 KMP 법을 사용합니다. 2) 패턴 안에서 중복되는 문자의 나열을 찾기 위해 패턴끼리 겹쳐놓고 생각해 보.. 더보기
[자바 Do It! 알고리즘]Chapter07 문자열 검색 (브루트-포스법) [문자열 검색이란?] 1. 문자열 검색이란 어떤 문자열 안에 다른 문자열이 들어 있는지 조사하고 들어 있다면 그 위치를 찾아내는 것을 말합니다. 2. 예를 들어 문자열 "STRING", "KING" 에서는 "IN"을 검색하면 문자열 검색에 성공합니다. 하지만 문자열 "QUEEN"에서 "IN"을 검색하면 문자열 검색에 실패합니다. 그러면 지금부터는 이해하기 쉽게 검색할 문자열을 패턴(pattern)이라 하고 문자열 원본을 텍스트(text)라고 하겠습니다. ​ [브루트-포스법] 1. 텍스트 "ABABCDEFGHA"에서 패턴 "ABC"를 브루트-포스법을 사용해 검색하는 순서입니다.. ABABCDEFGHA ABC 1) 텍스트의 첫 문자 'A'부터 시작하는 3개와 문자와 "ABC"가 일치하는지 검사합니다. 'A'.. 더보기

티스토리툴바