자료구조 + 알고리즘

이전에 봐왔던 이진검색에서는 중복 요소가 있을 경우에 중간인덱스를 리턴하는 구조이다. 갱신되는 구간의 중간인덱스와 찾는key값을 비교하는 방식이기 때문이다. 다음 사진을 보자. 동일 요소들 7중에서 7을 찾는 이진 탐색 결과, 중간 인덱스를 리턴한다. 하지만 이번에 풀어볼 문제에서는 중복요소의 중간 인덱스를 리턴하는 것이 아니라, 중복 요소 중 맨 앞의 인덱스를 찾아내는 것이 목적이다. 문제는 다음과 같다. (Doit! 자료구조와 함께 배우는 알고리즘 입문 자바편 117페이지 연습문제 ) 그냥 일반적인 이진검색 후에 리턴되는 인덱스에서부터 앞쪽으로 쭉 스캔하면 되는 문제다. 굉장히 간단하게 해결가능하다. 단지 그냥 아래 사진에서 하이라이트 친 부분처럼만 작성해주면 되잖아!! 이진탐색의 결과로 나온 key..

이진 탐색 과정을 출력하는 프로그램 작성하기 이진 탐색 과정 중, 현재 검색 중인 구간과 중앙요소를 표시해주는 프로그램을 작성하는 문제를 풀어보았다. (참고: "Doit 자료구조와 함께 배우는 알고리즘 입문 자바편" 117페이지의 연습문제다.) 완성된 실행 모습: 작성한 코드 프로그램의 구조는 다음과 같이 작성했다. - 실행부분인 메인메서드 - 이진 탐색을 수행하는 메서드: binSearch - 구간을 표시하는 메서드: intervalDesign ㅡ 메인메서드 먼저 메인메서드의 구조는 다음과 같다. 간단하다. 먼저 요솟수와 요소(정수) 내용을 Scanner로 입력받는다. 그리고 찾을 값을 입력하면 이진검색하는 메서드를 실행시킨다. 그리고 그 메서드가 반환한 인덱스를 기반으로, 원하는 값을 그 인덱스에서 ..

