전체 글

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net > 의식의 흐름 priority queue와 deque을 같이 쓰면 괜찮지 않을까?라는 생각과 함께 시도했으나 시간 초과,,, 시간복잡도가 괜찮은줄 알았는데 "priority queue의 remove(Object o) 시간복잡도 = O(N)" 이었고 결과적으로 O(N*N)의 시간복잡도를 가지게 되어 시간 초과가 난 것이었다. 어떻게 하면 시간복잡도를 줄일 수 있을까 고민고민했지만 결국 포기하고 풀이를 찾아봤당😅 > 풀이 ** deq..

# 최소 공통 조상 (LCA) 정점 A와 정점 B가 각각 자신을 포함하여 초상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 구하기 처음 아이디어 = 정점의 부모를 따라 1칸씩 올라가자 시간 복잡도 = O(N) => 어떻게 더 빠르게 찾을 수 있을까? 1칸씩 올라가는 것이 아닌 2^K씩 올라가자 => 시간 복잡도 = O(logN) 이때 다른 수도 아닌 2^K인 이유는??? 모든 수는 이진수로 나타낼 수 있기 때문에 parent[0][V] = 정점 V의 1(=2^0)번째 부모 parent[1][V] = 정점 V의 2(=2^1)번째 부모 ★ = 정점 V의 1번째 부모의 1번째 부모 ★ => parent[1][V] = parent[0][ parent[0][V] ] ★★ parent[K][V] = p..

# 플로이드-워셜 알고리즘 모든 정점 사이의 최단 경로를 구하는 알고리즘 순환만 없다면 음수 가중치도 가능 동적계획법으로 접근 dist[i][j] = Math.min( ~ , ~ ) 형태를 가짐 N개의 정점을 가진다고 할 때, 모든 정점으로 가는 최단 거리를 확인하므로 시간복잡도 = O(N^3) N이 200~300 이하인 경우에만 가능 # 코드 1. INF 값으로 세팅 public static final int INF = 1_000_000_000; INF 값을 Integer.MAX_VALUE로 설정하는 경우, 연산 과정에서 overflow 발생하는 문제 종종 있음 => 잘 확인해서 INF 값 적당히 크게 설정하기 for(int i=1;i

17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 의식의 흐름 돌려야하는 줄들만 이동시키면 될 것 같아서 n이랑 i로 표현해보고 대입시켜줬다. 근데 중간에 반대로 집어넣어서 꼬이는 바람에 헤맸다... 풀이 1. 배열의 크기 n과 각도 d 입력 받기 d가 음수인 경우 360을 더해 양수로 변경함 2. 2차원 배열 2개(originalArr, modifiedArr)를 생성한다. 3. 2차원 배열을 회전 (d/45)번 45도로 회전 한번 회전시킬 때마다 originalArr값을 modifiedArr값으로 변경 코드 import java.io.*; import java.u..

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 의식의 흐름 두 포인터 사용해서 배열 다 돌리면 되겠는데? -> 오답 알고보니 두 수를 합할 때 target으로 잡은 수는 두 수에 포함이 안되어야 하는데 그 부분을 확인하지 않았다.. 그것만 고치니까 정답 풀이 1. 배열에 수 담은 후 정렬 2. 배열 0 ~ N까지 차례대로 target으로 잡고 두 수로 나타낼 수 있는지 확인 두 포인터가 가리키는 수들의 합 > target) 큰 수 가리키는 포인터 왼쪽으로 두 포인터가 가리키는 수들의 합 < target) 작은 수 가리키는 포인터 오른쪽..

11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 의식의 흐름 구간 합이 뭔지 제대로 공부 안하고 무작정 풀어보기 -> (시간제한 안보고) 그냥 인덱스로 for문 돌리면 되는데 왜 실버지? -> 시간초과ㅎ... 풀이 1. 부분 합 배열 만들기 2. 인덱스 받아서 부분 합 적절하게 사용하기 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOExcep..

# 구간 합 구간 합 : i ~ j 인덱스 값들의 합 => 특정 구간 인덱스의 합 부분 합 : 0 ~ k 인덱스 값들의 합 => 처음부터 특정 인덱스까지의 합 시간 복잡도 반복문을 통해 i ~ j 인덱스 값들의 합을 구하는 경우) O(N) (i=0, j=N) 시간 복잡도를 줄이기 위해서는 합 배열을 이용해야 함 => O(1)으로 감소 # 합 배열 합 배열 S, 배열 A S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] 합 배열 : 기존의 배열을 전처리한 배열합 배열 만드는 공식 S[i] = S[i-1] + A[i] 합 배열을 이용해 구간 합 구하는 공식 S[j] - S[i-1] # 관련 문제 [JAVA] 백준 q11659 - 구간 합 구하기 4 11659번: 구간 합 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 일단 A, B, C,...에 대해서 색인 번호를 줘야하니까 HashMap을 써야겠다고 생각했다. 나중에 영문자에 따라 색인 번호를 answer에 넣어주어야 하므로 HashMap의 key는 String(영단어), value는 Integer(색인 번호)로 설정했다. msg의 어디까지 체크했는지 알 수 있도록 checkIdx를 하나 두고 checkIdx가 msg 길이보다 같거나 커지면 map에 넣고 색인 번호 찾고 하는 작업들을 그만두면 되지 않을까?하고 생각한대로 코드를 짰는데 answer에 마지막 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 문제 대충 읽은 후 "{", "}" 지우고 HashSet 이용해서 중복되지 않게 숫자 걸러서 다시 int[]에 담으면 되는거 아닌가?라고 생각하고 풀었다가 바로 테스트케이스들 대부분 실패 정신 차리고 문제 다시 제대로 읽었더니 "원소의 순서가 다르면 서로 다른 튜플입니다."가 있었네,, 어떻게 풀까 고민하다가 String s에 많이 포함된 순서대로 a1, a2, ...인 것을 깨닫고 숫자 별로 작성된 개수에 따라 내림차순 정렬하면 되겠다고 생각했다. 풀이 1. "{", "}" 제거 후 "," 기준..