동환아 공부해야지

(*뇌 빼기 연습 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자) 문제: 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..

(*뇌 빼기 프로젝트 -> 당신이 머리 쓰는 것보다, 컴퓨터가 몸으로 차력쑈 하는 게 성능이 더 좋다. 컴퓨터를 사용하는 법을 먼저 익히자)문제: https://www.acmicpc.net/problem/1145 조건TimeLimit = 2sn = 5각 수는 100이하의 서로 다른 자연수 풀이자연수가 5개밖에 없으니까, 모든 조합(5C3)을 구한 다음 최소공배수를 구해도 가능하겠다-> nCr 어떻게 구현?-> 아! 재귀로 구현해보자 ...더 간단하게 가능?-> 재귀는 무슨, 그냥 3중 for문 돌려버려도 되지 않나?-> 최소공배수를 구하려면 이건 불가능더 간단하게 가능??-> 생각해 보면 가능한 최댓값이 98*99*100(대략100만)임-> 이 말은, 1부터 대략 100만까지 전부 다 탐색해도 O(1..

1. 첫 번째 풀이(success): HashMap 사용import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.HashMap;import java.util.Map;/** * condition * - 성의 첫 글자가 같은 선수 5명을 선발 * * answer * - 가능한 성의 첫 글자를 사전순으로 공백없이 출력 * - 5명보다 적다면 PREDAJA 출력 * * approach * - HashMap 사용 * - 입력받은 이름의 첫 번째 값의 value 증가 * - 모든 입력이 끝난 후 cnt가 5 이상인 값들을 sb에 추가 후 출..

1. 첫 번째 풀이(success): 슬라이딩 윈도우(아님ㅋㅋ;)'''슬라이딩 윈도우로 한번 탐색 때리면 될듯!- 가장 첫 번째 지점부터 탐색하기 위해 물 세는 곳을 정렬- end = stt + l, (lst[-1]+0.5 in visited == True) 가 될 때까지 탐색- 방문할 곳이 연속적이라는 보장이 없으므로 visited는 set으로 처리- (다음 누수지점-0.5, 다음 누수지점, 다음 누수지점+0.5)를 분기처리해서 탐색'''# 입력def input_data(): n,l = map(int,input().split()) lst = list(map(int,input().split())) return n,l,lst# maindef solution(n:int, l:int ,lst:..

1. 첫 번째 풀이(success): DFS'''Condition- A-B-C-D-E 가 되는 node가 있는가?Answer- 존재하면 1, 없으면 0 출력Approach- 모든 node를 root삼아 한번씩 dfs 돌려보면 될 것 같음 - 이때 depth가 5가 된다면 끝'''from sys import stdininput = stdin.readline# 입력n,m = map(int,input().split())graph = [[] for _ in range(n)]for _ in range(m): a,b = map(int,input().split()) graph[a].append(b) graph[b].append(a)# dfsvisited = [False] * ndef dfs(no..

1. 첫 번째 풀이(success): 백트래킹'''Condition- n개중 m개 고름- 중복해서 뽑을 수 있음- 오름차순Answer- 중복값 출력x>>>> 백트래킹으로 풀자'''def dfs(cnt, seq:list, before, lst:list): global visited, answer # 조건 확인 if cnt == m and tuple(seq) not in visited: answer.append(seq[:]) visited.add(tuple(seq)) return # 탐색 for i in range(before, n): num = lst[i] seq.append(num) dfs(cnt+1, ..