화분

문제 링크는 다음과 같다 : https://www.codetree.ai/missions/5/problems/odd-even-bundle?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 이번 문제는 구현 문제이고 처음엔 동적 프로그래밍을 이용해서 푸는게 어떨까 생각했지만 동적 테이블을 만들기가 까다롭고 불가능할거 같아서 다른 접근 방식을 생각해봤다. 이 문제를 풀기 위해 주어진 각 숫자들의 높고 낮음은 무의미하다. 짝수인지 홀수인지가 중요하다. 간단하게 각 숫자들을 2로 나눈 나머지인 ..

문제 설명 링크 : https://www.codetree.ai/missions/2/problems/gold-mining?&utm_source=clipboard&utm_medium=text 이번 문제는 완전탐색의 문제이다. 이 문제를 살펴보고 나서 처음 떠오른 건 코드를 시작한 지 얼마 안됐을때 접한 다이아몬드 그리기 문제였다. 당시엔 정말 어려웠는데... 지금도 이 문제가 물론 어려웠지만 수식을 짜고 코드로 구현한 결과 문제를 풀 수 있었다. k의 최대 크기는 한 변의 길이보다 1 작다고 가정하고 풀었다. import java.util.*; import java.io.*; public class Main { static int[][] arr2d; public static void main(String[]..

코드트리 챌린지 첫주차 마지막 날이다. 챌린지를 진행하기 위해 매주 진단 결과를 올려야 한다. 나의 진단 결과는 이렇다. 오늘 내가 푼 문제는 완전탐색 문제 중 하나인 트로미노 란 문제이다. 문제의 링크는 다음과 같다. https://www.codetree.ai/missions/2/problems/tromino?&utm_source=clipboard&utm_medium=text 이 문제를 풀기 위해 떠올린 방법은 2중 for문으로 이차원 영역을 모두 순회하면서 블럭들을 대입해보며 비교하는 것이다. 그럴 경우 가능한 모든 형태의 블럭 6가지와 블럭을 구성하는 영역의 3개의 좌표를 알아내기 위해 N^2의 시간복잡도를 가진다고 생각했다. 그리고 블럭의 좌표와 현재 순회를 하고 있는 (i, j)좌표의 대입 결과..

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

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

완전탐색 문제이다. 이 문제를 어떻게 접근해야 할지 고민한 부분은 어떻게 시간복잡도를 최소한으로 줄일지였다. 결국 첫번째엔 행을 기준으로, 두번째엔 열을 기준으로 2중 for문을 2번 돌려서 풀기로 결정했다. 시간복잡도는 O(n^2)이다. 풀면서 고심한 부분은 변수 before와 current를 어떻게 설정할지였다. 처음 시도에서 통과하지 못했는데 행렬 크기가 1 x 1이고 M이 1인 경우에서 통과하지 못했다. 왜냐하면 처음엔 2중 for문의 조건식에 i와 j를 0이 아닌 1부터 시작하도록 했기 때문이다. 이 부분은 before와 current변수를 어떻게 설정할지와도 관련이 있다. 위의 코드는 그 부분까지 고려해서 코드를 짠 결과다. 전체 코드는 다음과 같다. import java.util.*; imp..

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

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