티스토리

서린이의 기술 블로그

검색하기

블로그 홈

서린이의 기술 블로그

nekara.tistory.com/m

서린이의 기술 블로그

구독자: 0

방명록 방문하기

주요 글 목록

시간 복잡도와 공간 복잡도 시간 복잡도시간 복잡도란?반에 있는 사람들이 N명이라고 한다면B 방식은 N^2 만큼의 연산이 필요하다고 할게요.💡 시간복잡도는 입력값과 문제를 해결하는 데 걸리는 시간과의 상관관계를 말합니다!입력값이 2배로 늘어났을 때 문제를 해결하는 데 걸리는 시간은 몇 배로 늘어나는지를 보는 것이죠.우리는 시간이 적게 걸리는 알고리즘을 좋아하니 입력값이 늘어나도 걸리는 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘이겠죠?N 이 예를 들어서 30이라면 A 방식은 30번, B 방식은 900 번의 연산이 필요하겠죠A 방식은 N 번 만큼의 연산이 필요하고예를 들어서 내가 반에 있는 사람들 중에서 가장 이성에게 호감이 높은 사람을 뽑는다고 해볼게요.“입력값에 비해 얼마나 일을 수행해야 하는가?”1) 최댓값 찾기 알고리즘의 시.. 공감수 1 댓글수 0 2025. 2. 3.
알고리즘과 친해지기 (2) 컴퓨터는 숫자밖에 저장하지 못하기에, ASCII 코드 개념이 등장ASCII (American Standard Code for Information Interchange) : 7비트를 사용하고, 암호화되지 않은 키로코드를 사용 문자 : ASCII 코드 예시A : 65, a : 97 문자('a')-> ASCII 코드로 변환print(ord('a'))ASCII 코드(97) -> 문자로 변환def find_alphabet_occurrence_array(string): alphabet_occurrence_array = [0] * 26 for char in string: if not char.isalpha(): continue arr_index = char - ord('a.. 공감수 1 댓글수 0 2025. 2. 2.
알고리즘과 친해지기 (1) # 알고리즘과 친해지기# 1. 최대값 찾기array = [3,5,6,1,10,4]max = 0def find_max_num(array): for num in array: for compare_number in array: if num max: max = num return maxprint(f'최대값은 {find_max_num2(array)}입니다.')# 위 알고리즘은 시간복잡도가 O(n)# 알고리즘 문제풀이의 목표 중 하나는# 같은 문제라도 시간복잡도가 더 작은 알고리즘을 찾아야한다. 출처 : 38군데 합격 비법, 2024 코딩테스트 필수 알고리즘 공감수 1 댓글수 1 2025. 2. 2.
완탐과 원복 1. 완탐과 원복첫번째 최종 탐색 후, 계속 원복을 하면서 탐색 가능한 모든 경우의 수를 구한다. 2. 인접 노드3. 탐색 순서 : 0 -> 1 -> 2 (첫번째 탐색 끝) > 2번을 pop() 및 방문 미처리하여 원복 : 0 -> 1 > 1번으로 가서 인접노드 3을 방문 : 0 -> 1 -> 3 > 3번을 pop() 및 방문 미처리하여 원복 : 0 -> 1 > 2와 3을 모두 탐색했으니 1도 pop() 및 방문 미처리하여 원복 : 0 4. 소스 코드# 완전탐색# 완탐과 원복# 원복의 필요성 : 상태값이 그 다음 경우의 수에 반영되지 않도록 하기 위함# 1. 인접 노드 방향 벡터# 0 1 2# 3# 2. 3개의 정점을 탐색하면 print3 하라!# 3. 방문한 정점은 다시 방문.. 공감수 10 댓글수 5 2024. 9. 14.
완전탐색(재귀함수)과 백트래킹 1. 재귀를 활용한 완전탐색 문제 2개 # 재귀를 활용한 완전탐색# 승철이는 도쿄 위의 빨간 구름위에 올라있다. 이 구름은 그대로 내버려 두면 땅으로# 떨어져 100만명의 사상자가 발생한다. 구름을 멈추는 방법은 구름의 특정 위치에 요석을# 꽂으면 된다. 해당 위치에는 숫자가 표기가 되어있고, 몇 개를 골라 숫자의 합이 "소수"가# 될 때 구름은 멈춘다. 총 몇개의 경우의 수가 있는지 말하라.# N개의 요석 후보의 숫자와 다음 줄에 해당 숫자들이 나온다. N # 입력# 10# 24 35 38 40 49 59 60 67 83 98# 소수 : 1과 자기 자신 외에 다른 약수를 가지지 않는 수입니다.# 2, 3, 5, 7, 11, 13, 17, 19 ..import sysinput = sys.stdin.rea.. 공감수 1 댓글수 0 2024. 9. 8.
완전 탐색 - for or while loop 1. 완전 탐색 : 순열, 조합 등을 포함하여 모든 경우의 수를 고려하는 방법 - 1억 미만 : 완전 탐색 - 1억 이상 : 완전 탐색이 가능 or 불가능 2. 반복문을 활용한 완전 탐색 - 문제 랄로의 수BJ랄로는 2400이라는 숫자를 좋아한다. 그래서 2400이 포함된 숫자를 보면 "랄로!"를 외치기에, 2400이 포함 된 수를 랄로의 수라고 한다. 첫번 째 랄로의 수는 2400이고, 두번 째 랄로의 수는 12400이며, 세번 째 랄로의 수는 22400이다.이때, N번 째, 랄로의 수는 몇인가? # 입력# 200 # 출력# 492400 - for loop 풀이import sysinput = sys.stdin.readlineINF = 1000000cnt = 0n = int(input())for.. 공감수 2 댓글수 0 2024. 9. 4.
2480 - 주사위 세개 https://www.acmicpc.net/problem/2480 1. 메인 아이디어 - 조건 그대로 조건문 로직을 만든다. - dictionary를 활용하여 max_number, max_count로도 문제풀이가 가능하다 - 단순 구현법import sysinput = sys.stdin.readlinea, b, c = map(int, input().split())if a == b == c: print(10000 + a * 1000)elif (a == b != c) or (b == c != a): print(1000 + b * 100)elif a == c != b: print(1000 + a * 100)else: print(max(a,b,c) * 100) - 딕셔너리를 이용한 방법i.. 공감수 2 댓글수 0 2024. 8. 31.
2525 - 오븐시계 1. 메인 아이디어 - m을 60으로 나눈 몫을 시간에 더함 - t에 다시 t를 24로 나눈 나머지로 대입 (24시간 형식 맞추도록) - m을 60으로 나눈 나머지가 분 import sysinput = sys.stdin.readlinet, m = map(int, input().split())m2 = int(input())m += m2t += m // 60t %= 24m %= 60print(t, m) 공감수 2 댓글수 0 2024. 8. 31.
2870 - 수학숙제 https://www.acmicpc.net/problem/2870 1. 메인 아이디어 - prev를 도입하여 이전 숫자/단어가 알파벳인지 아닌지 검증한다. - 알파벳이 아닐 경우 무조건 str += w로 담고본다. - 알파벳 -> 숫자가 나오는 시점에는 str += w를 더한다. - 숫자 -> 알파벳이 나오는 시점에는 digits 리스트에 str을 int형으로 담고, str을 ''로 초기화한다. > digits 리스트에 str을 담을 때, str이 애초에 ''이 아닌지도 검증이 필요하다 (if str != '' and str_lstrip != '':) > str 검증을 하지않으면 '' 빈 공백이 digits에 담기기 때문임 - digits 리스트의 오름차순으로 정렬한 후, print한.. 공감수 2 댓글수 0 2024. 8. 25.
2910 - 빈도 정렬 https://www.acmicpc.net/problem/2910 1. 메인 아이디어 - 각 원소에 대해 [빈도, 순번]을 정렬할 자료구조를 생각한다 -> dictionary가 적합 - dictionary를 key=lambda(=익명함수)를 기준으로 정렬한다 > -x[1][0] = 각 원소의 빈도를 우선으로 내림차순 > x[1][1] = 각 원소의 순번을 그 다음으로 오름차순 - result에 정렬된 dictionary를 원소 * 빈도로 extend한다 ( dictionary 내부 원소는 list 이므로 extend 써야함) > result = [], extend ([2,3], [1,2] ..) => result = [2, 2, 2, 1, 1] 2. 소스 코드# 백준 2910 빈도 .. 공감수 1 댓글수 0 2024. 8. 24.
2828 - 사과 담기 게임 https://www.acmicpc.net/problem/2828 1. 메인 아이디어- l(=left)와 r(=right)를 고려한다. (left는 바구니 왼쪽, right는 바구니 오른쪽)- 바구니의 길이가 1이기 때문에 시작 l = 1, r = 1 이다 ( r = 2 가아님, 2가되면 바구니의 길이가 2임)- l을 통하여 r을 정의하면, r = l + m - 1- 바구니가 사과보다 왼쪽, 오른쪽에 있을 때를 고려한다. 2. 소스코드import sysinput = sys.stdin.readline# 5 1# 3# 1# 5# 3# 1 2 3 4 5# | | | | | |# | | | | | |# | | | .. 공감수 2 댓글수 1 2024. 8. 23.
1992 - 쿼드트리 https://www.acmicpc.net/problem/19921. 풀이 알고리즘 : DFS(선택), BFS, 분할정복 2. 핵심 아이디어 2-1. 입력값 하나하나를 행렬에 원소로 담기 2-2. (0,0)과 size로부터 시작 2-3. 한번에 4개씩 재귀적으로 호출하며, 각각 재귀는 왼쪽위, 오른쪽위, 왼쪽아래, 오른쪽아래와 size / 2를 계속 매개변수로 담아서, size가 1이 될 때까지 계속 호출한다. 2-4. 문제 조건에 따라서 ret에 계속 String을 담아서 값을 만들어 호출한다. 3. 분할정복 알고리즘의 순차적 흐름 예시# divide and conqur# 분할 정복 # n * n 영역의 Matrix를 2 -> 1 -> 3 -> 4 분면 순서(Z 형태로)로 재귀적으로 호출.. 공감수 1 댓글수 0 2024. 8. 22.
2583 - 영역 구하기 출처 : https://www.acmicpc.net/problem/2583 import syssys.setrecursionlimit(100000)input = sys.stdin.readlinem, n, k = map(int, input().split())a = [list(map(int, input().split())) for _ in range(k)]dx = [0, 1, 0, -1]dy = [1, 0, -1, 0]visited = [[0] * m for _ in range(n)]for i in range(k): s = a[i] for i in range(n): for j in range(m): if s[0] = n or ny >= m: c.. 공감수 2 댓글수 0 2024. 8. 22.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.