본문 바로가기

알고리즘

시간복잡도에 대해서 알고가자 크흐흡 문명주의 자료를 이제야 다시보네 고마워요 명주맨 코테를 급하게 준비하며 명주글을 다시본다 흐흐흑 힘들어 코테 없어졌으면 좋겠다. https://medium.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80-%EB%AF%B8%EC%B9%9C%EC%A7%93%EC%9D%B4%EB%8B%A4/2-%EC%8B%9C%EA%B3%B5%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84%EC%99%80-%EC%9E%85%EC%B6%9C%EB%A0%A5-1df25ebaeede _2_ 시공간복잡도와 알고리즘 문제풀이에서의 시공간복잡도를 알아봅시다. medium.com 내가 보는 자료여서 내가 필요한 것들만 정리하고 넘어가려고 한다 -> 요약요약 1. 시간복잡도는 Big.. 더보기
백트래킹 개념정리 백트래킹 결론적으로 간단히 이야기하자면 트리 형태로 검색을 해나가며 만약 제약 조건을 통과하지 못한경우 그상태에서 탐색을 종료하고 부모 노드로 돌아가서 다시 다른 자식을 검사하는것이다 -> 크리티컬 맞으면 다검사하겠지만 당연히 종료하고 돌아오는게 있을테니 완전 탐색보다 빠름 Backtracking = Back (뒤) + Tracking (추적) 되추적, 퇴각 검색이라 불림 모든 경우의 수를 탐색하되, 문제가 요구하는 어떠한 제약 조건을 만족하지 않는 경우는 더이상 탐색하지 않고 종료하는 것 결론적으로 현재것을 까보는데 유망성(조건검사)를 검사후, 조건을 만족하지 못하면 부모노드로 돌아가 다른 자식노드를 검사하는것이다. 시간복잡도 -> 일반적으로 상태 공간 트리의 노드수에 비례한다. 그냥 트리가 쭉있다면 .. 더보기
브루트포스 개념정리 Brute Force 브루트포스가 무엇인가? -> 직역하면 짐승같은힘이다 멧돼지 블로그와 잘맞는 알고리즘 인거같다 직역한 그대로 짐승같이 컴퓨팅 파워로 조져서 해결하는것이다. 문제를 해결하기 위해 가능한 모든 경우의수와 그 경우의 결과를 구하는것이다 브루트 포스 알고리즘으로 문제를 푼다면 무조건 정답이 나온다 -> 당연하다 다 구해보니까 ㅋㅋㅋㅋ 한마디로 노가다 이다 ex) 6자리의 암호를 구해보자! 하나씩 죄다 넣어서 어렸을때 자물쇠 풀듯이 푼다 6! 가지수 한마디로 그냥 경우의수 다 가져다 넣어보는것이다 1~50까지 더하기 예시 //1부터 50까지 더한 값 구하기 - Bruteforce sum = 0 for i in range(1, 51): sum += i 🤔 근데 그럼 모든문제를 브루트포스로 풀면되.. 더보기
파이썬 기본 문법 정리 if 문 money = 1000 if money >= 3000: print("돈없다") elif money range(10):0,1,2,3,4,5,6,7,8,9 빠른 입력 input 은 느리다 -> sys 라이브러리의 readline()함수를 써야한다. sys 쓸떄는 한줄 입력받고 rstrip함수를 호출해야한다 -> readline() 으로 입력받고나면 엔터가 줄바꿈기호로 입력된다 이거 없애려고 rstrip 함수 호출해주는거다. import sys //정수하나 입력 a = int(sys.stdin.readline().rstrip()) //map 으로 여러개 int 처리해서 한번에 받기 a,b,c = map(int, sys.stdin.readline().rstrip().split()) //리스트로 담기 l.. 더보기
나중에 다시볼 알고리즘 백준 11653 소인수분해 간단한 소인수 분해이지만 나에게는 익숙지 않아서 나중에 보려고 적어놓는다. 문제:https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 소인수 분해에 대해서 쭉 생각해봤는데 소수를 쭉 구해놓고 그것들을 나눠지는 순서대로 대입해서 구하는 방법을 생각해봤는데 소수들이 무한이 많아 아주 크기가 큰 소수가 들어있는 테스트 케이스를 성공 못할거라 생각해서 한번더 생각해본결과 2부터 나누기 시작해서 안될경우 1씩 증가하면서 나누고 조건이 나누려는수가 1이 아니면 멈추는 방법을 택하면 4나 이런 소수가 아닌것들로 나눠지는것은 어짜피 앞전에서 2나 작은 소수로 나눠지는 경우의 수로 걸.. 더보기

티스토리툴바