Algorithm
Java와 자료구조 - 배열
Java와 자료구조 - 배열
2022.03.29특정 타입의 데이터를 연속된 형태로 묶어놓은 자료구조로, 인덱스로 데이터에 접근할 수 있어 접근에 대한 시간복잡도가 매우 낮다. ( O(1) ) 배열을 선언할 때 메모리를 할당해야 한다. 간단하게 계산할 수 있다. (타입의 크기) * (배열의 크기) int[100][100]크기의 배열을 선언하면 4 * 100 * 100이 메모리에 할당된다. 정해진 타입의 데이터를, 입력 길이가 변하지 않을 때 배열을 사용하면 편하다. 구현이 간단하고 이해하기 쉬우며 앞에서 살펴봤듯 데이터에 접근하는 속도가 매우 빠르다는 장점이 있다.
Java와 자료구조 - Collection Framework 2
Java와 자료구조 - Collection Framework 2
2022.03.28Collection인터페이스를 구현하는 컬렉션들과 Map에 대해 이어서 살펴보자. HashSet Set인터페이스를 구현한 컬렉션이며, 역시 중복을 허용하지 않고 순서가 유지되지 않는다. 지정된 순서를 보장하지 않고 자체적인 저장방식에 의해 순서가 결정되기에, 순서가 중요한 경우는 LinkedHashSet 컬렉션을 사용하는 편이 합리적이다. 여기서 Hash는 해시 함수(Hash Function)를 이용해 데이터를 해시테이블에 저장하고 검색하는 기법을 의미한다. 해시를 통해 데이터가 저장된 위치를 빠르게 알 수 있어 많은 데이터 중 원하는 데이터를 빠르게 찾아올 수 있다. 해싱 기법에서 사용하는 자료구조는 배열과 링크드 리스트로 구성된다. 저장할 데이터의 키 값을 해시함수를 통해 배열의 한 요소를 얻고, 연..
Java와 자료구조 - 배열 / 정렬
Java와 자료구조 - 배열 / 정렬
2022.03.19배열 sort() : 배열을 오름차순으로 정렬할 때 사용한다. binarySearch() : 배열에서 지정한 값이 저장된 위치를 찾을 때 사용한다. (중복되는 값이 있을 경우 무작위) 이진 검색은 배열의 검색범위를 절반씩 줄여가며 검색하기 때문에 빠른 속도로 검색할 수 있다. 정렬 배열을 정렬할 때 Arrays.sort()메서드를 자주 사용했는데, 사실 Character클래스의 Comparable의 구현에 의해 정렬되고 있었다. 정렬에 필요한 인터페이스로 Comparator와 Comparable이 있다. 같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들에 대해서 (Integer, String...) Comparable인터페이스가 정의돼있고, 기본적으로는 오름차순으로 정렬을 수행한다. public i..
Java와 자료구조 - Collection Framework 1
Java와 자료구조 - Collection Framework 1
2022.03.19Collection : 가장 기초가 되는 인터페이스. List와 Set를 상속시킨다. List : Order (O) / replacement (O) - ArrayList, LinkedList, Stack, Vector... Set : Order (X) / replacement (X) - HashSet, TreeSet.. Map : List와 Set과는 다른 형태로 컬렉션을 다룬다. key) Order (X) / Replacement (X) value) Order (X) / Replacement (O) - HashMap, TreeMap, Hashtable, Properties... Collection인터페이스 add clear contains equals isEmpty remove iterator ......
링크드 리스트 (Linked List)
링크드 리스트 (Linked List)
2022.03.07배경 기존 배열은 고정된 크기를 가지고 있었고, 이 부분을 개선하기 위해 자동으로 크기가 관리되는 동적 배열의 필요성이 확대됐고, 링크드리스트가 도입됐다. 싱글 링크드 리스트 (Singly Linked List) 데이터가 추가될 때 마다 데이터와 다음 데이터의 주소를 생성한다. 미리 데이터 공간을 할당하지 않고 사용할 수 있어 편리하지만, 데이터들을 연속적으로 이어 주기 위해 다음 데이터의 주소를 담고 있는 데이터 공간을 사용해야 해서 저장공간의 효율은 좋지 않으며, 같은 이유로 데이터에 접근하는 속도도 기존 배열보다 느리다. 또한 중간에 끼어 있는 데이터를 삭제할 때도 앞뒤 데이터의 연결을 재구성해야 하는 등 추가 작업이 필요하다. // 코드 추가 예정 이중 링크드 리스트 (Doubly Linked L..
[백준] 14888 연산자 끼워넣기 - Java
[백준] 14888 연산자 끼워넣기 - Java
2022.03.06N과 M 시리즈 문제들처럼 재귀를 통해 완전탐색을 구현해서 풀 수 있는 문제이다. 전체적인 흐름은 N과 M 문제에서 사용한 풀이와 같다. 연산자들을 갱신하는 배열인 order배열을 사용해 지금까지 등장한 연산자들을 갱신하고, 연산자에 대한 탐색이 끝났으면 탐색된 연산자와 숫자 배열에 대해 조건에 맞게 계산해 준 다음 최댓값과 최솟값을 비교해서 답을 갱신한다. 이 과정에서 답을 계산해서 갱신하는 부분은 따로 함수로 빼서 처리했는데, 연산자를 갱신하는 과정에서 답까지 함께 계산하게 되면 답을 갱신하는 함수를 돌릴 필요가 없어 좀 더 빠르게 처리할 수 있다. Java import java.io.*; import java.util.*; public class Main { static int N, max, min..
완전 탐색
완전 탐색
2022.03.05문제 해결을 위해 모든 경우의 수를 탐색하는 방법이다. 가장 간단한 방법으로는 for문을 중첩해서 사용하는 방법이 있지만, 좀 더 효율적으로 탐색을 진행하기 위해 문제 조건을 잘 읽고 백트래킹 혹은 재귀를 사용할 수 있는 경우라면 사용해서 푸는 편이 합리적이다. 완전 탐색을 사용해서 문제를 해결할 때는 주어진 문제를 잘 읽고 함수를 어떻게 정의할 지 생각하는게 매우 중요하다. 재귀를 이용해서 완전 탐색을 구현하면 코드의 길이가 짧아지고 직관적으로 코드를 작성할 수 있지만, 재귀에 익숙하지 않으면 생각해내기가 쉽지 않다. 많이 경험해 봐서 익숙해지자. 완전탐색을 진행할 때 값들에 대해서 중복 허용 여부와 순서의 유무를 확인하자. 조건들에 따라 다른 시간복잡도가 나올 수 있다.
[백준] 15649 N과 M (1) - Java
[백준] 15649 N과 M (1) - Java
2022.03.05https://13months.tistory.com/172 [백준] 15651 N과 M (3) - Java 완전탐색 문제이다. for문을 적당히 사용하면 쉽게 해결할 수 있지만, 답을 구하는 함수와 메인 함수를 구분해서 코드를 작성하고, 답을 구할 때 재귀를 사용해 좀 더 효율적으로 풀어보자. Java im 13months.tistory.com N과 M (3) 문제에서 중복을 허용하지 않는 조건이 추가된 문제다. boolean타입 변수를 선언해 중복된 수인지 확인해주는 방향으로 쉽게 해결할 수 있다. Java import java.io.*; import java.util.*; public class Main { static int N; static int M; static StringBuilder sb ..
[백준] 15651 N과 M (3) - Java
[백준] 15651 N과 M (3) - Java
2022.03.05완전탐색 문제이다. for문을 적당히 사용하면 쉽게 해결할 수 있지만, 답을 구하는 함수와 메인 함수를 구분해서 코드를 작성하고, 답을 구할 때 재귀를 사용해 좀 더 효율적으로 풀어보자. Java import java.io.*; import java.util.*; public class Main { static int N; static int M; static StringBuilder sb = new StringBuilder(); static int[] selected; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in));..
[백준] 3987 보이저 1호 - Java
[백준] 3987 보이저 1호 - Java
2022.03.04이차원 배열을 활용해서 풀 수 있는 구현 문제이다. 언제 break를 걸어주고 언제 방향을 바꾸는지 잘 파악하고 풀도록 하자. 풀이 로직은 다음과 같다. 1. C를 만나거나 경로에서 이탈하게 되면 break 2. .을 만나면 continue 3. 행성을 만나게 되면 현재 방향에 따라서 방향을 틀어준다. 마지막으로 무한으로 순환하게 되는 경우가 있는데, 이런 경우는 충분히 큰 수를 cnt변수와 비교해 무한으로 순환한다고 판단할 수 있다. dir배열을 사용해 현재 진행하고 있는 방향을 표시했고, 방향을 전환할 때도 배열을 사용했다. Java import java.io.*; import java.util.*; public class Main { static char[][] map; static int N; s..
[백준] 1706 크로스워드 - Java
[백준] 1706 크로스워드 - Java
2022.03.02지난번에 풀었던 경사로 문제와 비슷한 문제이다. 이차원 배열을 사용해 크로스워드 퍼즐을 구현하고, 조건에 맞춰 가로 단어와 세로 단어를 구해낸 다음 정렬을 진행한다. 풀이 로직은 다음과 같다. 1. 배열을 하나씩 반복하면서 현재 탐색하는 원소가 #가 아닌 경우 seq변수를 1 추가한다. (단어가 몇 번 연속되는지 확인) 2. #를 만나거나 행의 끝에 도달했을 때 seq변수가 2이상이면 (두 번 이상 연속됐으면) 정답을 갱신한다. 3. row방향으로, column방향으로 한 번씩 갱신한다. Java import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ ..
[백준] 17299 오등큰수 -Java
[백준] 17299 오등큰수 -Java
2022.03.02지난번에 풀었던 오큰수와 같은 로직으로 풀 수 있는 문제이다. 배열의 인덱스와 값을 가지는 스택 두 개를 선언하고 조건에 맞게 push와 pop을 진행해서 풀 수 있다. 오큰수 문제에서는 현재 탐색하는 원소보다 더 큰 수를 만나면 정답을 갱신했었는데, 이 문제에서는 원소들이 나온 횟수를 센 다음 현재 탐색하는 원소가 나온 횟수보다 더 많이 나온 횟수를 만났을 때 정답을 갱신해야 한다. Java import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReade..