오늘의 목표
오늘은 다 듣지못한 강의를 다 들어야하기 때문에 기존에 추가된 양의 목표는 없지만..
빨리 하는 것에 초점을 맞추는 걸 지양하기 위해, 이번엔 다른 형식으로 강의 진행률을 표시할 수 있게 바꿨음
훨씬 깔끔해져서 얼마나 더 해야하는지를 보기 편할 듯 싶다!
그리고 오늘은 해야할 일이 많아 많은 업무들만 보게 될 듯 싶어
건강을 생각해 여러 근력운동 루틴까지 계획했다!
PT를 받고있는 친구에게 부탁해 맞춤형 운동을 추천받았지~~
뭐.. 그만큼 제대로 자극을 주는 자세들이라 해서 조금 무섭긴하지만, 오히려 재밌을 것 같아서 벌써부터 신났음 🤩
자 그러면 스피드하게 오늘 계획을 진행해볼까~
1. PS - 2문제 이상 풀기
어제 문제가 올라오지 않아서 25일 문제를 풀었는데, 알고보니 월/목 정기 미팅이었기 때문이었음!
그래서 지금 오늘(29일) 문제까지 여러 올라온 터라 무슨 문제를 풀지 고민이 되긴하는데.. 그래도 오늘 문제부터 풀어보는게 맞겠지??
📌 25일 선정 문제
이 3문제를 모두 풀고 생각보다 빠르게 풀었다면 어제 문제들도 건드려볼 생각이다
오늘도 구글 타이머를 켜고 달려보자
비기너 - 부족한 금액 계산하기
단순 반복문만 잘 쓰면 풀리는 문제였다
3분 50초 정도 썼음
딱히 어려웠던 점도, 기록하고 싶은 부분도 없으니 다음문제로 넘어가야겠다
미들러 - 삼총사
보자마자 조합문제라 생각했고 바로 코드를 쳤는데
어라? 테케 2개가 틀렸었다
이 고정 스니펫인 조합이 왜 틀렸나.. 한참 봤는데
어이없는 실수를 하나 발견했다
조합은 내가 뽑았던 항목 다음순번부터 넣는 로직으로 다시 뽑는데, 초기값을 0으로 줘서 0을 보지 못한 채로 1부터 스캔해서였음..
그래서 start값을 -1로 주고 다시 돌리니 맞출 수 있었다..
너무 스니펫처럼 써서 몰랐나..
이 문제에 7분이나 쓰다니
챌린저 - 점 찍기
43분 경과
/*
x^2 + y^2 = r^2
중간 좌표 => x==y, 2*x^2 == r^2
중간좌표 부터 x,y 증가하는 방향으로만 보면 가능할듯
*/
import java.util.*;
import java.io.*;
class Solution {
public long solution(int k, int d) {
long ans = 0L;
int mid = (int) Math.sqrt(d*d/2);
ans += (int) Math.pow(mid/k, 2);
int rest = 0;
for(int i=mid; i<=d; i+=k){
for(int j=0; j<=d; j+=k){
if(i*i + j*j <= d*d){
rest++;
}
}
}
ans += 2*rest;
rest = 0;
for(int i=mid; i<=d; i+=k){
for(int j=mid; j<=d; j+=k){
if(i*i + j*j <= d*d){
rest++;
}
}
}
ans -= rest;
return ans;
}
}맞왜틀 중. . .
A영역에 속하는 걸 먼저 구하고, B영역 x 2 해서 더해주면 안되나? . . . mid를 double형으로 가져가야만 하겠지?
그렇게 고민해도 결국 답이 나오지 않아서.. 결국 다른 사람 풀이를 열었는데 반복문 하나로 끝낸 형태를 보았음
이게 가능한가 라는 생각을 하다가 반복문 하나만으로 짜보려 했는데 생각해보니 정말 간단한 형태로 만들 수 있었음
정답을 얻고 코드를 비교해보니 변수 제외 다른 점은 없었다
정말 이 문제로 머리가 지끈거렸다니..
설마 난이도를 알고 접근했기 때문에 더 어렵다고 느꼈나?
라는 생각을 좀 했는데
추가적으로 난이도를 모르는 문제를 풀어볼까 싶었음
SWEA 5656. [모의 SW 역량테스트] 벽돌 깨기 1차전
갑자기 왠 SWEA문제냐 싶겠지만 이게 오늘SSAFY 과제라 ㅎㅎㅎ
어짜피 풀어야 하기 때문에 넣어봤다
원래는 과제 풀고난 후 추가적으로 푼 문제를 기록에 남겼는데 오늘은 순서를 바꿔서 풀었기 때문에 한번 기록에 남겨보려고 한다
[모의 SW 역량테스트]라는 말머리가 붙어있는데 이건 모의 A형과 B형 대비 문제로 연습해볼 수 있도록 올려둔 문제임
풀어보고 싶으면 이 말머리로 검색해서 풀어봐도 좋다!
아무튼 문제를 풀어봐야지
위에서만 벽돌을 하나씩 깨고, 각 벽돌에 적힌 수만큼 상하좌우 방향으로 폭발한다 . . .
그러면 같이 터지는 거니까 한번 전체 스캔해서 어딜 건드렸을 때 같이 터진다는 정보를 체킹하고 그 벽돌에 가장 먼저 올 수 있는 위 벽돌을 부순다?
그런데 엣지케이스가 없을까..
1. 그렇게 터지는 수가 같은 영역이 두 곳 이상이라면
=> 터지고 난 후 다른 큰 숫자가 근처에 있어서 없앨 수 있으면 최적이겠지
2. 조금 조금 터진 후에 많이 터질 수 있는 경우가 최적인 경우는 없나?
=> 근데 무조건 가장 위층을 터트려야하니까, 더 위에있던 숫자가 내려오면서 밑의 영역을 터트려줄 수 있다면 최적은 아닐 것. . . 어라 그러면 위에 건드려서 터지는 경우가 아니라 다른 블록 폭발로 인한 연쇄폭발로 중간의 허리 블록들을 부술 수 있다면..?
26분 경과 . . .
아무리 생각해도 최적의 솔루션은 떠오르지 않는다..
도저히 모르겠어서 사람들 풀이 어떻게 했는지 구경하러 갔는데
엥??? 이걸 최적화를 안하고 그냥 구현한다고...??
최적화 솔루션 생각전에 구해본 시간복잡도
N(최대 4)개의 벽돌을 떨어트리고, 맵은W(최대 12)의 가로 길이와H(최대 15)세로 길이를 가짐sol 1) 벽돌을 떨어트릴 구간을 고르고, 그 구간에 대해 전체 맵 탐색으로 몇개가 터트려지는지 본다. 그리고 N개의 벽돌을 떨어트리니까 각 어떤 선택을 헀는지도 관계를 고려해야 함
=> (HxW)^(NxW) 이게 넘지 않나..?
생각하다가 6시가 넘어버렸고, SSAFY 퇴실 찍고 간단히 김치우동 뇸뇸한 후 주변 카페로 카공하러 왔다
SWEA 5656. [모의 SW 역량테스트] 벽돌 깨기 2차전
흐엑 벌써 7시네..
자 이제 다시 풀어보자~~
시간복잡도가 도저히 바로 떠오르지 않아서 로직을 써보고 계산하기로 했음
1. 떨어트릴 N개의 블록 중 현재 블록 n번째
2. 맵 전부를 스캔하면서 같이 터지는 구간들을 체크
3. 터지는 구간 하나를 선택하고
4. 그 구간을 지우고
5. 공중에 뜬 블록을 모두 내린다.
6. 그 다음 블록을 선택하고 1번부터 다시 반복한다쓰다보니까 이거 재귀로 하면 되려나?
가만보니 조합구성이네
그러면 depth는 4일테고,
1번은 O(N),
2번은 O(W x H),
3번은 최악의 경우 모두 1일 때니까 O(W x H)
4, 5번은 같이 진행하면 O(W x H)가 걸리겠네
6번은 총 시간복잡도에서 N제곱하면 될듯
=> O((WH)^(Nx3)) == O(180^12) == 1,156,831,381,426,176,000,000,000,000(???)
아무리 생각해도 안되는데... 씁
일단 코드를 그대로 작성해 보기로 했음
import java.util.*;
import java.io.*;
class Solution{
static int T,N,H,W,initRemainBlock,ans;
static int[][] board;
static int[] dx = {-1,1,0,0}, dy = {0,0,-1,1};
static int divide, remove;
public static void main(String args[]) throws Exception{
System.setIn(new FileInputStream("input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for(int t=1; t<=T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
ans = Integer.MAX_VALUE;
board = new int[H][W];
initRemainBlock = 0;
for(int h=0; h<H; h++) {
st = new StringTokenizer(br.readLine());
for(int w=0; w<W; w++) {
board[h][w] = Integer.parseInt(st.nextToken());
if(board[h][w] !=0) initRemainBlock++;
}
}
solution(1, initRemainBlock, board);
sb.append("#").append(t).append(" ").append(ans).append("\n");
}
System.out.print(sb);
}
public static void solution(int depth, int remainBlock, int[][] map) {
if(depth==N) {
ans = Math.min(ans, remainBlock);
return;
}
for(int w=0; w<W; w++) {
divide = 1;
int[][] vis = divideBoardWithBomb(map);
System.out.println("vis"+" "+w+" "+depth);
print(vis);
for(int space=1; space<=divide; space++) {
remove = 0;
map = removeAndDropBlock(map, vis, space);
System.out.println("map"+" "+space+" "+depth);
print(map);
solution(depth+1, remainBlock - remove, map);
}
}
}
public static void print(int[][] curMap) {
for(int h=0; h<H; h++) {
for(int w=0; w<W; w++) {
System.out.print(curMap[h][w]+" ");
}
System.out.println();
}
System.out.println();
}
public static int[][] divideBoardWithBomb(int[][] map) {
int[][] divideBlocks = new int[H][W];
for(int h=0; h<H; h++) {
for(int w=0; w<W; w++) {
boolean[][] vis = new boolean[H][W];
boolean changeCntFlag = false;
if(map[h][w] != 0 && divideBlocks[h][w] == 0) {
Queue<Point> q = new LinkedList<>();
q.add(new Point(h, w, map[h][w]));
while(!q.isEmpty()) {
Point cur = q.poll();
int x = cur.x;
int y = cur.y;
int val = cur.val;
for(int v=1; v<val; v++) {
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
if(0<=nx && nx<H && 0<=ny && ny<W) {
if(vis[nx][ny]) continue;
vis[nx][ny] = true;
divideBlocks[nx][ny] = divide;
changeCntFlag = true;
if(map[nx][ny] == 0) continue;
q.add(new Point(nx, ny, map[h][w]));
}
}
}
}
}
if(changeCntFlag) divide++;
}
}
return divideBlocks;
}
public static int[][] removeAndDropBlock(int[][] map, int[][] vis, int change) {
for(int w=0; w<W; w++) {
for(int h=H-1; 0<=h; h--) {
if(vis[w][h]==change || map[w][h]==0) {
if(vis[w][h]==change) {
remove++;
}
if(h==0 || map[w][h] == map[w][h-1])
continue;
int swap = map[w][h];
map[w][h] = map[w][h-1];
map[w][h-1] = swap;
}
}
}
return map;
}
}
class Point{
int x,y,val;
public Point(int x, int y, int val) {
this.x=x;
this.y=y;
this.val=val;
}
}답이 다르게 나와서 맞왜틀중. . .
시계를 보니 벌써 오후 9시다.. 다른 해야할 일이 있어서 PS는 여기까지 해야지..
답 코드를 봤는데 로직은 나와 같아서 내일 코드를 한번 뜯어서 수정해봐야겠다
진짜 이게 왜 돌아가지..?
2. JPA 강의 듣고 정리
HTTP 강의 부터 할까 했는데 이건 가벼운 마음으로 들어도 이해할 수 있기도 하고, 심화적으로 연결하고 싶은 부분도 있어서 이 다음으로 미루기로 했음!
JPA 강의는 책으로 공부하려고 사지 않았었는데, 스터디를 하게 되면서 강의를 보게 되었음..
다행히 한 스터디원이 계정을 빌려주셔서 강의를 들을 수 있게 되었다!
책과 강의가 어떻게 다른지도 궁금했는데, 그걸 이렇게 볼 수 있게 되어서 너무 좋다 ㅎㅎ
자바 ORM 표준 JPA 프로그래밍 - 기본편 의 진도를 이제 빼볼까!
오늘 나의 목표는 섹션 7까지 듣는건데 최대한 해봐야지
마무리
그렇게 강의 몇개를 듣고 지쳐버린 나는 오늘도 비슷한 마무리를 맞이했다
하아.. 언제쯤이면 다 이룰 수 있으려나