참고: Doit 자료구조+알고리즘 입문 자바편 | 117페이지 연습문제 Q3 다음의 메서드를 작성해야 한다. static searchIdx(int[] a, int n, int key, int[] idx) 인자의 형식에서 보면 알 수 있듯이, ArrayList같은 좋은 배열 형식을 사용해서는 안 된다. 그냥 순수한 배열 int[]를 사용하여 문제가 요구하고 있는 메서드를 작성해보자. 자 그럼 요솟수가 n인 배열 a에서, 원하는 key와 동일한 값을 가지는 요소의 인덱스를 반환하는 메서드를 만들어보자. 먼저 작성한 코드는 다음과 같다. package doit; import java.util.*; public class Q3 { static int searchIdx(int[] a, int n, int key,..

해시법(hasing) 데이터를 저장할 위치인 '인덱스'를 간단한 연산으로 구하는 것이다. 이렇게 구한 인덱스를 '해시값'이라고 한다. 마치 인덱스처럼 해시값을 통해서 데이터를 다룰 수 있게 된다. ㅡ 즉, 해시값은 데이터에 접근할 때 사용한다. ㅡ 데이터 검색, 추가, 삭제 효율이 있다. 해시는 배열의 단점을 커버한다 배열에서는 (추가, 삭제로 인한)요소 이동에 필요한 복잡도(time-complexity)가 O(n)이다(꽤 무거움). 배열 요소를 추가, 삭제할 때마다 하나씩 앞으로(뒤로) 쭉 밀어서 자리를 만드는 것을 다들 알 것이다. 해시에서는 (추가, 삭제로 인해)요소가 이동하더라도 다른 배열 요소들을 앞뒤로 옮기지 않아도 된다. ㅡ 그럼 어떤 원리로 해시의 요소를 재정렬할 필요가 없는 것일까? 다른..

문제 설명이 별로 안 친절하다! 그렇지만 학습하는 데는 지장이 없어서 딱히 상관 없다. Q4, Q5 배열 b의 모든 요소를 배열 a에 복사하는 메서드 copy와 rcopy를 작성하라고 했다. 그럼 적어도 b의 모든 요소가 a에 들어가게 해야 한다. 배열의 사이즈가 변경될 수도 있다는 것이다. 그렇지만 이지스퍼블리싱에서 제공한 연습문제 답안에서는 b의 모든 요소가 들어가게 하지 않는다. 배열 a의 사이즈가 더 작으면 b의 모든 요소가 들어갈 수 없게 짜여있었다. 그래서 이번 연습문제는 마음대로 연습했다. 어차피 로직만 알면 문제 없을 테니까..

Q11. 양의 정수의 자릿수 나는 맨 처음에 방법 1로 했는데정수의 자릿수를 세는 방법으로 방법2가 있다는 사실을 검색으로 알게되었고책의 답안을 열어보고 방법3을 새로 알게 되었다.num = num/10이 가능한 횟수를 통해 자릿수를 셀 수 있겠구나~~~ Q15. 여러 가지 직각이등변삼각형 만들기이 연습문제를 풀면서 for문을 원래 이렇게 많이 쓰는건가? 안쓰는 방법은 없나? 하고 생각했는데 답안에서 나와 같은 방법을 사용했다. 빈칸을 for문으로 채우는 것이 괜찮은가 보다. 참고하실분은 더보기 누르세요 ~.~더보기 Q16. n단의 피라미드 참고하실분 더보기 클릭 -ㅅ-더보기17번의 숫자 피라미드도 비슷한 논리~!단지 스타를 나타내는 for문에 i%10을 print했다는 차이.

종강을 했다!! 파이썬 과목도 A+ 가볍게 샷샷 ~>_< 이제 올해 상반기에 공부했던 자바를 이어서 단단히 하면서 자료구조랑 알고리즘을 학습하는데 집중할 계획이다 [Do it 자료구조와 함께 배우는 알고리즘 입문]을 단단히 공부하기!! 한빛미디어 책만 접해왔는데 지금 만나는 이책도 궁금하다~~! 이 책 : ㅇ 알고리즘과 자료구조를 혼자서도 정확하고 빠르게 배울 수 있도록 그 동안의 프로그래밍 교육 노하우를 이 책에 모두 담았다. ㅇ 개념 이해를 돕는 220개의 도해와 88개의 코딩 실습, 93개의 연습 문제까지 하고 나면 자바를 다루는 능력이 향상되는 건 물론 각종 시험도 대비할 수 있다. ㅇ 요구사항들을 해결할 힘을 스스로 키울 수 있도록 최대한 배려함. ㅇ 자료구조를 가지고 효율적인 알고리즘을 구현한..

ArrayList의 remove() 메소드 자료구조 요거 안하고 건너뛴것도 몰랐네 ㅠ,ㅠ ArrayList에서 리스트 값 삭제하는 remove, removeFirst, removeLast 메소드 구조는 어떤식으로 되어있는지 보고 가자 참고로 아래 유튜브 강의 보면서 학습중이다. https://www.youtube.com/watch?v=m-Csg_1Rxfc&list=PLuHgQVnccGMDsWOOn_P0EmAWB8DArS3Fk&index=14

ArrayList의 Iterator 부분을 건너뛰고 LinkedList를 학습했었다 ㄸㅣ로리!! 그래가꼬 다시 여기로 돌아왔다 ArrayList의 Iterator는 어떤 구조로 동작하게 되는지 학습 꼬 배울 것: ArrayList.ListIterator 클래스와 next() hasNext() previous() hasPrevious() ArrayList.ListIterator 클래스 ArrayList객체의 어떤 반복적인 작업을 처리하기 위해서는 ListIterator라는 객체가 필요하다. 이 객체를 리턴하는 메소드가 저 맨 오른쪽에 있는 listIterator() 웅웅 저 메소드를 호출하면 새로운 ListIterator객체를 만들어서 리턴하게 된다. 그럼 이제 ListIterator클래스를 작성해보자. ..

배울 구조 : ListIterator클래스 / next(), hasNext(), add(), remove() >>LinkedList.ListIterator 객체의 메소드의 자료구조>이터레이터에서 넥스트 넥스트 해가는 중에 add()로 객체를 추가할 수 있다. LinkedList.ListIterator i = numbers.listIterator(); i.add(5); 만약 위처럼 next()가 전혀 실행되지 않은 상황에서 add(Object)를 하게되면 LinkedList의 첫 번째 노드에 해당 객체를 저장하도록 하자. ListIterator()생성자 호출시 next=head;다. 또한 중간에 newNode가 들어갈 수도 있다. 그러면 lastReturned.next = newNode; 랑 newNode..