화분

2448번: 별 찍기 - 11 (acmicpc.net) 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 이 문제는 유명한 별찍기 문제의 심화버전 중 하나이다. 수학적인 규칙이 존재하고 그걸 발견해서 구현하면 됐지만, 나 같은 경우 클래스를 활용해서 풀고 싶어졌다. 그래서 아래와 같은 코드를 짜고 설마 돌아가진 않겠지? 생각하며 돌렸는데... import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOException{ Scanner s..

1107번: 리모컨 (acmicpc.net) 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net import java.util.Scanner; //import java.io.IOException; //import java.io.BufferedReader; //import java.io.InputStreamReader; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int..

문제 링크는 다음과 같다 : 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..