자바116 프로그래머스] 타겟넘버 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 +, - 로 이루어진 그래프가 있다고 생각한다. 해당 그래프를 순회하면서 주어진 숫자배열에 값들을 더하거나 빼면서 target 넘버가 나오는지 확인한다. import java.util.*; class Solution { static int count=0; //결과를 저장할 변수 static char[] d = {'+','-'}; //반복문을 쓸거면 사용할 배열 static public int.. 자바/알고리즘 문제 풀이 2023. 4. 27. ★프로그래머스3/베스트앨범/Map,Comparator,class 하나의 Map을 이용해서 풀려고하니 복잡해진 문제 2개의 Map으로 나눠도 좀 복잡하긴하다. Map을 정렬하려면 EntrySet를 이용해서 정렬하던지 Map안에 정렬가능한 List같은 collection객체를 넣던지 해야한다. Map을 EntrySet로 정렬하고 정렬된 EntrySet의 Key(장르)를 이용하여 인덱스를 가져오는 풀이 import java.util.*; import java.util.Map.*; class Solution { public int[] solution(String[] genres, int[] plays) { Map map = new HashMap(); // Map map2 = new HashMap(); // > for(int i=0;i { return map2.get(o2.g.. 자바/알고리즘 문제 풀이 2023. 3. 28. 프로그래머스2/위장 / Hash https://school.programmers.co.kr/learn/courses/30/lessons/42578 values는 collection으로 , keySet은 set으로 반환되지만 그냥 바로 받아서 사용가능 + 조합의 경우의 수를 잘생각해야한다. import java.util.*; import java.util.Map.*; class Solution { public int solution(String[][] clothes) { int answer = 1; Map map = new HashMap(); for(String[] cloth : clothes) { String category = cloth[1]; map.put(category,map.getOrDefault(category,0)+1); .. 자바/알고리즘 문제 풀이 2023. 3. 28. 프로그래머스] 완주하지 못한 선수 /Hash https://school.programmers.co.kr/learn/courses/30/lessons/42576 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 배열 정렬로 풀이 참가자,완주자 명단을 정렬 참가자명단을 반복문을 돌면서 같은 인덱스에 완주자 명단을 보고 이름이 같은지 체크 아니면 완주 못한사람 public String solution(String[] participant, String[] completion) { String answer = ""; if(participant.length == 1) { return participant[.. 자바/알고리즘 문제 풀이 2023. 3. 28. [Java] 플로이드 워셜 (Floyd-Warshall) 알고리즘 [미완] 플로이드 워셜 1. 음수가중치가 있어도 된다. 하지만 음수 사이클이 존재하면 안된다. 2. 다익스트라 알고리즘은 "어떤하나의 정점"에서 부터 다른 모든 정점까지의 최소비용을 구하는 알고리즘이지만 플로이드 워셜은 "다른모든정점"에서 부터 "다른 모든정점"까지의 최소비용을 구할 수 있다. 3. 인접 행렬을 사용한다. (모든 정점에서 부터 다른 모든정점까지의 최소비용을 저장한다) 4. 시간복잡도는 O(v^3)이다. v는 정점 "다른모든정점"에서 부터 "다른 모든정점"까지의 최소비용 정보가 필요할때 사용하자. 플로이드 워셜 코드 + 예제 (백준 11404) public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader.. 자바/알고리즘 2023. 1. 10. 백준/11404 플로이드 / (최단경로찾기) 플로이드 와샬,다익스트라 플로이드 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 48443 20032 14176 41.698% 문제 n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타.. 자바/알고리즘 문제 풀이 2023. 1. 10. [Java] 벨만-포드 알고리즘 (Bellman-Ford) [미완] 그래프 최단거리를 구하는 알고리즘 1. 다익스트라 2. 벨만 포드 3. 플로이드 와샬 벨만 포드 알고리즘은 다익스트라 알고리즘처럼 그래프에서 한 노드에서 다른 모든 노드까지 가는 최소비용을 구할 수 있는 알고리즘이다. 다익스트라와의 차이점은 음수 가중치가 존재하는 경우에도 적용 할 수 있다. 벨만 포드 알고리즘의 시간복잡도는 O(VE)이다. (V: 정점, E: 간선) 다익스트라에서 시간복잡도는 O(VlogE)이므로 다익스트라가 더 빠르다. 다익스트라 알고리즘의 한계 다익스트라 알고리즘은 그리디알고리즘 + 다이나믹 프로그래밍이 합쳐진 알고리즘이다. 그리디 알고리즘 한계점 때문에 다익트스라 알고리즘은 음수 가중치를 가질 수 없다. 위 그림에서 1번 -> 3번 이동할때 최소비용을 구하게하면 다익스트라는 1->.. 자바/알고리즘 2023. 1. 8. ★★★ 백준/13549 숨바꼭질3 / bfs, 다익스트라 알고리즘 숨바꼭질 3 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 512 MB 59673 17254 11099 25.327% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다... 자바/알고리즘 문제 풀이 2023. 1. 3. 백준/1504 특정한 최단 경로/ 다익스트라 알고리즘 특정한 최단 경로 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 59864 15172 10258 24.557% 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어.. 자바/알고리즘 문제 풀이 2023. 1. 3. [Java] 다익스트라 알고리즘(Dijkstra Algorithm) + 예제 다익스트라 알고리즘 V = vertext(정점) , E = edge(간선) , adjNode = adjacentNode(인접노드) - 최단경로를 구하는 알고리즘 - 하나의 정점을 기준으로 다른 정점까지 가는 최단거리를 구한다. (출발지에서 다른 정점까지의 최단거리들을 구한다) - 음수 가중치가 없어야한다 - 인접 행렬로 표현된 그래프로 다익스트라 알고리즘을 구현시 시간 복잡도 O(V^2) - 우선순위 큐+리스트를 사용해서 다익스트라 알고리즘 구현시 시간복잡도 ( ElogV) 까지 낮출수 있다고 한다. - 탐욕법(그리디 알고리즘) 과 동적 계획법(다이나믹 프로그래밍)을 사용한다. -> 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다 (그리디 알고리즘) -> 해당 노드로부터 갈 수 있는 노드들의.. 자바/알고리즘 2023. 1. 3. ★백준/7562 나이트의 이동 /bfs 나이트의 이동 성공다국어 한국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 44259 22440 16709 49.655% 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, .. 자바/알고리즘 문제 풀이 2022. 12. 27. [Java] 두 배열 비교하기 배열을 비교할때는 Arrays.equals() 메소드를 사용한다. static void solve() throws IOException { int[] a = {1, 2, 3,}; int[] b = {1, 2, 3,}; if (a == b) { bw.write("동일한 배열입니다."); } else { bw.write("동일하지않습니다."); } } ==로 비교하게되면 원하는 결과가 나오지않는다. ==연산자는 각 배열의 주소값을 비교하기 때문이다. Arrays.equals()를 사용하면 원하는 결과가 나온다. static void solve() throws IOException { int[] a = {1, 2, 3,}; int[] b = {1, 2, 3,}; if (Arrays.equals(a,b)) { .. 자바/++ 2022. 12. 27. 이전 1 2 3 4 5 ··· 10 다음