혜유의 코딩신 만들기 프로젝트

N과 M의 범위 때문에 값을 일일이 구하면 시간초과가 발생한다따라서 dp를 이용해서 풀어야 한다는 것은 이해가 갔는데..일반적인 누적합을 이용하니 결과를 구할때에 N*M 시간복잡도가 나와아슬아슬하게 테케를 통과했다...출처: https://developerjisu.tistory.com/9위의 사진처럼 누적합을 구해야한다는 것을 깨달았다!1. 1행/1열은 단순 누적합ex. 1행이 1 2 3 4 -> 1 3 6 101열이 1 2 3 4 -> 1 3 6 102. 나머지 행/열부터는 위와 같은 방식으로 누적합을 구해야지표에 한번에 저장할 수 있다  [1차 풀이]import java.io.*;import java.util.*;public class Main { public static void main(St..

전형적인 백트래킹 문제이다.다만 각 순열의 결과를 자료구조에 저장하게 된다면 메모리 초과가 발생한다.맨 처음 정렬된 상태로 순열의 결과를 저장하려고 TreeSet 자료구조를 선택해서메모리 초과가 났다 ㅜㅜ 순열 결과를 저장하지 않고바로 sb에 담아서 출력하는 방식으로 수정해서 해결했다! https://www.acmicpc.net/problem/6443 첫번째 풀이import java.util.*;import java.io.*;public class Main { static String words; static boolean[] visited; static HashSet answer = new HashSet(); static void backtraking(String result, i..

dfs, bfs 개념만 알고 있으면 쉽게 풀 수 있는 문제다!다만 처음에 문제를 잘못 이해해서 마지막 테스트케이스가 이상하게 출력됐다..모든 정점을 다 방문했을 때에 dfs, bfs 종료되도록 코드를 구현했었는데마지막 케이스 같은 경우에는 정점은 1000까지 있지만연결된 정점 정보가 999,1000만 나오기 때문에 모든 정점이 다 주어진 것은 아니다. 따라서 종료 조건을 없애고, result를 배열에서 List로 자료구조를 변경했다 ! https://www.acmicpc.net/problem/1260  import java.io.*;import java.util.*;public class Main { static int N, M, V; static ArrayList[] graph; sta..

문제를 꼼꼼히 봐야한다!두가지를 간과해서 계속 틀림,,;;처음에 left, right 범위를 잘못 잡아줘서 계속 2N%..에서 틀림 ㅜㅜ'이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다.'라는 조건 때문에 최소와 최대를 left=1(0이면 x), right=L-1로 잡을 수 있다.또한 개수를 세는 것이므로 -1을 해줘야 한다처음에는 (arr[i+1]-arr[i])/mid로 해서 값이 잘 안나왔다 ..만약 mid=200이라고 하고 arr[1]=200, arr[0]=0이라고 하면cnt=1이 나오지만 최대값이 mid이므로 1개를 세울 수 없다..!따라서 (arr[i+1]-arr[i]-1)/mid 로 cnt를 세줘야 한다  https://www.acmicpc.net..

괄호가 없는 경우/있는 경우를 모두 고려해서 완전탐색으로 풀이하면 된다dfs를 생각하지 못해서 삽질하다가 다시 풀었다 ㅜㅜ두 가지 경우로 나뉘기 때문에 dfs를 이용해서 괄호가 없는 경우를 먼저 모두 구한 후있는 경우를 구하면 쉽게 풀 수 있다  https://www.acmicpc.net/problem/16637  import java.io.*;import java.util.*;public class Main { static int N; static int answer = Integer.MIN_VALUE; static ArrayList nums; static ArrayList operator; static void dfs(int depth, int result){ ..

일단 처음에 문제가 잘 이해가 가지 않아서 오래 걸렸다..도시의 개수 N이 연결되어 있는지의 대한 정보가 N*N개 입력,여행 계획에 대한 정보를 M개 입력하는 것이다..또한 순간 착각해서 A->B, B->A를 같은 경우로 생각해서 ArrayList에 양방향으로 추가해줬는데..다른 경우이므로 따로 List에 추가해주지 않아도 된다 !! 이 문제는 bfs로 풀이해도 되지만union-find 알고리즘으로 푸는 게 더 수월하다 ! https://www.acmicpc.net/problem/1976   import java.io.*;import java.util.*;public class Main { static int N, M; static int[] parent; static void union..

리스트를 처음에 정렬해야 함lost와 reserve 모두에 해당하는 학생 먼저 판단한 후에나머지 학생들을 판단해야 한다.나 같은 경우에는 빌려준 학생 처리를 -1로 하고 싶지 않아서int[]에 있던 데이터를 ArrayList에 넣고빌린 경우에 리스트에서 값을 remove로 제거하도록 코드를 구현했다.but.. remove로 값을 제거하는 경우에 index도 함께 -1 update 해줘야 함..(이 부분 놓쳐서 계속 부분점수 나왔다 ㅜㅜ) https://school.programmers.co.kr/learn/courses/30/lessons/42862?language=java# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이..

https://school.programmers.co.kr/learn/courses/30/lessons/131124 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr MAX(count(review_id))를 이용해서 가장 많은 리뷰수를 구하고이 리뷰수와 동일한 만큼 리뷰를 쓴 사람을 구하면 된다!또한 리뷰를 많이 쓴 사람이 여러 명이므로 in 을 사용해야 한다  select m.member_name, r.review_text, to_char(r.review_date, 'YYYY-MM-DD')from member_profile m inner join rest_re..

똑같은 car_id를 가진 차에 대한 대여 기록이 여러 개 있을 수 있다따라서 11월에 대여 가능한 차를 조회하기 위해서는11월에 대여 불가능한 차(car_id)를 먼저 서브쿼리로 선별한 후에이에 해당하지 않는 차를 not in으로 골라내야 한다!! https://school.programmers.co.kr/learn/courses/30/lessons/157339 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  select c.car_id, c.car_type, 30*c.daily_fee*(1-p.discount_rate*0.01) as feefrom car..

(0,0)에서 시작해 y==3인 경우까지 가는 최단 거리를 구하는 문제로이해할 수 있으므로 bfs로 풀 수 있다하지만 범위가 크기  때문에 기본 이차원배열로 방문처리를 하면 시간초과가 발생한다따라서 ArrayList[]에 값을 저장한 후에방문한 경우에 remove로 배열 값을 바로 바로 삭제해주는 식으로 방문처리를 해줘야 한다여기서 주의할 점은 삭제한 경우에 Index 크기가 1씩 줄어들기 때문에 -1을 해주어야 한다!  https://www.acmicpc.net/problem/2412 import java.io.*;import java.util.*;public class Main { static ArrayList[] map; static int n, T; static int bfs(){..