분류 전체보기242 [알고리즘] 정렬 알고리즘 정리 - JAVA 개요어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제이다. 데이터를 정렬해야 하는 이유는 탐색을 위해서이다. 컴퓨터는 이론상 무한 개의 데이터를 다룰 수 있어야 한다. 탐색할 대상 데이터가 정렬되어있지 않다면 순차 탐색 이외에 다른 알고리즘을 사용할 수 없지만 데이터가 정렬되어 있다면 이진 탐색이라는 강력한 알고리즘을 사용할 수 있다. 대표적인 정렬의 종류로 버블정렬, 퀵정렬, 삽입정렬 등이 있다. 버블정렬버블정렬은 거의 모든 상황에서 최악의 성능을 보여준다. 단, 이미 정렬된 자료에서는 1번만 돌면 되기 때문에 최선의 성능을 보여준다. 시간복잡도는 O(n²). 버블정렬은 다음과 같은 순서로 작동한다.1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교2. 현재 원소가 다음 원소보다 크면.. 2024. 5. 17. [백준] 22866: 탑 보기 - JAVA https://www.acmicpc.net/problem/22866 풀이N개의 건물의 높이가 주어진다. 각 건물의 옥상에서 양 옆을 볼 때, 현재있는 건물의 높이보다 큰 건물만 볼수있고, 큰 건물로 가려지면 볼 수 없다. 스택을 이용해 저장하면서 현재 빌딩보다 낮으면 없애주는 식으로 구현했다. 왼쪽부터, 오른쪽부터 두번에 걸쳐 스택에 저장하는 과정을 거쳤다. 왼쪽부터 진행할 때는 현재 건물의 왼쪽을 본다는 것이고 오른쪽부터 진행하면 오른쪽을 본다는 것이다. 메모리: 34648KB시간: 656ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Building { int idx; i.. 2024. 5. 17. [백준] 1189: 컴백홈 - JAVA https://www.acmicpc.net/problem/1189 풀이(R-1, 0)에서 (0, C-1)로 이동한다. T는 가지 못하는 부분이고, 한번 지나친 곳은 다시 방문하지 않는다. 이동거리가 K인 경우의 수를 구하는 문제이다. 따라서 방문처리를 하며 dfs탐색을 했다. 각각의 경우에 따른 방문처리가 서로 영향을 주어서는 안되기 때문이다. 이동 거리를 1씩 늘려가면서 다음 칸으로 이동했고, 이동 거리가 K가 됐을 때, 도착점에 도달하였을 때 사이클을 종료시켰다. 메모리: 14584KB시간: 136ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[][] vector = { { 1, 0 }, { 0, 1.. 2024. 5. 17. [백준] 14658: 하늘에서 별똥별이 빗발친다 - JAVA https://www.acmicpc.net/problem/14658 풀이N, M의 범위가 500000이기 때문에 이것을 기준으로 탐색을하면 시간초과가 난다. K가 100까지인것을 보고 K를 기준으로 탐색했다. 트램펄린의 어느 모서리에 별이 위치해있어야 많은 별을 담을 수 있다. 별 두개를 선택해 별a의 x좌표와, 별b의 y좌표를 한쪽 꼭지점으로 하는 길이 L의 사각형을 만들어 거기에 별이 얼마나 들어가는지 체크했다. 메모리: 14712KB시간: 160ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int x; int y; public Node(int .. 2024. 5. 17. [백준] 2179: 비슷한 단어 - JAVA https://www.acmicpc.net/problem/2179 풀이영단어들이 주어지고 두 단어를 앞에서부터 비교하여 공통적으로 나타나는 부분의 길이가 긴 두 단어를 출력해야한다. 한글자씩 비교하기 위해 트라이 알고리즘을 생각했으나, 시간이 충분하고 메모리 제한이 작아서 트라이를 사용하지 않았다. 길이가 같을 경우 주어진 순서대로 앞쪽에 있는 단어가 답이되므로 순서 유지가 되는 ArrayList를 선택했다. ArrayList에 단어를 담고 앞에서 부터 순서대로 비교하여 접두사의 길이와 인덱스를 저장했다. 메모리: 19328KB시간: 2008ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void .. 2024. 5. 17. [백준] 7490: 0 만들기 - JAVA https://www.acmicpc.net/problem/7490 풀이1부터 N까지의 수 사이에 +, -, 공백을 넣어서 수식을 만들고 그 수식을 계산하여 0이 되는 경우 출력해야 한다. 출력할 때 ASCII 순서에 따라 출력하라는 제한이 있어서 공백, +, - 순서로 dfs탐색을 통해 수식을 만들었다. N까지 진행하면 수식을 계산하는 메서드를 통해 0이 나오면 값을 출력한다. 메모리: 17200KB시간: 168ms언어: Java 11import java.io.*;public class Main { static int N; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) throws.. 2024. 5. 17. [백준] 13144: List of Unique Numbers - JAVA https://www.acmicpc.net/problem/13144 풀이길이 N의 수열에서 연속한 1개 이상의 수을 뽑았을 때 같은 수가 여러번 등장하지 않는 경우의 수를 구해야 한다. 처음에는 첫번째 원소부터 시작하여 dfs탐색을 통해 구하려고 했었다. 방문체크는 비트마스킹을 이용할 계획이었다. 하지만 N의 범위와 숫자들의 범위가 커서 안되는 것을 깨달았다. 따라서 투포인터 알고리즘을 떠올렸다. start, end를 0에서 부터 시작하여 방문처리를 하면서 end값을 증가시킨다. 이전에 나온 숫자가 나올때까지 end값을 증가시키고 ans에 end - start를 더해준다. 현재 start값에 대한 경우의 수를 구했으므로 현재 start값의 방문처리를 지우고 start값을 1늘려 다시 판단한다. 메모리:.. 2024. 5. 17. [백준] 22251: 빌런 호석 - JAVA https://www.acmicpc.net/problem/22251 풀이디지털 숫자의 눈금들을 반전시켜서 다른 숫자를 만들 수 있다. 다른 숫자가 되려면 몇 개를 반전시켜야 하는지 이차원배열 arr에 저장해놓고 시작했다. dfs탐색을 통해 숫자 X를 일의자리부터 앞으로 가면서 바꿔줬다. 반전한 개수 누적하고 만들어진 숫자를 저장하면서 숫자가 N보다 크거나 반전 횟수가 P보다 크면 성립하지 않는 것이므로 return해주었다. K자리 수까지 갔을 때 만족하면 result에 1을 더해주었다. 숫자가 0이 되는 경우를 제외했고, 현재 숫자와 같으면 안되므로 result에 -1해주었다. 메모리: 14292KB시간: 196ms언어: Java 11import java.util.*;import java.io.*;pu.. 2024. 5. 17. [백준] 2075: 스카이라인 쉬운거 - JAVA https://www.acmicpc.net/problem/2075 풀이왼쪽부터 순서대로 좌표가 주어지므로 높이만 stack에 저장하면 된다. 스택에 높이를 저장하면서 stack.peek()보다 높이가 낮아지면 stack.peek()이 더 낮아질때까지 pop해주면서 답을 하나씩 늘린다. 그리고 새로운 높이를 스택에 저장한다. 주의할 점으로 높이가 0이면 저장을 안해도 되고, stack.peek()과 높이가 같으면 저장을 안해도 된다는 것이있다. 메모리: 19576KB시간: 212ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception {.. 2024. 5. 17. [트러블슈팅] Could not resolve org.springframework.boot:spring-boot-gradle-plugin:3.1.2" 에러 내용A problem occurred configuring root project 'projectName'.> Could not resolve all files for configuration ':classpath'. > Could not resolve org.springframework.boot:spring-boot-gradle-plugin:3.1.2. Required by: project : > org.springframework.boot:org.springframework.boot.gradle.plugin:3.1.2 해결프로젝트를 클론받아 IntelliJ에서 빌드하였는데 위와 같은 에러가 발생했다. spring boot 3.x 버전은 JDK 17 이상을 사용해야 한다고.. 2024. 5. 17. 이전 1 ··· 8 9 10 11 12 13 14 ··· 25 다음
