sori's Tstory

https://www.acmicpc.net/problem/1806 문제 개요N개의 수열에서 연속된 부분 수열의 합이 S 이상이 되는 가장 짧은 길이를 찾는 문제이다.해결 방법투 포인터(Two Pointer) 기법을 사용하여 다음과 같이 해결한다.low와 high 두 개의 포인터를 사용해 부분 합을 조절한다.sumNum이 S 이상이면 최소 길이를 갱신하고 low를 증가시킨다.sumNum이 S 미만이면 high를 증가시키며 부분합을 키운다.최소 길이가 초기 값(2e9) 그대로면 부분합을 만들 수 없으므로 0을 출력한다.코드 리뷰시간 복잡도: O(N)오류 가능성:low len = 2e9는 정수 연산을 고려하면 INT_MAX가 더 명확함else if (high == N)에서 break 처리 정확해야 함개선점le..

https://www.acmicpc.net/problem/14430 map이 주어지면 오른쪽 또는 아래쪽으로만 이동하여 주울 수 있는 자원의 최대치를 구하는 문제이다. 개인적으로 이동할수 있는 경우가 정해져있다는 점에서 숨바꼭질 문제와 비슷하다고 느꼈다.이 문제에서는 오른쪽 또는 아래쪽으로만 탐색을 해야하므로, 그래프 전체를 돌아다닐수 없고, 여러가지 경우의 수를 탐색 해 최적의 경로를 구해야 한다는 점에서 DP 문제 일것이다. 라고 느꼈다.우선 여느 DP 와 다를 것 없이 기존의 map 을 보존해야하므로  최대 자원 수를 구하는 이차원 DP와 원래 주어진 map, 2가지 이차원 배열을 선언 해야한다.처음에는 탐색 조건을 아래와 같이 설정했다. for (int i = 0; i 그러나 위와 같이 탐색을 하..

https://www.acmicpc.net/problem/27889  문제 출력 예제를 보자마자 해쉬 맵으로 풀어야겠다는 생각이 들었고, 푸는 김에 해쉬맵 메소드도 정리하면 좋겠단 생각이 들어서 쓴다. 풀이 각각의 약칭을 해쉬맵의 키에 넣고, 정식 명칭을  Value값에 넣으면 된다. 여러개를 출력하라고 했으면 While문을 돌렸겠지만, 여기서는 단순히 input 값을 키에 넣으면 되서 쉽다.import java.util.*;import java.lang.*;import java.io.*;// The main method must be in a class named "Main".class Main { public static void main(String[] args) { HashMap..

https://www.acmicpc.net/problem/1655이 문제의 핵심 전략은 두 개의 힙을 사용하여 중앙값을 유지하는 것임. 최대힙에서 중앙값(출력할 것)을 유지하면서, 최소힙이 중앙값보다 큰값을 가진 요소들을 저장한다.이렇게 되면 , maxHeap -> minHeap 을 연결하는 부분이 오름차순을 이루며, maxHeap의 마지막 값이 중앙값중 작은 것이 오게된다.각 입력시 최대힙의 루트를 중앙값으로 유지하기위해 조정이 필요만약, maxHeap의 루트가 minHeap의 루트보다 크다면 두 힙의 루트를 교환하여 조건을 맞춤(tmp 부분) 정답 코드import java.util.*;import java.lang.*;import java.io.*;// The main method must be in..

GROUP BY 란? 그룹 함수가 모든 데이터(또는 WHERE 절 조건에 충족하는 데이터)를 요약, 필터링하는 것이하면, GROUP BY는 각 데이터 별 필터링을 지원한다. 아래 그림에서 알수 있듯이, 그룹함수는 전체 테이블의 정보를 가져오지만, GROUP BY는 칼럼명이 같은 것 끼리 그룹핑 한 뒤에 각 그룹에 대한 계산 한다고 보면 된다. 간단한 예시로, 내가 대기업 A 회장일 때, 각 판매처의 매출을 구하고 싶다면 GROUP BY를, 전체 매출을 확인하고 싶다면 그룹함수를 쓰면 된다. SELECT VEND_ID, SUM(SALARY) AS SARARY FROM A GROUP BY VEND_ID; 그룹(집계) 함수(SUM,AVG,MIN,...) 자, 다시 오른 쪽위 그림을 눈여겨 보자. 그림은 GRO..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상정렬까진 어떻게 했지만 작업의 최솟값을 찾지 못했다. 처음에는 루트노드(가장 마지막 작업)을 시작으로 time배열에 더해 나가려고 했지만, 자식 노드의 형제 노드들까지 time을 더해 버리는 바람에 총 시간 이 나와버렸다. 문제에서 주어진 "서로 선행 관계가 없는 작업들은 동시에 수행 가능하다."라는 말은 사실 형제 노드들중 최댓값을 고르라는 말과 같다. (최솟값이 아닌 최댓값인 이유..

https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 설명 각각의 도시로 가는 버스의 비용들을 입력받아 출발 도시에서 도착 도시까지의 비용을 갱신하여 출력하고, 최소 비용으로 지나치는 경로를 출력하는 문제이다. 플로이드 워셔은 single source -all destination 이기 때문에 각 도시별 전체 비용을 출력하라는 힌트를 보자마자 플루이트 워셜을 떠올렸어야한다. 플루이드 워셜 시간 복잡도가 N^3 이라 그래프의 크기가 크면 안된..

https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 설명 우선 순위와 함께 문서가 주어졌을 때 우선 순위가 높은 애가 먼저 출력되어야 한다. 이때 내 문서는 몇번 째로 출력될까? 처음 생각한것은 우선순위 큐에 pair로 문서 번호와 우선순위를 둘다 넣어버리는 것이다. 우선순위 큐의 경우 pair에서 앞의 것을 기준으로 최댓값을 출력하고, 만약 first원소가 같다면, 두번째 원소를 기준으로 최댓값을 출력하기 때문에 나중에 우선 순위가 같더라도, ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 무작위 길이의 랜선이 N 개가 들어올 때, 나는 M개의 랜선이 필요하다. 가지고 있는 랜선을 동일한 길이로 잘라 M개를 만들고자 한다. 이때 랜선 길이는 최대한 길었으면 좋겠다. 이 때 어떻게 접근해야 할까? 우선, 대강의 길이를 파악 해야한다. 잘라야할 길이는 내가 가진 랜선 중 가장 긴 길이보다는 짧고, 0보다는 커야한다. 이 범위 내에서 최대한 빠르게 적정한 길이..

1. Out of Index 1. if 문에서 배열/ 큐/ 스택 의바운더리 검사를 먼저 하지 않을 경우 2. 기본 인덱스를 검사해두고 , 연산된 인덱스에 접근 할때 ex) if( n>0 && n < MAX ) arr[2 * n] =10; 컴파일 에러 1. 함수의 return 값이 일정하지 않을 경우 2. 헤더 함수 선언 하지 않고 함수 쓸경우(memset) ( 이 경우, 코드가 돌아가긴 하지만, 다른 여러곳에서 터질수도 +채점 환경에서는 아닐 수있다.) 2.기본 전역 변수는 다른 함수들 보다 맨 위로 올리자. 다른 함수에서도 쓰일수 있다 틀렸습니다 일출력을 cin과 scanf() 와 같이 쓰고 있다면, ios_base::sync_with_stdio(false); 구문을 제거해보자 코드 다시 짰을 때 사용..