본문 바로가기

개인 공부/알고리즘13

[ 이론을 한 번에 ] BFS 이론 뿌수기 1. 개념적인 이론 부분참고한 이론 강의 : https://inf.run/hpRtM BFS (너비 우선 탐색) | Do it! 알고리즘 코딩테스트 with JAVABFS (너비 우선 탐색)www.inflearn.com 1) BFS의 기본 이론BFS란?너비 우선 탐색. 즉, 그래프를 완전 탐색하는 방법 중 하나(DFS와 동일)시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘FIFO(선입선출) 탐색.  Queue 자료 구조 사용!시간 복잡도(노드 수 :  V, 엣지 : E) : O(V + E)탐색 시 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장  2) BFS의 핵심 동작 이론BFS를 시작할 노드를 정한 후.. 2025. 2. 24.
[ 코테 준비 PGS ] 코딩 테스트 합격자 되기(자바 편) - Ch 5 문제 편 Ch 05. 배열배열 제어하기[ 문제 ]정수 배열을 하나 받는다. 배열의 중복값을 제거하고 배열 데이터를 내림차순으로 정렬해서 반환하는 solution() 함수를 구현하세요.제약 조건- 배열 길이는 2이상 1,000 이하이다.- 각 배열의 데이터 값은 -100,000 이상 100,000 이하이다. 입출력 예입력출력[ 4, 2, 2, 1, 3, 4 ][ 4, 3, 2, 1 ][ 2, 1, 1, 3, 2, 5, 4 ][ 5, 4, 3, 2, 1 ] 해당 문제는 구현된 메서드를 사용하는 것이 좋다.stream() 메서드를 통해 stream으로 변환한다.해당 stream의 프리미티브 타입인 IntStream의 데이터를 boxed()를 통해 레퍼런스 타입인 Integer로 변환한다.distinct() 메서드를 통.. 2024. 8. 6.
[ 코테 준비 PGS ] 코딩 테스트 합격자 되기(자바 편) - Ch 5 Ch 05. 배열배열 개념배열은 인덱스와 값을 일대일 대응해 관리하는 자료구조데이터를 저장할 수 있는 모든 공간은 인덱스와 일대일 대응하므로 어떤 위치에 있는 데이터든 한 번에 접근할 수 있다.어디에 있는지만 알면 빠르게 탐색할 수 있으며 해당 접근 방식을 임의 접근(random access)라고 한다. 배열과 ArrayList의 차이점은 배열은 처음 선언할 때 배열의 크기가 결정되고, ArrayList는 크기가 동적이라는 것이다.따라서 정확한 데이터의 개수를 알 수 있다면 코드가 더 간결하고 속도가 더 빠른 배열을 사용하면 되고, 저장해야 할 데이터의 개수를 정확히 알 수 없다면 ArrayList를 사용하면 된다.엄밀히 말하자면 ArrayList도 초기에 크기가 결정되지만 동적으로 변하는 것처럼 구현되.. 2024. 7. 30.
[ 코테 준비 PGS ] 코딩 테스트 합격자 되기(자바 편) - Ch 4 Ch 04. 코딩 테스트 필수 문법프리미티브 타입과 레퍼런스 타입프리미티브 타입(primitive type)이란?int, long, float, double과 같은 타입레퍼런스 타입(reference type)이란?Integer, Long, Float, Double과 같은 타입참조형 변수이므로 연산 속도가 프리미티브 타입보다 느리다.컬렉션 프레임워크 등에서 정수형 또는 부동소수형을 저장할 때 사용하기 때문에 꼭 알아야 한다.정수형양의 정수, 음의 정수, 0정수형 비트 연산연산자의미 a ^ bxor~anota 왼쪽 시프트 ( a에 2²를 곱한 것과 동일)a >> 1오른쪽 시프트 (a를 2¹로 나눈 것과 동일) 부동소수형소수를 저장할 때 사용엡실론을 포함한 연산에 주의하라엡실론이란? 자바는 부동소수형 데이터.. 2024. 7. 25.