Algorithm

📝문제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{ ..

📝문제https://www.acmicpc.net/problem/12891DNA 비밀번호_12891번티어: 실버 2평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열의 부분문자열을 뽑았을 때 “AAAA”와 같이 보안에 취약한 비밀번호가 만들어 질 수 있기 때문이다...

📝문제https://www.acmicpc.net/problem/12865평범한 배낭_12865번티어: 골드 5💡풀이문제 유형다이나믹 프로그래밍 걸린 시간60분 시간 복잡도O(NxK) 풀이 방법 도출일단 dp라고 생각도 못했고, 배낭문제 유형이 있다는 것도 몰랐다.. 그래서 문제 이해하는데만 30분 걸린 거 같다이 블로그 덕분에 겨우 풀 수 있었다.. https://howudong.tistory.com/60 import java.util.*;import java.io.*;class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputS..

📝문제https://www.acmicpc.net/problem/7662이중 우선순위 큐 7662번티어: 골드 4💡풀이문제 유형자료 구조 트리를 사용한 집합과 맵 우선순위 큐 걸린 시간60분 시간 복잡도O(T×klogk) 풀이 방법 도출deque를 이용해서 시도했다가 시간초과 에러가 났고 우선순위 큐를 이용하려다 실패하고 결국 TreeMap이라는 자료구조를 사용하게 되었다.TreeMap이란 정렬된 맵으로 항상 키가 정렬된 상태로 유지되며, O(log N)의 시간 복잡도로 데이터를 삽입, 삭제, 조회할 수 있다. HashMap의 정렬된 버전이라고 생각하면 쉽다. (HashMap보다 삽입/삭제는 느리지만 정렬된 데이터를 다룰 때 훨씬 효율적이다.)firstKey(): 최솟값 찾기lastKey(): 최댓값 ..

📝문제https://www.acmicpc.net/problem/1504특정한 최단 경로 1504번티어: 골드 4💡풀이문제 유형다익스트라 걸린 시간100분 시간 복잡도O((V + E) log V) 풀이 방법 도출bfs로 접근했다가 도저히 답이 안 나와서 다익스트라 알고리즘이라는 힌트를 얻고 풀이를 하였다.다익스트라 알고리즘이란 가중치가 있는 그래프에서 최단 거리를 찾기 위한 알고리즘으로, 우선순위 큐를 활용한다.해당 문제는 1번 노드에서 시작해 꼭 거쳐야 하는 노드 v1,v2를 지나 n번 노드까지 도착해야한다.즉 다익스트라 함수를 구현하여(1번 -> v1번 노드의 최소 거리) + (v1번 -> v2번 노드의 최소 거리) + (v2번 -> N번 노드의 최소 거리)또는(1번 -> v2번 노드의 최소 거리)..

📝문제https://www.acmicpc.net/problem/2018수들의 합 5 2018티어: Silver 5 💡풀이문제 유형투포인터 걸린 시간거의 40분 시간 복잡도O(N) 풀이 방법 도출풀이법이 생각 안 나서 다른 사람의 풀이를 참고하였다..ㅠ완전 탐색으로 풀면 시간 초과 우려가 있어 투 포인터 알고리즘을 사용한다.start = 1, end = 1, sum = 1, count = 1로 선언 후sum sum > N 이면 start 위치를 오른쪽으로 옮겨 더 작은 수가 되도록 한다. sum -= startsum == N 이면 count 개수를 증가시키고 end 위치를 오른쪽으로 옮겨 더 큰 수가 되도록 한다. sum += end이 과정을 start import java.util.*;import j..