본문 바로가기

스터디IT🌼41

[ 다이나믹 프로그래밍 = 동적계획법 ] 알고리즘 내용 정리 😃 동적계획법 ( Dynamic Programming ) - 전체 문제를 작은 부분 문제로 나누어 푸는 방법 - 한 번 계산한 결과를 재활용하는 알고리즘 ( 중복되는 부분을 한번만 계산하도록 ) 😃 동적 계획법 조건 1. 최적 부분 구조 : 부분 문제의 최적을 이용해 지존의 답을 구하는 구조! 더보기 2. 중복되는 부분 문제 더보기 😃 동적 문제 방식 1. Memoization - 하향식 - 중복되는 계산을 한번한 뒤 메모해두는 방식 - cache에 저장하고 보통 재귀함수 사용 - 배열 값을 -1로 모두 초기화, 배열 값이 음수이면 계산한 후 저장, 양수이면 그대로 활용 2. Tabulation - 상향식 - 반복문 기반으로 해결하는 방식 ( 누적시켜 전체 큰 문제를 해결 ) 😃 동적 계획법 문제 접근방.. 2023. 1. 12.
[ 완전탐색 ] 알고리즘 내용 정리 ✅ 완전탐색 - 모든 경우의 수를 다 고려해야 하는 경우를 의미 - 시간복잡도가 큰 편! ✅ 완전탐색 문제 판별법 1. 하나의 경우마다 따져야 할 게 명확한 경우 2. 어떤 상태를 구성하고, 그 상태가 특정 조건을 만족하는지 검토해야 하는 등의 문제 3. 나올 수 있는 경우의 수가 모두 탐색할 수 있을 만큼 크기가 적을 때 ✅ 완전 탐색 문제 접근 방식 1. 모든 경우를 생성할 수 있는 방법을 생각 2. 각각의 경우에 대해 그 문제의 조건을 만족하는지 체크 ( 문제에 따라 다름 ) ✅ 완전탐색 방법 1. BruteForce : 반복문과 조건문을 이용하여 처음부터 끝까지 탐색하는 방법 2. 비트마스크 3. 순열 : 순열 시간 복잡도는 O(n!) 4. 재귀를 호출 -> 백트래킹 5. DFS / BFS ✅ 고.. 2023. 1. 12.
[ SpringBoot ] 스프링 핵심 원리 기본편_핵심원리 이해 (with. 예제) ** 본 글은 우아한 형제들 김영한 개발자님 강의를 기반으로 직접 재구성한 글 입니다. ** 🎯 비즈니스 요구 사항과 설계 회원 회원을 가입하고 조회할 수 있다. 회원은 일반과 VIP 두 가지 등급이 있다. 회원 데이터는 자체 DB를 구축할 수 있고, 외부 시스템과 연동할 수 있다. (미확정) 주문과 할인 정책 회원은 상품을 주문할 수 있다. 회원 등급에 따라 할인 정책을 적용할 수 있다. 할인 정책은 모든 VIP는 1000원을 할인해주는 고정 금액 할인을 적용해달라. (나중에 변경 될 수 있다.) 할인 정책은 변경 가능성이 높다. 회사의 기본 할인 정책을 아직 정하지 못했고, 오픈 직전까지 고민을 미루고 싶다. 최악의 경우 할인을 적용하지 않을 수 도 있다. (미확정) 💡 미확정인 부분이 있지만 객체 .. 2022. 10. 13.
[ DFS / BFS ] 알고리즘 문제 정리 1. 특정 거리의 도시 찾기 문제 유형 : BFS 문제 링크 : https://www.acmicpc.net/problem/18352 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번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하.. 2022. 10. 13.
알아두면 좋은 파이썬 문법 _ for 코딩테스트 🎯 리스트 a = [1,2,3,4,5] a.append(2) # 리스트 원소 삽입 a.sort() # 리스트 정렬 - 오름차순 a.sort(reverse = True) # 리스트 정렬 - 내림차순 a.insert(2,3) # 인덱스 2에 3 추가 a.remove(2) # 인덱스 2 원소 삭제 # 특정 값 다 지우고 싶을 때 remove_set = set({3,4}) result = [i for i in a if i not in remove_set] # 리스트 컴프리헨션 사용 🎯 문자열 a = "python" print(a * 3 ) # pythonpythonpython 🎯 집합 자료형 # 사전 자료형 data = dict() data['사과'] = 'Apple' data['바나나'] = 'Banana' .. 2022. 10. 13.
[ BaekJoon ] 마법사 상어와 토네이도 _ 시뮬레이션 🐥 문제 분류 - 시뮬레이션 (구현) 더보기 구현 : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제! 구현 문제로 완전탐색과 시뮬레이션이 주로 출제 - 완전탐색 : 모든 경우의 수를 주저 없이 다 계산하는 방법 - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 🐥 문제 링크 - https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 🐥 문제 설명 마법사 상어가 토네이도.. 2022. 10. 11.

티스토리툴바