문제 보기https://www.acmicpc.net/problem/2458  풀이 미들러 문제가 이미 해결한 문제라 챌린저만 풀었다. 일단 그래프 탐색이 필요한 문제이다.1. 자신으로부터 진행방향으로 탐색한 노드(자신보다 키가 큰 모든 사람들)2. 자신으로부터 역방향으로 탐색한 노드(자신보다 키가 작은 모든 사람들)1, 2번을 탐색해서 모든 노드 탐색이 가능하다면 자신의 키 순서를 정확하게 알 수 있다. 그림으로 보면 아래와 같다.예시 그림에서 4번 노드를 기준으로 탐색해보자.진행방향 탐색(주황)역방향 탐색(빨강)자신을 합하면 모든 노드를 탐색할 수 있다. 다른 노드들을 기준으로 탐색하면 어떻게 되는지 보자. 꼭 하나씩 탐색하지 못 하는 코드가 생긴다.  private static void dfsBac..

문제 보기https://www.acmicpc.net/problem/2457  풀이1. 정렬 방법 flowers.sort(new Comparator() { @Override public int compare(int[] o1, int[] o2) { if(o1[2] == o2[2]) { return o2[3] - o1[3]; } return o2[2] - o1[2]; } });시작, 끝이 주어지기 때문에 정렬 기준을 무엇으로 해야 할지 감이 안 잡힐 수 있다.나는 끝나는 날짜를 기준으로 내림차순 정렬을 했다.유효기한이 긴 순으로 살펴보며 개화 시기가 이전 꽃이 진 날 보다 작거나 같은 것을 찾았다.  2. 비교 방법in..

문제 보기https://www.acmicpc.net/problem/24444  풀이 어제 문제의 BFS 버전이라 역대급 속도로 풀었다.  private static void bfs(List[] arr, int r, int[] order) { boolean[] visited = new boolean[arr.length + 1]; Queue queue = new LinkedList(); visited[r] = true; queue.add(r); while (!queue.isEmpty()) { int cur = queue.poll(); order[cur] = count++; for(int i : arr[cur]) { if (!visited[i..

문제 보기https://www.acmicpc.net/problem/1865  풀이나는 벨만 포드 알고리즘이라는 걸 처음 들어봤다.코테스터디 톡방을 보니 나만 그런 건 아닌 것 같다. 그래서 문제를 푸는 것 보다 알고리즘 이해를 하는 데 더 시간이 걸렸다. 1. 벨만포드 알고리즘벨만포드 알고리즘은 가중치가 음수일 수 있는 그래프에서 최단 거리를 찾는 알고리즘이다.그러나 이 문제에서 할 일은 최단 거리를 찾는 것이 아니다.주어진 바와 같이 출발 할 때 보다 시간이 과거로 돌아간 경우가 있는 것을 음수의 순환이라 부른다. 원래는 노드의 개수 - 1 만큼 모든 간선을 탐색하면 최단거리를 완성할 수 있으나,음수의 순환이 있을 경우 이후 탐색에서도 최단거리는 계속 작아지고 -INF로 발산한다. 두 번째 예제의 그래..

문제 보기  풀이DFS에 입문하기 위한 문제인 것 같다. 간선을 방문하며 순서를 기록하면 되는 문제이고 어려운 점은 없었다. 주의할 점은1. 오름차순으로 정렬이 되어 있어야 한다는 것2. 간선 정보를 리스트, 배열 중 무엇에 담을지 생각해 봐야 한다는 것정도가 있다. 난 오름차순 정렬을 신경 쓰기 귀찮아서 2차원 배열에 간선 정보를 저장했었는데 메모리 초과가 났다.아무래도 DFS를 재귀로 구현했는데 간선 정보도 boolean 2차원 배열에 담아서 최대 100,000* 100,000*1byte를 잡아먹게 되니... 메모리 초과가 나 버렸다. 사실 최대 간선 수가 최대 정점 수의 두 배 밖에 되지 않으니 당연히 리스트로 보관하는 게 좋긴 하다.  전체 코드import java.io.BufferedReader..

문제 보기이미지를 클릭하면 넘어갑니다.  풀이왼쪽, 오른쪽 끝에서 다가가며 동일한 글자인지를 파악하는 문제.매커니즘은 쉬우나 유사회문이라는 게 존재해 머리를 아프게 만든다. 그러나 회문을 판단하는 과정을 메서드로 빼내, 한 두 번씩 더 검증하는 과정을 거칠 뿐이라면 매우 쉽게 해결 된다. 1. 회문을 검증하는 메서드 private static boolean palindrome(String s, int left, int right) { while (left 왼쪽, 오른쪽의 문자를 비교해 회문을 판별한다.  2. 유사회문 검증 int left = 0; int right = s.length() - 1; while (left = right - 1) { bw.write(0 + "\n"); ..

문제 보기https://school.programmers.co.kr/learn/courses/30/lessons/133502  풀이솔직히 너무 야매로 푼 것 같지만 일단 공유한다.스택을 쓰면 될 것 같은데 한 쌍이 아니라 4개의 숫자가 연속돼야 하는 게 문제였다.그래서 단순 무식하게 4개를 전부 꺼내서 확인하는 방법으로 했다 ㅋㅋ  전체 코드import java.util.Stack;class Solution { public int solution(int[] ingredient) { Stack stack = new Stack(); int count = 0; for (int j : ingredient) { stack.push(j); if(stack.size() >= 4) ..

문제 보기https://school.programmers.co.kr/learn/courses/30/lessons/43238# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  풀이또 이분 탐색!반복해서 풀어서 그런가 이번엔 더더 쉬웠던 것 같다. 1. 최소 시간은 어떻게 구하나?우선 기다리는 사람이 아니라 심사관에 따라 시간이 다르다는 것을 알아야 한다.걸리는 시간은 고정적이고 시간 지체 없이 바로 다른 사람을 받을 수 있다는 소리이다. 그럼 생각을 달리 해보자. - 기다리는 사람: 6- 심사관 별 걸리는 시간: 7, 10- 총 최소 시간: 28 반대로 28분 동안 몇 명을 받을 수 있는지를 생각 해보는..