말하는 컴공감자의 텃밭

수 정렬하기 2  간단하게 sort 메서드로 정렬 1234567891011121314151617181920212223242526import java.io.*;import java.util.*; public class Main { // S5 수 정렬하기 2    public static void main(String[] args) throws IOException {        BufferedReader br = ..

오랜만에 알고리즘이라 재활치료 시작합니다.. Boj 1620  나는야 포켓몬 마스터 이다솜 포켓몬 도감이 들어온다.1번 피카츄~2번 파이리~... 이후 숫자가 주어지면 해당 번호의 포켓몬이 무엇인지포켓몬 이름이 주어진다면 도감 번호가 무엇인지 출력해야한다.빠르게 Map 구조를 떠올려주고, 중복이 없으니 hash를 생각했다 다만 key로 value 조회는 수월하지만, value로 key를 찾는건 다소 비효율적이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243import java.io.BufferedReader;import java.io.IOException;import java.io.I..

이전 문제인 벽 부수면서 이동하기  객체에 걍 boolean으로 줬다. " data-og-host="hb-in99.tistory.com" data-og-source-url="https://hb-in99.tistory.com/147" data-og-url="https://hb-in99.tistory.com/147" data-og-image="https://scrap.kakaocdn.net/dn/2onvR/hyVVFLMuQW/DmplUnDC9xqrc7bAFkNjKk/img.jpg?width=259&height=194&face=0_0_259_194,https://scrap.kakaocdn.net/dn/RYK8n/hyVVDNYE2H/J59HMz7Wp0kDI8K494iDK1/img.jpg?width=259&hei..

G3.. 이놈 조건이 독특하다. 단순히 최단 거리를 구하는 알고리즘 + 벽을 1번 뚫을 수 있다가 조건이다. 근데 저 조건 하나가 왤케 무겁지 어떻게 뚫은거 체크하지~? -> 객체에 걍 boolean으로 줬다. 그리고 하나 더 visited를 3차원으로 선언해 주었다. 이게 풀면서도 아! 이거 생각 많이해야겠다 했는데 다행히 방법이 맞았다. 벽을 부수는 순간 다른 공간으로 인식해야하기 때문인데, 지도에 지름길이 하나 생길 수도 안부수는게 더 빠를 수도 있는 경우가 생기니까. 결국 판단하는 기준은 부수는 위치로 나눠야하며 만약 부순 이후라면 다르게 경로를 탐색해주어야 한다. 이런 조건을 사용하지 않는다면 부수고 새로 열리는 길이 더 효율적인지 판단해서 넣어도 답이 나올것 같다.. 하지만 지금은 졸려서리 빨..

문제를 한참 읽은 것 같다. 친구의친구의친구의..친구의..ㅊ.ㄱ..ㅇ... 정리하자면 친구인 사이가 많을수록 점수가 낮다. 친구 -> 1점 친구의 친구 -> 2점 친구의 친구의 친구 -> 3점 ... 점수가 낮을수록 친구가 많다는 뜻 이므로 회장점수가 가장 높다고 판단한다. 예제를 간단히 그래프로 나타냈을때 이처럼 된다. 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다. 그렇다면 깊이자나. 깊이. 탐색하면 끝이네. 다만 회장후보의 점수와 후보 수를 출력해야하고, 후보자들을 출력해야 하므로 정렬도 필요하다. 가보자고 코드 흐름 먼저 각 사람의 회장 점수를 계산합니다. 이 과정에서 가장 높은 회장점수를 찾아 메모리를 아낍니다. 정리한 회장 점수를 통해서 ..

문제를 잘 읽어도 보물이 없다. 땅과 바다 뿐이다. 눈이 침침한가. 보물은 육지에서 서로 빠르게 가도 가장~~ 먼 위치에 묻혀있다고 한다. 결국 L의 범위를 탐색해서 그 안에서 가장 먼 거리를 찾으면 된다. 최단거리는? BFS 손흥민 봉준호 제이팍 레스고 BFS는 탐색안된 영역을 찾아 시작점을 잡아주고 B와 W를 구분한 뒤 BFS 내부에서 Maxdist= Math.max(Maxdist,dist); 를 통해 최대 거리를 찾아주면 된다. HTML 삽입 미리보기할 수 없는 소스 큐에 배열을 넣어도~ 클래스를 짜서 넣어도~ 뭐든 상관은 없다.

오늘은 가볍게 풀자면서 골랐던 문제다.. 난이도가 뭐라고 기세등등하게 키보드를 두둘겼다가 한참 혼났다. 쉬운것도 제대로하자 실수하지말자.. 쫌 서브태스크로 문제 배점을 공개한 문제인데... 아직 정렬개념이 확실하게 안잡힌게 분명하다... 보단 사사로운 문제에 시간을 썼다. 순위 이놈 때문에 1시간반을 넘게 썼다. 정리해보자.. 문제 조건이 주루루 있다. 금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 많은 나라 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 음~ 이해하기 쉽다. 금메달이 가치가 높아(1등만 기억하는 세상) 금메달이 많다면 국가 등수가 올라간다. 단. 동일하다면 1번 국가 2위 -> 3,4번 국가 4위 -> 3번 국가 가 된다. 금메달 은메달 동메달 순으로 Co..

먼저 문제를 잘 읽어보자. 트리의 그래프에 가중치가 있는채로 들어가 있고, 양쪽으로 쫙 당길때 -> 서로 끝과 끝일때 란 얘기. 결국 트리의 리프노드를 찾아서 거리계산하면 되는구나! 라는 접근법에 도달했다. ㅋㅋ 아 시작은 거창하죠 HTML 삽입 미리보기할 수 없는 소스 먼저 코드를 보게되면 bfs 식으로 que를 활용해서 자식 노드가 없다면 리프노드이다! 라는 함수를 짜주었다. 이후 리프노드들을 leaf 리스트에 모아서 dfs를 굴려줬는데,,, 노드가 10,000개 까지라 메모리가 석나가버렸다... (돌아와 줘) 이차원 배열을 사용했기에 뭐 1억.. 써버렸으니 머 어떻게 가지치기를 할까 하다가 인접 리스트로 다시 구현하고, 로직을 수정하고자 했다. 어짜피 우린 가중치가 큰 경로를 찾아야 하므로 루트에서..

뭐 간단하다 트리형식으로 연결되어 있고, 연결된 거리가 주어진다. 이후 N과 M의 거리는 몇이야? 묻는 문제이다. 가볍게 BFS로 풀어줬다. HTML 삽입 미리보기할 수 없는 소스 Node 클래스를 짜서 넣어도 되고, 큐에 배열보단 그냥 따로 dist 변수를 만들어서 해결해도 된다.

입력들이 주루루 주어지고 1이 루트로 기준이 된다. 입력예제 처럼 주어지게 되면. 그림과 같이 입력이 들어온다. 1이 root 가 된다면 이처럼 표기할 수 있겠다. 따라서 각 자리의 부모를 나타내면 2 : 4 3 : 6 4 : 1 5 : 3 6 : 1 7 : 4 이다. Level 별로 나타내는게 문제의 핵심이기때문에 Map에 레벨과 리스트를 넣어 tree를 구성해주었다. static Map tree = new HashMap(); 이후 선언된 tree에 입력을 처리할때 computeIfAbsent를 활용해서 기존 값이 있다면 추가, 없었다면 새로 리스트를 넣어주었다. tree.computeIfAbsent(a, k -> new ArrayList()).add(b); dfs 재귀를 통해서 모든 트리를 찾아 주었..