화분

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

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

Codetree ID : otu123

어느덧 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..

이번 구현 문제는 수가 오름차순이었다가 내림차순으로 바뀌는데 다시 오름차순으로 변하는 지 알아내는 문제이다. 이 문제를 flag 변수를 활용해서 풀었다. 배운점 StringTokenizer의 사용법에 대해 다시금 익혔다. 느낀점 flag 변수에 너무 의존하거나 잦은 사용은 깔끔하지 못한 코드를 만들기 때문에 가급적 지양하려 했는데 한두개 정돈 괜찮지 않을까 해서 사용했다. 어려웠던 점 이전 문제들보단 어려웠지만 그럼에도 쉬운 편에 속하는 문제였다..

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

이번 문제는 최장 공통 부분수열(LCS:Longest Common Subsequence)이다. 어떻게 동적계획법을 이용해 풀지 고민하다가 테이블에 어떻게 기록할진 떠올렸으나 코드로 구현할 방법은 떠오르지 않아 결국 인터넷을 참고하였다. 이 문제에 어떻게 접근했냐하면 우선 큰 문제를 해결하기 위한 공통된 작은 문제를 찾아내려 했다. 앞에서부터 공통된 문자를 찾기보단 뒤에서부터 찾으려 했다. 그 결과 다음과 같은 테이블을 완성했다. A C A Y K P C 3 A 4 2 P 1 C 3 A 2 2 K 1 가장 우측 하단 위치에서부터 왼쪽 행과 윗쪽 열의 안쪽에 있는 수를 증가시켜 나간다. 이렇게 접근하면 LCS를 만족하는 문자의 개수를 알아내는 실마리를 찾은거 같았다. 하지만 문제가 있었다. 어떻게 저 가장 ..