동환아 공부해야지

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/14718 조건TimeLimit = 1s병사 수 N, 이겨야 할 병사 수 K (1 진수가 이기는 조건 (아래를 모두 만족)- 진수 힘 >= 병사 힘- 진수 민첩 >= 병사 민첩- 진수 지능 >= 병사 지능 풀이완전탐색-> 각 스텟의 모든 조합을 구해본다-> 주어진 병사가 최대 100명이므로, 시간복잡도는 O(100*100*100)으로 충분히 통과-> 각 병사의 '힘', '민첩', '지능' 스텟을 배열로 저장하고, 오름차순 정렬시켜서 비교하자 코드더보기import java.io.*;import java.u..

문제: https://www.acmicpc.net/problem/23882 조건TimeLimit = 1s배열크기 (5 교환횟수 (1 풀이선택정렬을 구현하자-> 정렬을 진행할 사이즈를 제한하고, 가장 큰 수가 뒤로가도록 구현한다-> 한번 교환이 일어나면 사이즈를 줄인다-> for (last = n-1; last >=0; last --) // 최댓값 관련 정보 max = arr.max(0~last사이) max_idx = arr.index(max) // 교환 if (max_idx != last) last_v = arr[last]; arr[last] = max; ..

문제: https://www.acmicpc.net/problem/16171 조건TimeLimit = 1s1 풀이S의 문자열을 하나씩 탐색하여, 숫자를 제외한 새로운 S를 만든다-> 이때 아스키 코드를 사용해보자이후 S.contains(K)로 결과를 확인한다 코드더보기import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { // input BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] s_char = br.readLine().toChar..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/5883 조건TimeLimit = 1s사람 수 (1용량 (0 풀이B의 한 종류씩 전부를 빼면서 완전탐색을 하면?-> 최악의 경우, 1000종류의 B와, 1000명의 사람을 탐색-> 따라서 O(1000*1000) = O(100만) 이므로 충분함어떻게 구현?-> 종류는 중복을 없애기 위해서 Set로 다룬다-> '연속 구간 사이즈'는, 사람들의 요구 바이트 배열(bites)에서 하나의 type씩 제외한다음, 연속되면 +1 해준다-> Before와 Current를 선언해서 사용하고, 조건에 따라서 '연속 구간 ..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/2304 조건TimeLimit = 2s11지붕의 어떤 부분에도 오목한 부분이 존재하면 안된다 풀이오목한 부분이 없으려면 다음 조건에 따라 지붕을 이어야 한다-> 가장 높은기둥을 '기준'으로 삼는다-> '기준'으로부터 다음 좌/우 기둥들은, '기준'보다 높이가 같거나 작아야 한다-> 이후 '기준'을 다음 좌/우 기둥들로 변경한다-> 가장 마지막 기둥에 도달할 때까지 위를 반복한다이때 가장 높은기둥이 여러 개라면?-> 높이가 동일한 가장 높은기둥들 중, 가장 끝에 위치한 두 기둥 사이의 면적을 더해준다-> ..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/2503 조건TimeLimit = 1sflow1. 영수가 숫자 생각2. 민혁이가 질문3. 질문에 대해 'n 스트라이크, m 볼' 로 대답4. 3 스트라이크 나올때까지 질문스트라이크 = 위치 & 숫자 모두 맞추는 경우, 볼 = 숫자는 맞지만 위치가 다른 경우1 풀이서로 다른 세자리수를 정렬시키는 방법의 수는 9P3 = 504가지-> 각 504개의 수에 대해, 모든 질문을 다 해봐도 N이 최대 100이므로 시간복잡도는 O(50400)-> 완탐 가능각 숫자에 대해 N개의 질문-> 하나라도 만족을 못한다면 co..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/1816 조건TimeLimit = 2s'매우 큰 소수' = 10**6보다 큰 소수S의 모든 소인수가 10**6보다 크면 적절하다110**12 풀이적절한지만 판단하면 됨 (몇 개가 나오는지가 아님)-> 즉, 각각의 S에 대해 '10**6보다 작은 소인수 여부'만 판단하면 되는 문제-> n이 최대 10이고, [1~10**6-1]중에 약수가 있는지 확인해야함-> 따라서 모든 S에 대해 [1~10**6-1]로 나누어보고, 나머지가 0이라면 'NO'를 출력-> n이 최대여도 O(10**7)로 충분히 만족 코드더..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/2563 조건TimeLimit = 1sn"색종이 왼쪽 아래 모서리의 x좌표 y좌표" 형태로 입력됨색종이가 도화지 밖으로 나가는 경우는 없음 풀이 (1)최대 n=100이므로, 색종이가 차지하는 모든 좌표(x,y)를 다 저장 후 count 해도 됨-> 색종이 크기가 10x10으로 고정이므로, 이중 for문을 사용해서 Set에 저장해서 중복을 제외하고 카운트하자-> (x,y)를 입력받았을 때 좌표 저장 for(r=x, r for(c=y, c set.add("x..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/15593 조건TimeLimit = 2s10 풀이 (1)최대 n=100이므로, lifeguard를 하나씩 차례대로 제외하고 계산한다면?-> 매번 99개 더하기(O(99)) * 100번반복(O(100)) = 9900-> 완탐가능-> 입력 저장해두고, 차례대로 제외하면서 모두 더해서 max time을 구해보자 코드(1)import java.io.*;import java.util.*;/* * Condition * - TimeLimit = 2s * - 1 매번 99개 더하기(O(99)) * 100번반복(O(..

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: https://www.acmicpc.net/problem/19532 조건-999(x,y)는 유일하다-999TimeLimit = 1s 풀이x와 y의 범위를 모두 탐색하면?-> 1999*1999 ~= 400만-> 1s안에 충분히 들 수 있다완탐으로 풀어보자 코드import java.io.*;import java.util.*;/* * Condition * - -999 1s안에 충분히 들 수 있다 * - 완탐으로 풀어보자 */public class Main { public static void main(String[] args) throws IOExceptio..