목록알고리즘 (6)

다잘하고싶어

백준 1946. 신입사원 (Comparator 를 사용하여 객체배열 오름차순)

Person 객체를 생성해서 멤버변수로 서류등수와 면접등수를 선언했다 Comparator 를 이용하여 객체배열을 서류등수 기준으로 오름차순 정렬한 후, 면접 등수를 비교하여 신입사원으로 채용가능한 숫자를 증가시키는 방향으로 진행했다. 이미 서류기준 정렬이 되어 있으므로, 다음인덱스의 서류 등수는 이전 인덱스의 서류 등수보다 낮다 따라서 현재 인덱스의 면접 등수는 그동안의 이전 인덱스들의 면접 등수보다 높아야 한다 for 돌면서 min 값을 갱신하고, 들고가면서 비교해야한다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java..
알고리즘 2024. 1. 31. 15:10
length, length(), size()

함수 길이를 반환하는 데이터 타입 length 배열 length() 문자열 (String Object) size() 컬렉션 프레임워크 타입 (ArrayList, ..) 배열과 문자열은 immutable (불변의) 한 특징을 가진다. 그리고 모든 최상위 Collection의 하위 클래스는 mutable한 특징을 갖는다. 따라서 “length” 라는 것을 봤다면, 그건 constant(=immutable) 변수일 것이다. 이와 반대일 때 “size”를 볼 수 있다. Immutable Object란 생성 후 변경불가능한 객체 를 의미한다. 대표적인 Immutable 클래스로는 String, Boolean, Integer, Float, Long 등이 있다. REFERENCE : Stackoverflow Diff..
알고리즘 2022. 11. 3. 10:42
[알고리즘] BFS 너비우선탐색

풀이방법 1. 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 2. 큐에서 값을 꺼내고 그 칸의 상하좌우로 인접한 칸에 대해 3번을 진행한다. 3. 해당 칸을 이전에 방문햇다면 아무것도 하지않고, 처음으로 방문햇다면 방문했다는 표시를 남기고 해당칸을 큐에 삽입 4. 큐가 빌 때까지 2번을 반복한다. -> 모든 칸이 큐에 1번씩 들어가므로 이때의 시간복잡도는 칸이 N개 일때 O(N). -> 만약 행이 r개 이고 열이 c개이면 O(rc). (+)시간복잡도 관련 게시글 https://22chaechae.tistory.com/7 [알고리즘] 빅오표기법(Big-O Notation), 시간복잡도, 공간복잡도 빅오표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 예1) 6N+5 의 경우, 총 소요시..
알고리즘 2022. 10. 6. 17:38
[알고리즘]BufferedReader 사용

Scanner 보다 훨씬 처리속도 빠르다. 코딩테스트 준비중이라면 그냥 이거 쓰기. 선언 방법 암기 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 입력시에는 readLine(); 이라는 메소드를 사용. String으로 리턴 값이 고정되어 있으므로, 다른 타입으로 입력을 받고자 한다면 반드시 형변환이 필요하다. (+) 예외처리를 반드시 필요( throws IOException 사용하기 ) 데이터 가공 방식 암기 BufferedReader를 통해 읽은 데이터는 개행 문자 단위(Line 단위)로 나누어지므로 이를 공백 단위로 데이터를 가공하고자 할때는 StringTokenizer 나 String.split() 함수 사용하기...
알고리즘 2022. 10. 6. 17:26
[알고리즘] 빅오표기법(Big-O Notation), 시간복잡도, 공간복잡도

빅오표기법 : 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 예1) 6N+5 의 경우, 총 소요시간은 5보다는 6N에 좌우된다.이때 상수 6도 제외하고 그냥 N에 집중하는 것. => O(N) 예2) 2N+10logN의 경우 N이 커질수록 10logN보다는 2N이 훨씬 클테니 2N만 남기고, 상수도 제외함. => O(N) 예3)N2(제곱)+2N+4 => O(N제곱) 시간복잡도 뒤로 갈 수록 시간 복잡도의 차이가 수행시간에 아주 큰 영향을 준다. 이때 O(2의N승) 은 N이 25이하 정도로 아주 작은 수가 아니면 코딩테스트 시간 복잡도를 통과하기 어렵다. 팩토리얼은 그보다 더 큰 폭으로 시간 복잡도가 올라가기 때문에 11이하의 수가 아니면 시간 제한 통과하기가 어렵다. 공간복잡도 : 입력의 크기와..
알고리즘 2022. 10. 6. 16:32
알고리즘 개념 공부 순서

8가지 개념 순서대로 익히기 1. 완전탐색 2. bfs 3. dfs 4. 다이나믹 프로그래밍(LIS, LCS, 냅색..) 5. 트리탐색(트리dp, dp적용..) 6. 이분탐색 7. 다익스트라 문제 8. 위상정렬 문제 - 각 개념에 대해 구글링, 블로그, 강의 등을 통해 간단하게 익히기 - 기초 문제 풀어보고, 10분정도 고민 후 풀리지 않는다면 정답을 참고해서 익힌다. 더 길게 고민하는 건 실력이 쌓이면 해보기
알고리즘 2022. 9. 21. 14:31
이전 Prev 1 Next 다음