본문 바로가기

전체 글

(31)
[자료구조] 시간복잡도 Time Complexity (1) 시간복잡도 Time Complexity 프로그램의 연산 시간과 입력의 함수 관계를 의미하며, 특정 알고리즘 로직의 수행시간을 시간복잡도라고 할 수 있습니다. 일반적으로 시간복잡도는 빅오 표기법으로 표현합니다. 우리는 시간복잡도를 기준으로 알고리즘을 평가할 수도 있고, 이를 통해서 로직을 개선하고 알고리즘을 최적화할 수도 있습니다. 속도는 SW 성능을 평가하는 중요한 지표이니, 시간복잡도가 중요하게 여겨질 수 밖에 없겠죠? (2) 빅오 표기법 Big-O Notation 빅오 표기법은 input "N"으로 입력을 표현할 때, 해당 로직을 함수로 나타낸 낸 수식입니다. 이때 최고차항만 표기하고 상수항은 생략하여 표기합니다. 그렇기 때문에 입력값 N에 대한 개략적인 수행시간만 알 수 있고, 정확한 시간을..
[Simulation] 교차로-소프티어(별3) 문제 제목 : 교차로 문제 출처 : 소프티어 알고리즘 : simulation 문제원본링크 https://softeer.ai/practice/info.do?idx=1&eid=803 Softeer 자율주행차가 아래와 같은 교차로를 통과하는 상황을 생각하여 보자. 이 문제에서 다루는 교차로에서는 직진만 가능하기 때문에, 아래 그림과 같은 네 가지 방법으로만 교차로 softeer.ai import sys; reader = sys.stdin.readline from collections import defaultdict,deque from sys import setrecursionlimit setrecursionlimit(5000) INF = int(2e9) aord = ord('A'); tonum = defau..
[Brute Force] 카펫-프로그래머스(Lv.2) 문제 제목 : 카펫 문제 출처 : 프로그래머스 알고리즘 : Brute Force https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(brown, yellow): answer = [0,0]; hoobo = [] for i in range(1, brown+yellow): if (brown+yellow)//i < i: break if (brown+yellow)%i == 0: hoobo.append(((brown+yellow)//i..
[Brute Force] 소수 찾기-프로그래머스(Lv.2) 문제 제목 : 소수 찾기 문제 출처 : 프로그래머스 알고리즘 : Brute Force https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from itertools import permutations def makePrime(n): prime=[0,0]+[1]*~-n for i in range(int(n**.5)+1): if prime[i]:prime[i*i::i]=[0]*(n//i-i+1) return prime def solution(numbe..
[Brute Force] 모의고사-programmers(Lv.1) 문제 제목 : 모의고사 문제 출처 : 프로그래머스 알고리즘 : Brute Force https://school.programmers.co.kr/learn/courses/30/lessons/42840 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(answers): ans = []; le = len(answers); trr = [5,0,1,0,3,0,4]; score = [0]*3; thrr = [3,3,1,1,2,2,4,4,5,5] for i in range(1,le+1): one = 5 if i%5 == 0 else i%5 two ..
[python] 비트마스킹 ***비트마스킹 : 정수로 표현된 2진수 숫자 자체를 자료구조로서 활용하는 것 일반적인 코딩테스트 문제에서, 경우의 수 30-31 가지 이상의 상황에서는 비트마스킹을 활용하기 어렵습니다. 시간복잡도의 문제로 시간초과가 나기 쉽기 때문입니다. ( 2^30 = 1,073,741,824 ) 그럼에도 불구하고 비트연산을 활용하면 다른 자료구조를 사용했을 때보다 획기적으로 연산 시간을 줄 일 수 있을 때가 많습니다. 또한 펜윅트리에서 비트마스킹은 매우 유용합니다. 1. 비트 연산자 AND & ( 1 & 1 == 1 ) OR | ( 1 | 0 == 1 ) ( 1 | 1 == 1 ) XOR ^ ( 1 ^ 0 == 1 ) ( 1 ^ 1 == 0 ) NOT ~ ( ~1010 == 0101 ) [SHIFT] 1 1 2 >..
[cpp] 비트마스킹 옛날에 비트마스킹을 공부할 때 정리했던 노트입니다. "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"(도서, 구종만 저)과 백준의 "집합" 문제를 참고하여 작성했던 자료입니다. 중요한 자료는 아니지만 혹시 필요하신 분이 계실 까봐 업로드해두었습니다.