stonesy

해결방법수를 순서대로 순회하면서 투 포인터로 서로 다른 두 수의 합으로 나타낼 수 있는 수의 개수를 구한다. ⇒ O(N^2) (N≤2000)*수의 위치가 다르면 값이 같아도 다른 수이다. 코드import java.util.*;import java.io.*;// O(N^2)public class Main_1253_G4_좋다_투포인터 { static int N; static int[] numbers; public static void main(String[] args) throws IOException{ // 1. 입력 및 초기화 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

해결방법2개의 용액을 골라야한다. 일반적으로 조합을 구하기 위해서는 O(2^N)의 시간복잡도를 가진다. 위 문제의 경우 2≤N≤100000이므로 적용불가능하다. (대략 N이 10을 넘어가면 불가능)투포인터로 접근한다.left+right의 절댓값이 answer보다 작다면 answer 갱신(left와 right 위치 저장)left와 right의 용액을 더했을 때 양수이면 → right-1left와 right의 용액을 더했을 때 음수이면 → left+1left결론적으로 투포인터로 O(N)의 시간복잡도로 문제를 해결할 수 있다.  코드import java.util.*;import java.io.*;// 308ms, 투포인터, O(N)public class Main_2467_G5_용액_투포인터 { stati..

해결방법최단 경로이므로 BFS로 접근한다.단, 이동하는 도중에 한개의 벽을 부수고 이동할 수 있다는 변수가 있다. 벽의 위치를 저장하고 먼저 벽을 부수고 출발하면 최악의 경우 시간복잡도가 O((N*M)^2)로 시간초과가 발생한다.따라서 3차원 배열로 거리/방문체크를 해야한다. 3차원 배열인 이유는 map 자체가 2차원 배열이고 벽을 부수지 않은 경우/벽을 부순경우를 나눠야 한다. 벽을 부수고 간 것이 먼저 도착하는 경우 벽을 부수지 않고 도착한 것이 방문처리되어 통과되지 못할 수 있기 때문이다. 코드1(거리 비교)import java.util.*;import java.io.*;public class Main_2206_G3_벽부수고이동하기_거리체크 { static int N,M; // N(1 ≤ N ..

해결방법기둥을 정렬한 후 가장 높은 기둥을 알아낸다.왼쪽 ~ 가장 높은 기둥까지 면적을 더한다. 왼쪽에서 가장 높은 기둥을 기준으로 가장 높은 기둥이 갱신될 때마다 면적을 더한다.오른쪽 ~ 가장 높은 기둥까지 위와 같은 로직을 반복한다.⇒ 정렬에 O(Nlog), 면적을 더하는데 O(N)의 시간복잡도가 소요된다. 코드import java.util.*;import java.io.*;// 112mspublic class Main_2304_S2_창고다각형 { static int N; static Tower[] tower; static class Tower{ int w, h; public Tower(int w, int h){ this.w=w; ..

스택해당 유형의 문제는 스택 자료구조를 사용하여 O(N)으로 문제를 해결할 수 있다.스택에는 항상 “현재 인덱스보다 높은 탑들의 인덱스들”만 들어있다. 1부터 N까지의 인덱스를 순회하면서, 현재 인덱스보다 낮은 탑들의 인덱스를 스택에서 제거한다. 스택의 최상위에는 레이저가 처음으로 도달하는 탑의 인덱스가 항상 위치하게 된다.Stack stack = new Stack();for(int i=1; i 코드import java.io.*;import java.util.*;//716ms, O(N)public class Main { static int N; static int[] tower; public static void main(String[] args) throws IOException{ ..

가장 긴 증가하는 부분수열(LIS)  가장 긴 증가하는 부분 수열을 구하기 위해 아래와 같이 DP를 이용해서 풀 수 있지만, 이 경우 시간복잡도가 O(N^2)이기 때문에 N값이 매우 커지면 위험하다고 생각했다.//1. dpfor(int i=0; iA[j]) dp1[i] = Math.max(dp1[i],dp1[j]+1); }} 이분탐색, O(logN)이분탐색을 이용하면 DP를 이용했을 때 O(N^2)이었던 시간복잡도를 O(NlogN)으로 줄일 수 있다.public static void binarySearch(List arr, int target){ int left = 0; int right = arr.size()-1; while(left=target){ right = mid-1; }else{ ..

외판원 순회(TSP)외판원 순회 문제란 모든 도시를 한 번씩 방문하고 다시 출발점으로 되돌아오는 최소 비용을 구하는 문제이다.N(도시의 수) 값이 작으면, 순열로도 문제를 해결할 수 있지만 N 값이 매우 커지면 불가능하다. 순열의 시간복잡도가 O(N!)일 때 N의 값이 대략 11을 넘어가면 위험하기 때문이다. N 값이 매우 클 경우, DP를 이용해서 풀어야한다. DP + 비트마스킹dp[current][visited]: current 도시에서 남은 도시들을 모두 방문하여 출발점으로 되돌아가기 위한 최소비용current: current 현재 도시visited: 현재까지 방문한 도시들을 비트마스킹으로 표현해놓은 것 비트마스킹모든 도시를 방문한 경우 visited == (1(1 도시를 아직 방문하지 않은 경우v..

다익스트라 알고리즘최단경로 → 다익스트라(Dijkstra) 알고리즘다익스트라 알고리즘은 한 정점에서 각 정점까지의 최단경로를 찾는 알고리즘으로 우선순위큐를 사용하는 경우 O(MlogN)의 시간복잡도를 가진다.(이때, N: 정점의 개수, M: 간선의 개수)  로직초기화시작 정점까지의 거리는 0으로 초기화후, 우선순위 큐에 넣음시작 정점 외의 다른 정점까지의 거리를 무한대로 초기화(dist 배열)인접한 정점의 거리 update우선순위큐에서 정점을 뽑아, 현재 정점으로 설정현재 정점에서 인접한 정점까지의 거리 update(시작 정점 → 인접한 정점까지의 거리보다 현재 정점을 거쳐서 가는 경우가 더 빠르다면, dist 배열을 초기화하고 우선순위큐에 넣음)우선순위큐가 빌때까지 2번을 반복 코드import java..

처음에는 슬라이딩 윈도우 기법으로 풀었으나 이 경우 시간복잡도가 O(N^2)으로 N의 최대값이 10^6이기 때문에 시간초과가 발생했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int N,M; static int[] numbers; static int answer; public static void main(String[] args) throws IOException { BufferedReader br = ..

13460번: 구슬 탈출 2 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 최단거리⇒bfs(⇒Queue) Queue에 원소가 없다면 종료 Queue의 원소가 있다면? 종료조건 확인 꺼내서 구슬을 움직임(구현) 큐에 다음 수행 추가 python from collections import deque N,M=map(int, input().split(" ")) board=[] for i in range(N): board.append([]) string = input(..