<<개발일지>>

오늘은 조합 문제로서 DFS를 활용해서 알고리즘을 만들어 풀어보았다. 해당 문제는 문제의 말이 헷갈리 수도 있고 논란의 소지도 있을 것 같다는 생각이 든다. 하지만, 알고리즘에 초점을 두고 배웠다는 생각으로 풀어보았다.  > import java.util.ArrayList;import java.util.Scanner;class Point { int x; int y; Point(int x, int y) { this.x = x; this.y = y; }}class Main { static int answer = Integer.MAX_VALUE; static ArrayList house, pizza; static int n, m, len; s..

> import java.util.*;class Lecture implements Comparable { public int money; public int time; Lecture(int money, int time) { this.money = money; this.time = time; } @Override public int compareTo(Lecture ob) { //내림차순 return ob.time -this.time; }}class Main { static int n, max = Integer.MIN_VALUE; public int solution(ArrayList arr) { i..

오늘은 LIS(최대부분 증가수열 알고리즘)을 활용한 알고리즘 문제를 풀어보았다. 우선적으로 특정 한 부분을 정렬을 하고 시작하면 원활하게 풀 수 있는 문제였다. 하지만 이 문제를 제대로 풀기 위해서는 객체를 정렬하는 방법에 대해 알아야 하고, 아래에 사용하고 있는 dy의 개념을 잘 파악해야 한다. >import java.util.ArrayList;import java.util.Collections;import java.util.Scanner;class Brick implements Comparable { public int s, h, w; Brick(int s, int h, int w) { this.s = s; this.h = h; this.w = w; ..

>import java.util.Scanner;class Main { static int answer = 0, n; static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}; static int[] dy = {0, 1, 1, 1, 0, -1 ,-1, -1}; public void DFS(int x, int y, int[][] board) { for (int i = 0; i = 0 && nx =0 && ny  이 문제는 DFS 문제 중에서도 쉬운 문제에 속한다. 이 문제의 핵심은 DFS이다. 외부에 참조해서 들어오는 예를 들어 board 같은 경우는 실제 board 값도 변경이 된다. (참조하는 거는 그대로이다. 변수만 여러개 생기는 것이다.) ..

> 우선 이 문제는 LIS(최장 증가 부분 수열) 이라는 알고리즘을 가진 문제이다. dynamic programming(동적계획법) 중 하나로 처음 푼다면 생각하기가 조금 어려운 듯 하다 ㅋㅋ ㅎㅎ 내가 그럼 .. 이 문제의 접근 방식은 아래 사진과 같다. 처음 값을 arr에 넣고 같은 크기의 배열 dy도 추가해준다. dy를 추가해주는 이유는 비교를 통해 최장 길이를 구하기 위함이다.  for문으로 arr처음 돌면서 그 밑으로 작은 값이 있다면 +1을 해주고 dy에 넣는 형식이다. 이러한 논리를 가지고 접근하면 수월하게 풀 수가 있다!!  import java.util.*;class Main { static int[] dy; private int solution(int[] arr) { ..

> 이 문제는 BFS 문제인데 너무 오랜만에 하다 보니 어려웠다 ㅋㅋ 하지만 해오던 것들이 있어서 차근차근 접근했을 때 이해하는데 어려움은 없었다. BFS 문제를 풀 때에는 Queue를 사용해서 해야 한다. 우선 두개 똑같은 배열 board와 dis를 만들어 준다. 하나는 1만을 넣어주는 것이고 다른 하나는 +1이 계속 되어 총 날짜를 표현한다. 이렇게 셋팅을 해주고 처음에 1이 들어간 좌표를 Queue에 넣어준다. 그다음 시작을 하면 while 구문에서 인접한 토마토까지 변화를 다 주게 되었을 때까지 작동하게 되는데 중간에 1로 변한 것이 있다면 Q에 다시 넣어주고 또 다른 하나는 원래 값에서 +1을 해주고 넣어준다. 그렇게 마지막까지 while 이 돌고 나서 최종 확인으로 여전히 0이 있다면 -1을 ..

-1차 나의 풀이- 흠 ~~ 일단은 greedy 문제이지만 그냥 단순하게 풀리는 느낌이 있어서 일반적인 구현을 했고, 실제로도 답은 맞았다!! 근데 전체 풀이는 오답으로 나왔다 ?? 근데 조금만 생각해보니까 바로 틀린 이유가 보인다 ㅋㅋㅋ 일단 나는 이 특정 구간 하나만을 비교해서 count++; 를 해줬다. 이렇게 되면 특정 구간에서는 겹치는 사람이 n명이 있더라고 해도 n명끼리는 또 안 겹칠 수 있기 때문이다. import java.util.ArrayList; import java.util.Scanner; class Data { int start; int end; public Data(int start, int end) { this.start = start; this.end = end; } } cla..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 하 ㅋㅋ 일단 내 논리적인 생각은 틀린 것이 없었다. 다만 ,, ㅋㅋㅋ 휴ㅠ 문제를 잘 못 읽었다 ㅋㅋㅋ ㅠ 내가 생각한 문제는 주어진 모든 값들에서 추출해 체스판을 만들 수 있냐?? 라고 생각했지만, 다시 읽어 본 결과, 저기서 8 x 8 잘라서 색을 칠하는 최소 횟수를 구하는 것이었다. 아예 접근이 잘못된 것이다. import java.io.BufferedReader; import ja..