본문 바로가기

분류 전체보기61

[BFS] 전력망을 둘로 나누기 1. 위 문제와 같이 노드와 노드가 연결되어있는 문제의 경우, 인접관계행렬을 만들어 각 노드간 연결되어있을 경우 1, 연결되어있지 않을 경우 0으로 설정해, 배열을 만든다. 2. BFS를 이용해, 선을 하나씩 끊고, 복구하기를 반복하면서 " |두 전력망의 송전탑 개수 차| "가 가장 작은값을 반환한다. 3. BFS / DFS 모두 각 노드를 방문 했는지 안했는지를 나타내는 boolean[] visited를 생성해야 한다. 4. BFS에서는 Queue를 사용하는데, 처음 기준이 되는 노드를 넣어주고, 이 노드와 연결되어 있는 다음 노드를 추가하고 삭제하는데 사용 된다. 코드 import java.util.LinkedList; import java.util.Queue; class Solution { int[.. 2024. 2. 20.
시간 복잡도 계산 https://devraphy.tistory.com/284 시간복잡도 완전정복(1) 0. 시작에 앞서 요즘 백준을 통해 알고리즘 문제를 열심히 풀고있다. 문제를 작성하면 내 코드가 다른 사람들의 코드보다 10ms 정도 더 걸리는 경우도 있고, 올바른 답은 나오지만 시간초과로 인 devraphy.tistory.com 시간 복잡도를 코딩 테스트에 활용하는 방법 이제 시간 복잡도를 표현하는 방법이 빅오 표기법이라는 건 알았습니다. 그럼 빅오 표기법을 어떻게 활용하면 좋을까요? 코딩 테스트 문제에는 제한 시간이 있으므로 문제를 분석한 후에 빅오 표기법을 활용해서 해당 알고리즘을 적용했을 때 제한 시간 내에 출력값이 나올 수 있을지 확인해볼 수 있습니다. 그러면 문제 조건에 맞지 않는 알고리즘을 적용하느라 낭비하.. 2024. 2. 20.
HashSet 사용법(개념,특징,사용법) HashSet이란? HashSet은 Set 인터페이스의 구현 클래스입니다. 그렇기에 Set의 성질을 그대로 상속받습니다. HashSet의 특징 1. 객체를 중복해서 저장할 수 없고 하나의 null 값만 저장할 수 있습니다. 2. 저장 순서가 유지되지 않습니다. (만약 요소의 저장 순서를 유지해야 한다면 JDK 1.4부터 제공하는 LinkedHashSet 클래스를 사용) 3. Set 인터페이스를 구현한 클래스로는 HashSet과 TreeSet이 있는데, HashSet의 경우 정렬을 해주지 않고 TreeSet의 경우 자동정렬을 해준다는 차이점이 있습니다. 4. 비선형 구조이기에 순서가 없으며 그렇기에 인덱스도 존재하지 않습니다. 그렇기에 값을 추가하거나 삭제할 때에는 내가 추가 혹은 삭제하고자 하는 값이 S.. 2024. 2. 20.
int[] -> List<Integer> 반환? 메소드 리턴타입을 바꾸자 https://school.programmers.co.kr/learn/courses/30/lessons/42840 import java.util.*; class Solution { public int[] solution(int[] answers) { int[] user1 = {1,2,3,4,5}; int[] user2 = {2,1,2,3,2,4,2,5}; int[] user3 = {3,3,1,1,2,2,4,4,5,5}; //맞춘 개수를 담을 배열 int[] cnt = {0,0,0}; //가장 많이 맞춘 사람 넣는 리스트 List list = new ArrayList(); for(int i=0;i 2024. 2. 19.
[Java] ArrayList와 LinkedList의 차이 위 사진을 보면 알 수 있듯 ArrayList는 index가 있고, LinkedList는 각 원소마다 앞,뒤 원소의 위치값을 가지고 있다. 이러한 각각의 특징은 조회, 삽입, 삭제시에 성능의 차이를 발생시킨다. ArrayList ArrayList는 기본적으로 배열을 사용한다. 하지만 일반 배열과 차이점이 존재한다. 일반 배열은 처음에 메모리를 할당할 때 크기를 지정해주어야 하지만, ArrayList는 크기를 지정하지 않고 동적으로 값을 삽입하고 삭제할 수 있다. 조회 ArrayList는 각 데이터의 index를 가지고 있고 무작위 접근이 가능하기 때문에, 해당 index의 데이터를 한번에 가져올 수 있다. 데이터 삽입과 삭제 데이터의 삽입과 삭제시 ArrayList는 그만큼 위치를 맞춰주어야 한다. 위의.. 2024. 2. 18.
[Java] ArrayList 사용법 List 인터페이스 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현 https://velog.io/@roro/Java-List-ArrayList-LinkedList [Java] - List / ArrayList / LinkedList 중복을 허용하면서 저장순서가 유지되는 컬렉션을 구현 List 인터페이스 구현 클래스 저장순서 유지, 중복 허용 컬렉션 프레임워크에서 가장 많이 사용되는 컬렉션 클래스일반 배열과 인덱스로 velog.io ArrayList란? ArrayList는 자바의 컬렉션 프레임워크의 일부로 List 인터페이스를 상속받은 클래스 중 하나이다. ArrayList는 한번 생성하면 크기가 고정되는 배열과 다르게 부족한 공간을 자동으로 조정해주는 선형리스트 이다. 배열은 데이터를 추가, 삭제 .. 2024. 2. 18.

티스토리툴바