더 부지런해지기 위한 블로그

개발 공부하며 기록하는 블로그 입니다.

자바알고리즘

DFS(Depth First Search) 깊이 우선탐색 위에서 아래로 탐색하는 것 최고 조상 : 루트 노드 데이터 하나, 주소두개를 저장하는 Node 클래스를 만든다. 부모(lt -> 자식 주소 / rt -> 자식주소) 어디서 부터 훑고 가느냐에 따라 전위순회 : 부모 > 왼쪽자식 > 오른쪽 자식 방향 중위순회 : 왼쪽 자식 > 부모 > 오른쪽 자식 후위순회 : 왼쪽 자식 > 오른쪽 자식 > 부모 (중요 병합정렬) 말단 노드엔 값이 없으므로 null이면 끝나게 한다. 아래는 재귀로 구현한 코드인데 스택에 쌓이면서 돌아간다. class Node{ //이진트리 순회(깊이우선탐색) int data; Node lt, rt; //주소를 저장 public Node(int val) { data=val; lt=rt=..

2021. 9. 4.

자바알고리즘

나 자신을 부르는 재귀함수 특이하게도 재귀함수는 "스택영역"에 "스택프레임"을 형성할 수 있다. 메모리의 스택(stack) 영역 : 함수의 호출과 관계되는 지역 변수와 매개변수가 저장되는 영역 스택 프레임(stack frame) : 스택 영역에 차례대로 저장되는 함수의 호출 정보 원리 : 함수가 호출되면 -> (매개변수, 지역변수, 복귀주소) 가 메모리에 계속 쌓이다가(push()) -> 끝나면 pop()하면서 소멸 이러한 스택 프레임 덕분에 함수의 호출이 모두 끝난 뒤에, 해당 함수가 호출되기 이전 상태로 되돌아갈 수 있다. import java.util.Scanner; public class Recursive1 { //재귀함수로 1부터 N까지 출력 public void DFS(int n) { if(n..

2021. 9. 3.

자바알고리즘

선택정렬 : i 값 과 구간을 줄여나가며 비교한다. 가장 작은 값이 i가 된다 버블정렬 : 이웃과 비교, 파도타기하면서 뒤에서부터 정렬됨 삽입정렬 : 앞에서부터 가는데 i를 중간에 끼워넣는다.(크면 밀고 작으면 break) 나는 가장 작은 수를 찾아서 앞에다 넣는 알고리즘을 사용하였는데 답안에서는 한칸 범위 돌면서 계속 1:1 비교하는 방법이었다. 선택정렬 : 한바퀴씩 돌면서 제일 작은숫자를 찾음 for(int i=0;i

2021. 9. 2.

자바알고리즘

TreeSet은 중복되는 데이터가 들어오면 저장하지 않음! 그리고 자동 정렬되는 이진트리이다. 기본이 오름차순인데 Collections.reverseOrder() 하면 내림차순 정렬 된다. TreeSet Tset = new TreeSet(Collections.reverseOrder()); 값 추가 : Tset.add(143); 해당값 삭제 : Tset.remove(143); 원소 갯수 : Tset.size(); 첫번째 원소 : Tset.first(); (오름차순일땐 최소값, 내림차순일땐 최대값 출력됨) 마지막 원소 : Tset.last(); (반대경우) + 참고로 set은 인덱스를 사용하지 않는다. set은 순서가 없어서 list 처럼 출력 시 .get으로 출력이 안된다. 따라서 Iterator 객체를 ..

2021. 8. 22.

자바알고리즘

HashMap map = new HashMap(); 카운팅 (있으면 꺼내서 1더하고 다시 넣음 / 없으면 그냥 더하고 넣음) : map.put(x, map.getOrDefault(x,0)+1); key 가져오기 : map.keySet(); value 가져오기 : map.get(key); key 존재여부 (T/F) : map.contains(key); key갯수 : map.size(); key삭제 (특이하게도 value 반환) : map.remove(key); 전부 지우기 : map.clear(); map 복사 (origMap은 복사할 맵) 1) 생성자를 이용 HashMap map = new HashMap(origMap); 2) clone() 을 이용 HashMap map = (HashMap)origMap..

2021. 8. 21.