본문 바로가기

분류 전체보기215

원형 연결 리스트 원형 연결 리스트- 마지막 노드가 첫 번째 노드를 가리키는 리스트(마지막 노드의 링크 필드가 첫 번째 노드의 주소)- 하나의 노드에서 모든 노드로 접근 가능- 노드의 삽입과 삭제가 단순 연결 리스트보다 용이 - 리스트의 끝에 노드를 삽입하는 연산이 단순 연결 리스트보다 효율적- 단순 연결 리스트에서 리스트의 끝에 노드를 추가하려면 head에서부터 링크를 따라 노드 개수만큼 진행- 원형 연결 리스트에서는 아래와 같이 헤드 포인터가 마지막 노드를 가리키도록 구성하여 효율적인 처리 가능- 헤드 포인터 head가 마지막 노드를 가리키고 있음- 첫 번째 노드는 head->link가 가리키고 있음- 리스트의 마지막에 노드를 삽입하거나 삭제하기 위해 리스트의 끝까지 갈 필요 x원형 연결 리스트 정의- 원칙적으로 헤드.. 2024. 7. 19.
단순 연결 리스트의 연산 구현 - 앞에서는 노드를 하나씩 만들어 서로 연결- 리스트가 커지면 위 방법보다는 추상 데이터 타입에 정의된 전용 함수들을 통하여 노드를 추가하는 것이 편리insert_first(): 리스트 시작 부분에 항목 삽입insert(): 리스트 중간 부분에 항목 삽입delete_first(): 리스트 첫 항목 삭제delete(): 리스트 중간 항목 삭제print_list(): 리스트를 방문하여 모든 항목을 출력- 위 함수들을 작성할 수 있다.단순 연결 리스트 정의ListNode* head;- 단순 연결 리스트는 원칙적으로 헤드 포인터만 있으면 됨 삽입 연산 insert_first()- 리스트의 첫 부분에 새로운 노드 추가ListNode* insert_first(ListNode* head, element value);.. 2024. 7. 19.
단순 연결 리스트 단순 연결 리스트- 노드들이 하나의 링크 필드를 가짐- 이 하나의 링크 필드를 이용하여 모든 노드들이 연결- 마지막 노드의 링크 필드 값은 NULL노드의 정의: 자기 참조 구조체- 자기 참조 구조체는 자기 자신을 참조하는 포인터를 포함하는 구조체- element 타입의 데이터를 저장하는 data 필드- 포인터를 저장하는 link 필드- link 필드는 ListNode를 가리키는 포인터로 정의typedef int element;typedef struct { //노드 타입을 구조체로 정의 element data; struct ListNode* link;}ListNode;- 노드의 구조는 정의하였지만 아직 노드는 생성되지 않음- 구조체 ListNode는 노드를 만들기 위한 설계도에 해당- ListNode로 실.. 2024. 7. 19.
백준 1269: 대칭 차집합(java) 문제풀이 대칭 차집합은 (A의 원소 개수) + (B의 원소 개수) - 2*(A, B 교집합의 원소 개수) 로 구할 수 있으므로 이를 이용해 풀이한다. A와 B 교집합의 원소 개수를 구하기 위해 이진 탐색을 사용했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStrea.. 2024. 7. 19.
백준 14425: 문자열 집합(java) 문제풀이 앞의 탐색 문제들과 동일하게 풀이한다. N, S에 포함된 문자열, M, 검사해야 하는 문자열들을 입력받은 후 nArr에 대해 이진 탐색을 진행해 mArr[i] 요소가 포함되었는지 판단해 주면 된다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=new BufferedReader(new InputStreamRead.. 2024. 7. 19.
백준 10815: 수 찾기(java) 문제풀이 BufferedReader와 StringTokenizer를 이용해 N. 적혀있는 정수, M, 구해야 할 정수를 입력받고 저장한 후 이진 탐색을 이용하여 판단하면 된다. 이진 탐색 알고리즘을 구현하지 않고 Arrays.binarySearch()를 사용하여 풀이하였다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br=.. 2024. 7. 19.

티스토리툴바