📝문제https://www.acmicpc.net/problem/2468티어 : 실버1 💡풀이 문제 유형dfs 걸린 시간37분 시간 복잡도O(N^2)최악의 경우 -> O(100*100*100) => 1000000번의 연산 => 1초 안에 ok 풀이 방법 도출구역 나누기 => dfs로 풀이 가능h를 증가시키면서 가장 큰 값이 나오는 경우를 저장해 두는 방법을 사용했다.h=0으로 두고 while 반복문을 돌린다.이때 구역의 수를 count로 두고 count가 0이 되면 반복문을 빠져나온다.  => 모든 위치를 다 방문함현재 위치의 높이가 h보다 높거나 같고, 방문하지 않은 위치라면 dfs를 돌려 현재 위치부터 사면을 검사해 방문을 체크해 준다.정답 max와 count 중 더 큰 값을 max에 저장하고 답을..

📝문제https://school.programmers.co.kr/learn/courses/30/lessons/161990 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr코딩테스트를 준비하는 머쓱이는 프로그래머스에서 문제를 풀고 나중에 다시 코드를 보면서 공부하려고 작성한 코드를 컴퓨터 바탕화면에 아무 위치에나 저장해 둡니다. 저장한 코드가 많아지면서 머쓱이는 본인의 컴퓨터 바탕화면이 너무 지저분하다고 생각했습니다. 프로그래머스에서 작성했던 코드는 그 문제에 가서 다시 볼 수 있기 때문에 저장해 둔 파일들을 전부 삭제하기로 했습니다. 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판입니다. 이때 컴퓨터 바탕화..

📝문제You have a long flowerbed in which some of the plots are planted, and some are not. However, flowers cannot be planted in adjacent plots. Given an integer array flowerbed containing 0's and 1's, where 0 means empty and 1 means not empty, and an integer n, return true if n new flowers can be planted in the flowerbed without violating the no-adjacent-flowers rule and false otherwise.💡풀이 문제 유형..

📝문제민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨..

📝문제https://www.acmicpc.net/problem/1074Z 1074번티어 : 골드 5💡풀이문제 유형분할정복 걸린 시간40분? 50분? 시간 복잡도O(N) 풀이 방법 도출r과 c가 현재 사이즈를 사등분 후 왼쪽 위인지, 오른쪽 위인지, 왼쪽 아래인지, 오른쪽 아래인지 판단하는 문제다.우선 size = 2^N으로 정의 가는하고, 이를 사등분하려면 newSize = size/2가 된다.그럼 이때 (0,0)을 기준으로 0 + newSize, 0 + newSize와 r,c를 비교 검사해 위치를 구한다.이후 왼쪽 위인 경우는 count를 그대로, 오른쪽 위인 경우 count에 newSize*newSize를 더해준다. 왼쪽 아래인 경우는 newSize*newSize*2,  오른쪽 아래는 newSiz..

📝문제https://www.acmicpc.net/problem/11660구간 합 구하기 5 : 11660번티어 : 실버 1 💡풀이문제 유형다이나믹 프로그래밍 걸린 시간80분.. 시간 복잡도  풀이 방법 도출전에 비슷한 문제를 풀었어서 어렴풋한 기억을 가지고 풀었다.일단 arr 배열에 입력 받은 값들을 넣어주고dp 배열을 생성한다. dp[i][j] = (1,1) 부터 (i,j)까지의 합이때 dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; 의 규칙을 갖는다.dp배열을 완성하면 (x1,y1)에서 (x2,y2)까지의 합을 구할 준비가 되었따.구간 합 식은 다음과 같다. sum = dp[x2][y2] - (dp[x1 - 1][y2]..

📝문제https://www.acmicpc.net/problem/11779최비용 구하기 2 : 11779번티어 : 골드3💡풀이문제 유형다익스트라 걸린 시간110분 시간 복잡도  풀이 방법 도출이제 가중치가 다른 경로 사이의 최소 비용 구하기 하면 바로 다익스트라가 떠오른다.이틀 전에 풀었던 최소비용 구하기 문제와 거의 흡사하나 출력 조건에 몇가지 추가 되었다 (https://girokeulhaja.tistory.com/135)우선순위 큐를 사용하여 인접한 배열 리스트를 검사해 최소비용을 갱신해준다.지나간 경로 출력 하는 방법을 모르겠어서 지피티한테 물어봤다,,그리고 StringBuilder 의 reverse() 메서드를 사용하려고 했으나 1 10 100으로 들어온 경우001 01 1이 출력 되므로 Ar..

📝문제https://www.acmicpc.net/problem/1043거짓말: 1043번티어: 골드 4💡풀이문제 유형유니온파인드 걸린 시간60분 시간 복잡도O(N+M) 풀이 방법 도출1. 이 문제의 키포인트: 진실을 알고있는 사람끼리 묶기2. hashset에 진실을 알고 있는 사람을 add한다.3. 같은 파티에 있는 사람들은 모두 같은 집합으로 묶는다. union4. 진실을 아는 사람의 최상위 부모를 새로운 set에 넣고5. 파티 별 사람들을 검색해 사람들의 최상위 부모가 set에 포함되어있는지 확인한다.import java.util.*;import java.io.*;class Main{ static int[] parent; public static void main(String[] arg..

📝문제https://www.acmicpc.net/problem/1916최소비용 구하기 1916번티어: 골드 5 💡풀이문제 유형다익스트라 걸린 시간60 시간 복잡도O(M log N) 풀이 방법 도출문제에서 최소비용을 보고 무슨 알고리즘이더라...? 고민했던,, 문제 최근에 비슷한 문제를 풀었기 때문에 다익스트라 알고리즘을 생각보다 수월하게 구현할 수 있었따.이렇게 유형이 정해져있는 것은 비슷한 문제 여러개 풀다보면 감이 잡히는 거 같다.우선순위 큐를 사용하여 인접한 배열 리스트를 검사해 최소비용을 갱신해주었다처음 제출할때 시간초과가 나서 if(cost > dist[now]) continue; 이 조건을 추가해주었다.import java.util.*;import java.io.*;class Main{ ..

1️⃣트랜잭션의 개념과 성질(ACID)🚀트랜잭션이란?단일한 논리적인 작업 단위논리적인 이유로 여러 SQL문들을 단일 작업으로 묶어서 나눠질 수 없게 만든 것SQL문들 중에 일부만 성공해서 DB에 반영되는 일은 일어나지 않는다.🚀ACIDAtomicity (원자성)모두 성공하거나, 모두 실패하거나 (All Or Nothing)trancation은 논리적으로 쪼개질 수 없는 작업 단위이므로 SQL문들이 모두 성공해야 한다.중간에 SQL문이 실패하면 지금까지의 작업을 모두 취소하여 아무 일도 없었던 것처럼 rollback 한다.데이터 베이스 상태가 계속 일관적일 수 있도록 유지Consistency (일관성)transaction은 DB 상태를 consistent 상태에서 또 다른 consistent 상태로 바..