본문 바로가기

개발자145

[Java] 알고리즘 최단경로 (다익스트라) [Java] 알고리즘 최단경로 (다익스트라) 최단 경로 알고리즘 두 노드를 연결하는 가장 짧은 경로를 찾는다 (노드 사이의 간선 마다, 특정 값이 있다) 지도 탐색, 네트워크 다익스트라 출발 노드 기준에서, 다른 모든 노드의 최단 경로를 구할 수 있다 (하지만 가중치 음수 값이 없어야 한다) 다익스트라 알고리즘은, 우선순위 큐를 사용한다 그림으로 대략적인 설명 import java.util.*; public class Dijkstra { static class Node { int to; int distance; Node(int to, int distance) { this.to = to; this.distance = distance; } } public static void dijkstra(int node.. 2023. 7. 10.
20230709 [Java] 문제풀이 20230709 [Java] 문제풀이 [프로그래머스] 요격 시스템 미사일이 떨어지는 개구간이 targets라는 2차원 배열로 주어진다 이 미사일을 요격하기 위해, 필요한 요격 미사일의 개수의 최솟값을 구하는 것이다 일단 각 미사일의 개구간 중, 끝 부분을 기준으로 오름차순으로 정렬을 한다 그렇게 정렬을 하고 난 후에, 현재 공격 받는 미사일의 개구간의 시작점과, 그 전의 공격 받았던 미사일의 개구간의 마지막 지점이 완전히 겹치면, 한번에 요격을 할 수 있다 [3, 6] , [4, 7] : 두 미사일을 한번에 요격할 수 있음 [3, 6], [6, 8] : 두 미사일을 요격하려면 두 개의 요격 미사일이 필요함 [3, 6], [7, 9] : 두 미사일을 요격하려면 두 개의 요격 미사일이 필요함 // ==== .. 2023. 7. 9.
20230708 [Java] 문제풀이 20230708 [Java] 문제풀이 [프로그래머스] 체육복 체육복을 도난 당한 학생들의 배열과, 여벌이 있는 학생들의 배열이 주어진다 여벌이 있는 학생은, 도난당한 학생에게 체육복을 빌려줄 수 있다 단 도난 당한 학생은, 자신보다 1 아래 또는 1 위에 있는 학생의 체육복을 빌릴 수 있다 여벌이 있지만, 체육복을 도난 당했다면 (그 학생은 다른 학생에게 체육복을 빌려줄 수 없게 된다) 일단 새로운 배열을 만들었다 학생들의 번호를 인덱스로 넣었다 (-1을 해줌) 그리고 값은 -1 : 도난 당함 0 : 자기 자신의 체육복만 있음 1 : 여벌이 있는 학생 그리고 이 배열을 순회하면서, 도난 당한 학생의 index - 1 또는 index + 1의 값이 1이라면 1을 더해준다 더해줬다는 것은, 체육복을 빌렸다는.. 2023. 7. 8.
20230707 [Java] 문제풀이 20230707 [Java] 문제풀이 [프로그래머스] 완주하지 못한 선수 완주하지 못 한 선수를 찾는 것이다 참여는 했지만, 끝내지 못 한, 한 사람을 찾으면 된다 참여한 사람들의 이름을 marathon 이라는 HashMap에 넣고, value는 +1을 해준다 같은 이름이 있을 수 있다 completion에서, 이름이 나올때마다, value에 -1을 해준다 동명인이 없으면 모든 value는 하나 빼고 0일 것이다 동명인이 있을 수 있어 -1만 해주는 것이다 0이 아니면 그 사람이 완주를 못 한 선수다 import java.util.*; class Solution { public String solution(String[] participant, String[] completion) { HashMap ma.. 2023. 7. 7.
[Java] 알고리즘 백트래킹 [Java] 알고리즘 백트래킹 백트래킹 DFS와 백트래킹이 다른점 DFS는 가능한 모든 경우의 수를 탐색을 한다 (그래서 시간이 많이 걸린다) 백트래킹은 탐색을 하다가, 불필요한 탐색이라고 생각하면, 다른 루트를 탐색을 한다 백트래킹에서는 얼마나 가지치기를 잘 하느냐가 제일 중요하다 용어 유망 (Promising) : 목표의 값이 될 가능성이 있다는 것 가지치기 (Prunning) : 목표의 값이 될 수 있는 가능성이 없어, 해당 노드를 제외 백트래킹 (Backtracking) : 유망하지 않는 쪽으로 가지 않고 다시 돌아오는 것 void dfs(int cnt, int idx) { // 현재까지의 결과, 탐색을 진행할 인덱스 // r개를 선택한 경우 if(cnt == r) { // 결과 처리 후 현재 가.. 2023. 7. 7.
20230706 [Java] 문제풀이 20230706 [Java] 문제풀이 [프로그래머스] 신규 아이디 추천 그냥 1단계부터 7단계까지, 구현을 하라고 문제에서 나온 대로, 코드를 작성했다 특히 아스키 코드를 많이 썼고, 그리고 문자열 슬라이싱을 많이 사용했던 것이 특이점이다 다른 분의 코드 (정규 표현식 사용하기) .toLowerCase() : 이것을 사용해서 대문자를 소문자로 바꾸기 replaceAll() : 문자열에서 변경할 점들을 바꾸기 .replaceAll("[.]{2,}", "."); => '.' 이 2개 이상이면 '.' 하나로 바꾸기 .replaceAll("^[.][.]$", ""); => 앞뒤에 '.'이 있으면, 없애기 import java.util.*; class Solution { public String solution(.. 2023. 7. 6.
[Java] 알고리즘 다이나믹 프로그래밍 [Java] 알고리즘 다이나믹 프로그래밍 다이나믹 프로그래밍 큰 문제를 작은 문제로 쪼개서 앞에 저장을 하고, 해결해 나가는 것이다 피보나치 수열 예시) 1, 1, 2, 3, 5, 8, 13, 21 - 이렇게 순서대로 공식대로 계산을 하면서 문제를 해결하는 방식이 있다 (시간이 오래 걸릴 수 있다) f(1) f(2) f(3) f(4) f(5) f(6) f(7) f(8) f(9) f(10) 1 1 2 3 5 8 13 21 34 55 위와 같이 f(10) 까지 저장이 되어 있으면, f(11)을 구할 때 f(1)부터 다시 구하는 것이 아니라 f(9)와 f(10)만 찾아서 더해주면 된다 피보나치 수열을 구할 때에, 재귀를 사용할 때에는, 위와 같이 A zone과 B zone 모두 작동하게 된다 즉 B zone에.. 2023. 7. 6.
백엔드 신입 개발자에게 자료구조와 알고리즘이란 백엔드 신입 개발자에게 자료구조와 알고리즘이란 제로베이스 백엔드 스쿨 나에게 자료구조, 알고리즘란? 자료구조 그리고 알고리즘을 배우면서, 제일 스트레스를 많이 받으면서, 그만큼 성취감이 제일 컸던 것 같다. 처음 파이썬으로 알고리즘을 배우고, 문제를 풀면서 파이썬이라는 언어에 더 익숙해질 수 있었다. 그만큼 나에게 자료구조, 그리고 알고리즘은 새로운 언어에 익숙해질 수 있는 촉진제 같은 역할을 했다. 알고리즘을 풀면서, 필요한 메서드나 클래스를 찾아가면서 문제를 풀어나갔다. 이렇게 알고리즘을 풀면서 사용했던 클래스나 메서드를 프로젝트에 사용하기도 했다. 그리고 실제로 자료구조를 잘 배워둬서, 나중에 프로젝트를 할 때에 더 편안하게 진행을 했던 부분도 있다. 파이썬은 많은 라이브러리가 있어서, 알고리즘을 .. 2023. 7. 5.
20230705 [Java] 문제풀이 20230705 [Java] 문제풀이 신고 결과 받기 k번 이상 신고를 받은 사람은 게시판 이용이 정지된다 한 사람이, 특정한 사람 한 명을 계속 신고해도, 한번 신고한 것과 같다 set을 이용하여, 한 사람이 특정 한 사람을 여러 번 신고 한 것을 없앤다 각 유저가, 신고한 유저 ID 중, 정지된 ID의 개수를 구하는 것 import java.util.*; // 각 유저가, 신고한 유저 ID 중, 정지된 ID의 개수를 구하는 것 class Solution { public int[] solution(String[] id_list, String[] report, int k) { HashSet set = new HashSet(); for (String string : report) set.add(string.. 2023. 7. 5.

티스토리툴바