n . n

https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr A, B 플레이어가 주사위를 절반으로 나누고, 본인의 주사위에서 나오는 숫자들의 합이 최대이면 승리하는 게임을 함.이 때 A가 승리하는 확률이 최대이도록 하는 A의 주사위 배열을 구해야 함  일단 주사위의 개수는 최대 10, 주사위에 적힌 숫자도 최대 100이므로 완전탐색 을 느껴야 한다완탐으로 구현될 코드의 흐름을 단계별로 생각해 보면 1. 주사위의 조합을 구한다2. 해당 주사위의 조합에서 나올 수 있는 합들을 구한다3. A, B의 각 합을..

https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   카드 게임을 진행할 수 있는 최대 라운드 수를 구해야 함 초기 접근 방식매 라운드마다 다음과 같은 경우의 수가 존재하므로, dfs 알고리즘을 떠올림: 카드 두 장 구매 / 카드 한 장 구매 / 구매하지 않음 하지만 dfs를 적용할 경우 카드 배열의 최대 길이는 1000이니까대략 3^500 의 시간복잡도가 발생 > 시간초과 따라서 greedy 방식으로 바꾸어서 풀이(타 풀이를 참고했다..) - 매 라운드마다 카드를 버리는 게 아닌, 따로 저..

https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에서 완전 탐색을 수행하면 무 조 건 효율성에서 시간초과가 뜬다.. 효율성을 통과할 방식을 고민해 보았으나 영 방법이 떠오르질 않아서 😅 질문 게시글을 읽었다.. 처음에 내가 생각한 방식은 아래 글 더보기 다음과 같은 테스트 케이스를 예시로 들면 board = 1 2 3 4 5 6 7 8 9 skill = { 1번째 스킬 : {1, 1, 1, 2, 2, 4}, 2번째 스킬 : {1, 0,..

누적 합 1차원 배열을 예로 들 때, 누적 합은 인덱스 0에서부터 인덱스 i까지의 값들을 모두 더한 값이다. 즉 다음과 같은 배열이 존재할 때 {-1, 7, 4, -3, 0, 1, 8, 7} 위 배열의 누적 합 {-1, 6, 10, 7, 7, 8, 16, 23} 은 O(n)의 시간복잡도를 통하여 다음과 같이 구할 수 있다. int[] cumulativaSum(int[] arr){ int total = 0; int[] sum = new int[arr.length]; for(int i=0; i 변경될 때마다 누적 합 재계산(O(n))의 시간복잡도가 소요된다는 단점이 있다. 이러한 약점을 개선한 것이 세그먼트 트리를 이용한 방식임 세그먼트 트리를 이용한 방식 세그먼트 트리는 위처럼 이진 트리 구조를 지니는, ..

https://school.programmers.co.kr/learn/courses/30/lessons/42891 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시간 k의 범위가 위와 같으므로, 완전 탐색을 통하여는 효율성 테스트를 통과할 수 없음 다음과 같은 예시 food_times = {4, 5, 5, 5, 1, 3} k = 15 이의 막대그래프를 그려보면 다음과 같다 효율적인 계산을 수행해야하므로.. 얘를 cost ASC 순으로 재정렬해보면 위처럼 정렬되는데.. 코드 상에서는 priority queue를 통하여 위처럼 정렬하였다 따라서 큐를 poll..

https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 테스트케이스 12,14,25 틀림!!!!!!!!!!!!!!! 왜틀린지 모르겠다.. 돌겟다 좀만 더 해보고 해결 안 될거 같으면 봉우리에서부터 시작ㄱ 방식으로 바꿔서 구현해 봐야 겠다 ^^ 누가이기나보자 -> 봉우리 시작 방식으로 변경하였다.. 😅 단번에 통과해서 허무해지다 시작점부터 시작하도록 구현한 방식(부분 통과) import java.util.ArrayList; import java.uti..

https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 완전 탐색이 하기 싫어서.. 우선 순위 큐를 적용하여 풀이하는 방법으로 계속 생각해 보았지만 예외 케이스가 내 눈에도 계속 보였다ㅜ 결국 완전 탐색으로 ㄱㄱ 👇 참고 문서 https://school.programmers.co.kr/questions/25736 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는..

https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 맨 처음 bfs + priority queue를 사용하여 풀이하였고, 시간 초과 ㅜㅜ 가 떴다(아무래도 한 번 방문했던 좌표에 또 방문할 수 있으니까) 아마 처음의 방식의 시간복잡도는.. 4^k횟수(최대 2500) 사실 프로그래머스의 시간 초과 기준은 잘 모르겠지만 2의 5000승 정도면 시간초과가 안 나는게 이상하긴 하지.. 미친거지 최적화할 방식이 도저히~~ 생각이 나질 않아서 아래 게시글을..

https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 숫자에 대해 이진수로 변환하였을 때, 그 이진수로 포화 이진 트리를 만들 수 있는지 확인하는 문제이다 즉 58을 예제로 생각해 보면 58 -> 0111010(2) 이진수 문자열을 중위 순서로 표현한다고 생각하면 되고, 위처럼 0은 dummy 노드로 표현하여 이진 트리로 나타낼 수 있다 이 문제에서 체크해야 할 점?은 다음 두가지인 것 같다 1. 트리를 포화 이진 트리 형태로 만들어야 하므..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 맨 처음에는 [1️⃣번째 방법] 조합으로 치킨집을 고른 뒤, 집과 치킨집 사이의 최소 거리들을 bfs를 적용해서 풀이했다.. 일단 이 방법으로 풀면 풀어지긴 하지만 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Array..