동환아 공부해야지

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

1. 첫 번째 풀이(fail): 백트래킹'''이건 백트래킹으로 풀면 될 듯!더 이상 움직일 있는 칸이 없다면 끝인걸로'''def move(i,cr,cc): if i == 0: nr,nc = cr-2, cc+1 elif i == 1: nr,nc = cr-1, cc+2 elif i == 2: nr,nc = cr+1, cc+2 else: nr,nc = cr+2, cc+1 return nr,ncdef dfs(cr,cc,cnt,visited,used): global maxCnt # 탐색 for i in range(4): nr,nc = move(i,cr,cc) if not(0 4: fo..

'''- 부등호를 만족하는 최대, 최소를 출력- 사용되는 숫자는 유니크해야함- 백트래킹으로하자'''def compare(before, cur, sign): return beforecurdef dfs(depth, s): global max_v, min_v, visited # 제일 처음 depth가 k+1이 되었을 때 -> 0부터 오름차순이므로 min이 됨 # 제일 마지막으로 depth가 k+1이 되었을 때 -> max가 됨 if depth == k+1: if len(min_v) == 0: min_v = s else: max_v = s return # 0부터 오름차순으로 탐색 for i in r..