화분

문제를 요약하자면 i번째엔 그래프의 i번 노드를 통과하지 못하고 목적지까지 도달할 수 있는지, 도달할 수 있다면 최소 몇개의 노드를 통과해서 갈수 있는지 알아내는 것이다. 이번 문제는 연결 리스트로 그래프를 구현하여 해결하였다. 배운 점 목적지에 최단 횟수로 도달하는 방법을 알아내려면 dfs보단 bfs가 더 나은거 같단 생각이 들었다. dfs는 어떤 한 길을 택하고 그 길이 목적지에 도달할 수 있는지 없는지 알아낸다면 bfs는 모든 길에 동등한 차수를 우선적으로 방문하기 때문이다. 물론 이럼에도 중복해서 노드를 방문할 가능성이 있기 때문에 이런 점을 counting이란 배열을 선언해서 각 노드에 해당하는 counting 배열의 위치에 최단거리를 저장하는 식으로 풀었다. 느낀 점 여전히 코드를 테스트할 때..

드디어... 구름톤 챌린지의 끝에 도달했다. 하지만 마지막 문제를 기간 내에 못 풀어서 아쉽게도 20개를 다 모으진 못했다..ㅠㅠ 좀만 더 부지런할껄. 그래도 여기까지 꾸준히 풀어온 나 자신에게 칭찬해주고 싶다. 이번 문제 풀이의 접근 방식은 옳았다고 생각하나, 논리적 절차에 있어 오류의 여지가 있어서 모든 케이스를 통과하지 못했다. 그래서 문제가 시작되고 24시간이 지나고 올라온 정해코드를 하나씩 따라 적고 구동해보고 어디서 틀렸는지 확인해보면서 풀었다. 이번 문제를 통해 배운점이나 느낀 점, 어려웠던 점은 다음과 같다. 배운 점 조건식에 논리 연산자를 사용할 때 잊지 말아야 할 점이 있다. 쇼트 서킷(short circuit)으로 인한 문제가 발생하지 않도록 작성해야 한다는 점이다. 나같은 경우 or..

이번 문제는 그리디 문제이다. 처음엔 동적 프로그래밍 문제라고 생각해서 어떻게 테이블을 만들지 생각했었는데 굳이 동적 프로그래밍을 위한 테이블을 따로 생성하지 않더라도 그리디 접근 방식으로 풀 수 있다는걸 알게 되었다.문제 해결 방법은 간단하다. 일단 주어진 조건인 쓸 수 있는 금액이고 그 금액 한도 내에서 가격 대비 포만감이 높은 과일을 먼저 사 나가는 방식으로 풀면 된다. 만약 쓸 수 있는 금액보다 과일의 가격이 높다면 과일 가격의 최소단위로 포만감을 나눠서 조각 단위로 구매하면 된다. 배운 점 10의 9제곱 이상인 수를 다룰때 int형이 아닌 long 타입을 활용해야 한다는 걸 알게 되었다. 그리디 문제를 해결하기 위한 접근 방식도 알게 되었다. Collections.sort()로 내림차순으로 정렬..

이번 문제는 dfs를 활용하여 문제를 풀었다. dfs를 구현하기 위해 stack을 활용할 수도 있고 재귀함수를 활용할 수도 있는데 이번 풀이는 스택을 활용해서 풀었다. 배운 점 그래프 탐색 알고리즘을 마지막으로 접한지 오래됐는데 이번 문제를 풀면서 다시금 상기하고 공부할 수 있어서 좋았다. 하나의 조건식에 2~3개 이상의 논리 연산자를 사용하는 것이 잘못되었다는걸 깨달았다. short-circuit evaluation에 대해서 다시금 상기할 수 있는 기회였고 앞으론 조건식의 논리연산자를 최대한 적게 쓰는 방향으로 풀어야 한다고 느꼈다. 어려웠던 점 자바로 알고리즘 문제를 풀이한 지 좀 됐는데 그럼에도 여전히 문법 오류를 여러번 겪게 되는거 같다. 한번에 통과하지 못하고 문법 오류를 수정해나가면서 완성해나..

어느덧 10일차이다. 이번 문제에 대한 설명은 다음 링크 ( GameJam - 구름LEVEL (goorm.io) ) 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 를 참조해주기 바란다. 문제를 풀기 위한 코드는 다음과 같다. 코드가 꽤 길다. import java.io.*; class Main { static int[] dy = {-1, 0, 1, 0}; static int[] dx = {0, 1, 0, -1}; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in..

소개 이번 문제는 N * N 크기의 2차원 배열에 K개의 폭탄이 떨어지면 상하좌우 그리고 가운데에 점수가 올라간다. 특이점은 @인 자리는 2점씩 올라가고 #인 자리는 점수가 안 오른다. 빅오표기법을 사용하면 O(K)여서 시간초과를 걱정해야 하는 문제는 아닌거 같다. 코드는 다음과 같다. import java.io.*; class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] NK = br.readLine().split(" "); int N = Integer.parseInt(NK[0]); i..

이번 문제는 지금까지 풀어왔던 구름톤 챌린지 문제 중에서 가장 난이도가 높았다고 느꼈다. 문제를 요약하자면 N개의 숫자들을 입력 받고 그 숫자들을 2진수로 변환 했을때 1이 가장 많은 수부터 내림차순으로 정렬하고, 1의 개수가 같은 숫자가 있을 경우 10진수 값으로 내림차순 하는 문제이다. 이 문제를 풀기 위해 우선 2진수로 변환했을때 1의 갯수 별로 10진수 숫자들을 저장한다. 이때 사용한 자료구조는 TreeMap이다. key값은(1의 개수는) 1부터 20까지 있고 각 key에 해당하는 10진수들을 value인 ArrayList에 담는다. 그 다음으로 TreeMap을 역순으로 정렬한다.(1->을 20->1로) 그리고 TreeMap에서 key마다 저장되어 있는 ArrayList를 내림차순으로 정렬한 후,..