성장하고 개발하는 계란의 이야기

문제 풀이고려해야할 점더보기타일은 위와 아래로 존재하고 있다. 이 문제는 위와 아래 타일에 각각의 경우에 따른 계산이 필요하다.  n의 최대 개수는 100,000 이므로 모든 경우의 수를 완전 탐색할 경우 시간 초과 문제가 발생한다.  풀이 아이디어 더보기다이나믹 프로그래밍타일의 개수에 따른 점화식을 세워 계산한다. 이때 점화식은 위 타일 아래 타일 분리하여 계산하여야 한다.  점화식 계산 DP 배열은 2차원으로 생성. int[][] dp = new int[n+1][2]; 형식으로 선언하였다. 이때 배열의 첫 번째 인덱스는 몇 번째 타일인지를 나타내고 두 번째 인덱스는 위 타일인지 아래타일인지를 나타낸다. 이 코드에서는 위의 인덱스를 0으로 아래를 1로 표시한다. 아래 타일 점화식아래 타일(dp[n][1..

문제  풀이 고려해야할 점더보기 선분의 겹침 처리: 여러 개의 선분이 주어졌을 때, 겹치는 부분을 제외하고 전체 선분의 총 길이를 구해야 합니다.입력 순서: 선분들이 입력되는 순서가 정렬되어 있지 않을 수 있으므로, 시작점 기준으로 선분들을 정렬할 필요가 있습니다.데이터 타입: 좌표의 범위가 매우 크거나 작을 수 있으므로, 오버플로우를 방지하기 위해 적절한 데이터 타입(long)을 사용해야 합니다.  문제 풀이 아이디어 더보기 선분 정렬: 시작점 기준으로 선분들을 정렬하여 겹치는 부분을 효율적으로 처리할 수 있도록 합니다.현재 선분의 범위 추적:변수 l과 r을 사용하여 현재까지의 유효한 선분의 시작점과 끝점을 추적합니다.초기값으로 l은 가장 작은 값(Integer.MIN_VALUE)으로 설정하고, r은 ..

풀이 고려해야할 점더보기여러 개의 테스트 케이스가 존재하며 각 테스트 케이스는 최대 100000개의 도미노가 주어진다. 시간 복잡도를 고려하면 O(n)이나 O(nlogn) 사이로 구현해야 한다.도미노는 순서대로 넘어지므로 이 순서를 바탕으로 처음 넘어뜨려야 하는 도미노를 찾아야 한다. 보통 도미노의 시작 지점을 찾아서 넘어뜨릴 것이나, 도미노가 루프 형태를 가질 경우 시작 지점이 존재하지 않을 수도 있다. (예외 케이스)예외 1: 루프 형태 예외 2: 올가미 형태   문제 풀이 아이디어 더보기먼저 모든 도미노의 연결 관계를 저장한다. (자신을 넘어뜨릴 수 있는 도미노는 부모, 자신이 넘어뜨리는 도미노는 자식으로 설정하여 연관관계를 저장)부모가 없는 도미노의 경우 사람이 직접 넘어뜨려야 하므로 해당 도미노..

문제 풀이 고려해야할 점더보기입력 데이터의 수는 100000개 이하로 최악의 경우를 생각하면 O(nlogn)의 시간 복잡도로 문제를 해결해야 한다. 길이만 출력하는 것이 아닌 제거해야 하는 전깃줄의 번호도 출력해야 하기 때문에 각 경우에 제거되는 혹은 남는 전깃줄의 번호를 저장하고 추적해야 한다. 출력하는 것은 A 기둥의 번호이다. 실수로 B기둥의 번호나 임의로 부여한 인덱스를 출력하지 않도록 주의해야 한다.  문제  해결 아이디어더보기겹치지 않는 경우를 찾으려면 왼쪽과 오른쪽 인덱스가 서로 교차하지 않도록 전깃줄을 선택하면 된다. 즉 왼쪽과 오른쪽 모두 증가하는 전깃줄의 경우의 수 중 가장 많은 수의 전깃줄이 배치된 것을 찾으면 된자. (LIS 문제)가장 긴 증가하는 부분수열은 DP와 이분 탐색으로 풀..

문제https://www.acmicpc.net/problem/2447    풀이 고려해야할 점 *를 어떤 방법으로 찍을 것인가결과 출력알고리즘재귀풀이 설명 1. * 찍기먼저 n*n 크기의 2차원 배열을 선언하고 여기에 출력 값을 저장한다. 재귀함수를 통해 *을 찍어야 하는 곳의 위치를 구한 뒤 해당 위치에 *을 할당하고 배열을 출력한다.  재귀함수는 f(x,y,d)의 형식으로 호출한다. x, y는 x, y 좌표이며 d는 처음에는 입력 값의 지수(입력 = 3^m에서 m의 값)를 할당해 준 다음 재귀 호출시마다 값을 1씩 감소한다. x,yx+3^m,yx+2*3^m ,yx, y+ 3^m x+2*3^m ,y+ 3^mx, y+2* 3^mx+3^m, y+2*3^mx+2*3^m , y+2* 3^m함수 호출 시 d의 ..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 아이디어 초반에는 두 시간 대 사이에 분당 2회씩 알람 숫자를 세고 if 문으로 예외 케이스에서는 알람 횟수를 더하거나 빼는 방식으로 진행하려고 하였으나 예외 케이스를 정의하고 조건문으로 확인하는 것에 있어서 어려움을 겪었다. 결국 다른 사람의 아이디어를 참조해서 문제 풀이를 마무리했다. 문제 풀이의 핵심 아이디어는 모든 경우의 수를 확인하여 숫자를 세는 것이었다. 시간은 24시간으로 한정되어 있으며 반복문도 한 번 밖에 사용되지 않아 시간 복잡도가 높지 않다. 두 지점 사이에 존재하는 매 초마다 ..

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 아이디어 각 도형의 특징을 고려하면 쉽게 풀 수 있다. 임의로 생성된 정점: 임의로 생성된 정점은 들어오는 간선은 없으며 나가는 간선만 존재한다. 또한 도형은 최소 2개 이상 존재하니 나가는 간선은 2개 이상이다. (in_line=0, out_line>=2) 추가적으로 임의의 정점은 모든 도형과 1개의 간선으로 연결되어 있으니 나가는 간선(out_line)의 개수가 전체 도형의 개수와 같다. 막대그래프: 막대그래프는 들어오는 간선이 0개인 정점과 나가는 간선이 0개인 정점이 하나 존재한다. 그러나 ..