본문 바로가기

알고리즘146

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.
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.
[Java] 알고리즘 투포인터, 그리디, 분할정복 [Java] 알고리즘 투포인터, 그리디, 분할정복 투포인터 투포인터는 주로 배열에서 두 개의 포인트를 만들어서 포인트에 대한 정보를 가지고 데이터를 찾아내는 것이다 투포인터는 양 옆에서 안쪽으로 들어오는 형태로 순회가 가능하다 또한 같은 지점에서 탐색을 할 수 있도록 할 수 있다 기본적으로 문제에 따라 적절하게 사용을 하면 될 것 같다 // ======= 양쪽에서 안 쪽으로 들어오는 방식 ========= // 2개의 숫자를 가지고, target을 만드는 것 private static boolean isPairSum(int[] array, int target) { int left = 0; int right = array.length - 1; while (left < right) { if (array[le.. 2023. 7. 5.
[Java] 알고리즘 이진 탐색 [Java] 알고리즘 이진 탐색 이진 탐색은 정렬된 데이터에서 특정 데이터를 빠르게 찾는 방법이다 데이터를 정렬을 한다 정렬 후, 중간 인덱스를 찾고, 해당 값이, 구하려는 값과 같은 값인지 본다 찾으려는 값이 더 작다면, 중간 인덱스 기준 왼쪽으로 / 크다면 중간 인덱스 기준으로 오른쪽으로 탐색을 한다 위와 같이 왼쪽 또는 오른쪽 기준에서 중간 지점을 찾고, 중간에 있는 숫자보다 작은지 큰지, 또는 같은지 탐색을 한다 그리고 숫자 하나가 남을때까지 탐색을 한다 (마지막 숫자 하나가 답이 아니면, 찾으려는 숫자가 없는 것이다) // ========== loop문으로 구현 ================= public static int binarySearch(int[] array, int target) {.. 2023. 7. 4.
20230704 [Java] 문제풀이 20230704 [Java] 문제풀이 [프로그래머스] 숫자 짝꿍 두 개의 숫자가 문자열로 주어진다 두 숫자가 공통으로 가진 숫자들을 모아서 제일 큰 수를 만드는 것이다 110, 11110 이면 110이 있어 110이 가장 큰 숫자다 1234, 123456 에서는 1234가 있고 4321이 가장 큰 숫자다 0~9까지, 각각 숫자들의 개수를 넣으려는 배열을 2개 만들었다 하나는 X 수에 대한 배열 하나는 Y 수에 대한 배열 두 배열을 제일 뒷부분에서 순회하면서, 0이 아닐 경우 겹치니깐 두 배열 중 작은 숫자만큼 문자열에 넣어주면 된다 StringBuffer를 사용할 때에는 .toString() 을 이용하면 문자열로 바꿔준다 import java.util.*; class Solution { public St.. 2023. 7. 4.
20230703 [Java] 문제풀이 20230703 [Java] 문제풀이 [Baekjoon 1254] 팰린드롬 만들기 주어진 단어의 인덱스를 순회를 한다 해당 인덱스부터, 단어 끝까지, 팰린드롬이 성사하는지 확인을 한다 aaabab가 주어진다 string.substring(0) - aaabab (팰린드롬이 아님) string.substring(1) - aabab (팰린드롬이 아님) string.substring(2) - abab (팰린드롬이 아님) string.substring(3) - bab (팰린드롬이다) 그렇게 팰린드롬이 주어지면, answer = string.substring(palindromIdx).length() + (palindromIdx * 2); 을 한다 팰린드롬 단어의 길이 + 팰린드롬을 찾기 전 단어의 개수와 팰린드롬을.. 2023. 7. 3.

티스토리툴바