Let's get "IT"

what? 이진탐색이란 시작점, 중간점, 끝점 3개의 지점을 기준으로 탐색하는 것을 의미하고 중간점과 target(찾으려는 값)을 비교하며 탐색을 진행한다. why? 탐색범위가 크거나 정렬이 된 배열속에서 특정 값을 빠르게 찾기 위해서 사용한다. how? 시작점, 중간점, 끝점 3개를 설정하고 배열이 정렬되어있다는 가정하에 중간점과 target을 비교하며 탐색을 시작한다. 이때, target이 중간점의 원소보다 작다면 끝점은 중간점의 이전값이 되고 / 중간점의 원소보다 크다면 시작점이 중간점의 다음값이 된다. 이때, target이 중간점의 원소가 같을 때 target이 있던 위치는 중간점을 담은 변수의 값이 되고 탐색을 중단한다. 1. 재귀를 활용 2. while()문을 활용 = 반복문 활용 1. 재귀를..

what? sys의 sys.stdin.readline() 공백을 기준으로 입력 받을 때 => sys.stdin.readline().split() 문자열을 기준으로 입력 받을 때 => sys.stdin.readline().rstrip() why? 데이터가 많거나 탐색 범위가 매우 넓은 이진 탐색과 같은 문제에서는 입력 데이터의 개수가 많아서 input() 함수를 사용하면 동작 속도가 느려 시간초과로 오답이 될 수 있기때문에 사용한다. How? 1. input = sys.stdin.realine으로 input을 정의후, input().rstrip()혹은 input().split()처럼 사용할 수 있다. 2. sys.stdin.readline().rstrip() 혹은 sys.stdin.readline().sp..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 수 정렬하기 3에서 제공하는 최대의 값이 10000이기때문에 계수 정렬을 사용하여 문제를 풀기로 하자. 계수정렬이란 입력받은 숫자중 가장 큰 값을 배열의 크기로 설정하고 입력받은 값을 배열의 index로 하여 해당 index에 숫자가 들어올때마다 +1을 넣어주고 0이 아닌 값들을 출력하는 정렬방법이다. 1. 메모리초과가 났던 코드 import sys input = sys.stdin.readline n=int(inp..

1. 경쟁적 전염 => bfs 사용문제[8/6] 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 오답이유 1. 틀렸습니다 : 1-k까지의 바이러스의 종류가 있고 바이러스 개수는 k개로 정해진 것이 아닌데 한종류의 바이러스가 1번만 들어왔을때 체크하도록 코드를 작성하였음 => 다른 부분에서 error가 나는 줄 알고 계속 시도했다가 틀렸었고, 해당 이유를 찾을 수 있었던 testcase를 아래코드 밑에 넣어둠. 2. 출력초과 : list를 print해본 코드를 주석 혹은 삭제처리 하..

정렬의 종류 선택정렬 특정 리스트에서 가장 작은 데이터를 선택해서 앞으로 보내면서 정렬해주는 방법으로 시간이 오래걸림 삽입정렬 데이터를 확인하며 각 데이터를 적절한 위치에 삽입하는 정렬로 특정 숫자의 왼쪽 부분들은 이미 정렬된 것으로 가정함. 특정숫자의 왼쪽부터 처음에 위치한 배열의 숫자까지 for문을 돌리며 앞의 숫자가 더 작다면 그 뒤에 특정숫자를 삽입해줌. 퀵 정렬 = 피벗정렬 pivot을 기준으로 pivot보다 작은 숫자들을 왼쪽으로 큰 숫자들을 기준점 오른쪽으로 옮기며 이 과정을 반복하다보면 정렬됨 계수정렬 가장 큰 숫자와 가장 작은 숫자의 차이+1개 만큼의 배열을 선언하고 배열의 원소 번호와 같은 숫자일 경우 +1을 끝까지 해줘서 각 원소에 저장된 숫자만큼 원소번호를 출력하는 것을 끝까지 해주..

문제 1. 특정거리의 도시찾기 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 메모리초과 => 코드를 작성할때 이차원 list의 크기를 n+1*n+1로 하였기 때문에 메모리초과가 나게 됨. from collections import deque import sys input = sys.stdin.readline n, m, k, x = map(int, input().split()) map_list = [] for i in range(0,..

1. 볼링공 고르기 [2019 SW 마에스트로 입학 테스트] #볼링공 고르기 => 두사람이 무게가 다른 볼링공을 고르는 경우의 수를 출력하는 문제 n,m = map(int,input().split()) #n개의 공이 m까지의 숫자로 구성됨 w = list(map(int,input().split())) count=0 for i in range(0,n-1): for j in range(i+1,n): if w[i]!=w[j]: count+=1 print(count) 2. 무지의 먹방 라이브[2019 카카오 신입 공채] #무지의 먹방 라이브 eat = list(map(int,input().split())) k = int(input()) time =0 i=0 cnt=0 while True: if time==k: ..

#모험가 길드 => 공포도가 x인 모험가는 반드시 명 이상으로 구성한 모험가 그룹에 참여해야함. 최대 몇개의 모험가 그룹? //28 ''' n = int(input()) num = list(map(int, input().split())) #print(num) num.sort(reverse = True) list2= [] for i in range(0,n): cnt=0 while i

1.럭키 스트레이트 =>반으로 나누어 동일한 합을 가지면 LUCKY 출력 n = input() m = len(n)//2 sum=0 sum2=0 for i in range(0,m): sum += int(n[i]) for i in range(m,len(n)): sum2 += int(n[i]) if sum==sum2: print("LUCKY") else: print("READY") 2. 문자열 재정렬 => 알파벳은 정렬하고 숫자는 숫자끼리 합쳐서 가장 마지막에 넣기 s = input() s2=[] sum=0 for i in range(0,len(s)): if s[i]>='A' and s[i] 문제 사이트 def solution(s): answer = 0 len_list=[] max_len = len(s)//2..

(1) 깊이 우선 탐색 DFS dfs : 깊이우선 탐색으로 넓게 퍼지며 탐색하는 것이 아니라 가장 깊은 곳까지 우선 탐색 후 넓게 퍼져가며 탐색하는 방법. => 깊이를 우선으로 먼저 탐색하고 탐색이 끝난 후에는 탐색을 시작한 위치로 돌아와 넓게 퍼지며 또 다른 노드에서 깊은 곳까지 탐색하는 방법. => 따라서, 중요한 것은 탐색한 지점을 기억해놔야한다는 점이고 이를 위해 재귀를 적절히 사용할 예정이다. => 익숙해지면 반복문을 통한 방법보다 재귀를 사용해 stack을 구현하는 것이 편리. (2) 너비 우선 탐색 BFS bfs : 너비 우선 탐색으로 넓게 퍼지며 현 위치 노드에 연결된 모든 노드를 우선으로 탐색하고 그 다음으로 한번 깊이를 들어가주며 그 노드의 연결된 모든 노드를 우선으로 탐색하는 방법 =..