드롱드롱

https://www.acmicpc.net/problem/11663 1. 틀린 풀이 및 알아갈 점def binary_search(list1, target): left, right = 0, len(list1)-1 while left list1[mid]: left = mid+1 elif target == list1[mid]: return mid return rightn,m = map(int, input().split())list1 = list(map(int,input().split()))list1.sort()for _ in range(m): a,b=map(int, input().split()) n1 = binary_sea..

https://www.acmicpc.net/status?user_id=aiden1212&problem_id=13706&from_mine=1math 모듈에서 제공하는 sqrt()는 가볍게 시간초과 에러가 뜬다.따라서 이진탐색을 이용하여 문제를 풀어주면 된다. def binary_search(target): left, right = 0, 10**800-1 while left mid**2: left = mid+1 elif target

1. Search Algorithms이 글에서 Search, 즉 탐색을 하는 방법에 대한 알고리즘 2가지를 소개하고자 한다. 첫번째는 Linear search(선형 탐색)이고, 두번째는 Binary search(이진 탐색)이다.Linear Search는 처음부터 끝까지 하나씩 구먹구구식으로 탐색하는 것을 말하고, Binary search는 계속해서 반으로 쪼개서 탐색을 하는 방법을 말한다. 이렇게만 말해도 구현은 단순한 Linear Search가 쉽지만, 시스템이 복잡해질수록 구현하는 데에 있어서는 Linear Search보다는 복잡하지만 시간 복잡도는 확실히 Binary Search가 단축시켜줄 것만 같은 느낌이다.(느낌만 그런 것이 아니라 실제로도 그렇다.) 1-1. Linear search Algo..

서론이제 공부하고 있는 자료구조/알고리즘 주제로 슬슬 백준 문제풀이를 해볼 시간이 왔다!! 1. 10815: 숫자카드https://www.acmicpc.net/problem/10815코드 및 문제풀이def binary_search(some_list,target): left, right = 0, len(some_list)-1 while left some_list[mid]: left = mid+1 return Nonen = int(input())list1 = list(map(int, input().split()))list1.sort()m = int(input())list2 = list(map(int, input().split()))list3 = ['0']*mfor ..

서론본격적으로 코딩을 공부하기 시작하면서 자료구조/알고리즘에 대해 깊이 있게 공부해 볼 시간을 언젠가 가져야 함을 알고 있었다. 이제 백준과 solved.ac를 통해서 파이썬에 대해서 다룰 수 있을 정도가 되었다. 문제를 풀면서 자료구조와 알고리즘에 대해 공부해야만 풀 수 있는 문제들을 맞닥뜨리게 되면서 이왕 이렇게 된 거 차근차근 블로그에 하나씩 글을 올려보자고 생각이 들었고, 9월 1일 기분 좋게 한 달을 시작하는 날에 시작하게 됐다!주절주절 말이 길었는데 그리하여 자료구조/알고리즘의 시작은 바로 뜬금없이 python에서의 객체이다. 이 블로그는 cdragon님의 블로그를 중심적으로 차근차근 따라가며 공부한 것입니다.https://cdragon.tistory.com/category/CS%20%EC%A..

그래프 알고리즘을 공부하던 도중 블로그 설명 중간에 있던 deep copy와 shallow copy의 보다 명확한 이해를 위해 글을 작성한다. copy에 대해 이해하기 전에 그보다 더 기본 배경이 되는 mutable과 immutable에 대해 이해한 후 copy를 이해해보자.  1. mutable과 immutable 객체일단 파이썬은 객체 지향형 프로그래밍이니 뭐니 객체에 대해 너무 많이 이야기를 들었는데 이 공부를 하기 전까지 객체에 대해 너무 두루뭉실하게 알고 있었다.객체란 3가지 요소로 구성된다. 주소(id), 데이터형(type), 값(value) mutable은 값이 변할 수 있는, immutable은 반대로 값이 변할 수 없다는 의미를 가지고 있다.mutable에는 list,dict,set이 있..

https://www.acmicpc.net/problem/10871 간단한 문제이다.그러나 이 문제에서 평소 자주 쓰지만 맨날 구글링해서 가져오는 기능을 확실히 내 것으로 만들기 위해 포스팅한다. n,x= map(int,input().split())list1 = list(map(int,input().split()))for i in list1[:]: if i >= x: list1.remove(i)print(*list1)  1. 리스트에서 요소 제거리스트에서 요소를 제거하는 방법에서는 크게 2가지가 있다.리스트 요소를 직접 참조하여 제거하는 것과 리스트 인덱스를 이용해서 제거하는 것이 그것이다. 1-1. 리스트 요소를 직접 참조하여 제거리스트 요소를 직접 참조하여 제거하는 함수는 'del'..

https://www.acmicpc.net/problem/1463 1463번은 결과값 자체를 도출하는 것은 어렵지 않으나 시간 제한이 걸려있어 알고리즘 지식을 동반해 푸는 것이 핵심인 문제이다.이 문제를 가져온 이유는 가장 최근에 공부한 Dynamic programming이 사용되는 문제이기 때문디ㅏ. 동적 계획법은 상향식과 하향식이 있는데, 상향식은 제일 작은 인덱스의 수부터 목표하는 값으로 향하는 것이고 반대로 하향식은 맨위의 값에서 재귀로 제일 작은 인덱스를 향하는 것이다. 동적 계획법은 장점 중 메모리 공간을 활용하여 시간 복잡도를 줄일 수 있다는 것을 활용해서 문제에 접근하면 된다.이를 메모이제이션 방법이라고 한다. (값을 기억해서 문제를 푼다고 이해해두자.) 메모이제이션 방법으로 문제를 풀 때..

1. DP란 무엇인가DP는 Dynamic Programming의 약자로 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.이러한 점에서 분할정복 알고리즘과 비슷하지만 분명한 차이점은 DP에서는 작은 문제들이 반복되며, 그것을 이용해 풀어나간다는 점이다.+) 동적 계획법은 소문제가 종속적이고, 분할 정복은 소문제가 독립적이다.  1. 처음 진행되는 연산은 기록2. 이미 진행되었던 연산이라면 다시 연산하지 않고 기록되어 있는 값을 호출한다.3. 시간과 자원 절약 가능하다. 즉, 시간복잡도와 공간복잡도를 낮춰준다. 2. DP를 사용할 수 있는 상황1. 큰 문제를 작은 문제로 분할 가능2. 작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일 *** 최적성의 원리를 만족하는지 판단해야 ..

https://www.acmicpc.net/problem/17219 n, m = map(int, input().split())list_dict = {}for _ in range(n): a, b = input().split() list_dict[a] = blist1 = []for _ in range(m): word = input() print(list_dict[word])  딕셔너리를 이용하는 간단한 문제였다. 그러나 이 글을 쓰는 이유는 전에는 코드도 훨씬 길게 쓰고 딕셔너리에 대한 활용이 미숙했다면, 지금은 그것보다 조금 더 나아졌다는 것에 뿌듯함을 느꼈기 때문이다.