CS21 [카테부] 코딩테스트 1회차 총평📍문제 조건 정리하는게 중요📍조건 놓쳐서 틀린게 많음 1번 - 시뮬레이션 문제틀린 이유 - 이중 for 문을 돌려서 시간에서 짤림 ( 보통 문제에서는 10의 9승 안에 들어가야함)- 문제를 꼼꼼하게 읽고 순서대로 푸는 게 중요함 이중 for문 안돌리고 어떻게 하지??-> for문을 돌리면서 한번 돌 때마다 i씩 증가하니까 그걸 일일이 기록하지 말고 그냥 ans에 더할 때 같이 더해주기-> 한번 자른 곳을 또 자를 수도 있음 이러면 i를 더해주면 안되니까 마이너스 범위가 되도록 해야함 -> trees[k] -= (trees[k] + i) 이런 식으로 현재 trees에 남아있는 것에서 현재까지 인덱스 빼줘야됨 ! 2번 - 완전 탐색 시뮬레이션 할 필요 없는 완전 탐색 틀린 이유- 판다가 살고 .. 2024. 7. 20. [알고리즘] 백트래킹 재귀함수안의 값 재귀함수 밖으로 가지고 나오기 백트래킹 재귀함수에서 항상 부딛히는 문제가 있다. 안에서 만든 리스트를 어떻게 밖으로 꺼내올 것인가? 1. final에 ans를 그냥 append -> 안됨 빈 리스트 출력n = int(input())ans = []final = []cnt = 0def beautiful_number(curr_num): global cnt if curr_num >= n: if curr_num == n: cnt += 1 # print(ans) final.append(ans) return for i in range(1, 5): for j in range(i): ans.append(i) .. 2024. 5. 21. [자료구조] HashMap ▶ Java Collection 자료구조 전체 구조 ▶ HashMap이란? Key와 value 쌍으로 구성된 비선형 자료구조이다. ▶ 언제 쓰나? - Key : Value 형태로 저장되기 때문에 Key를 직접 설정하고 접근하는 일이 잦을 때 사용한다. - 검색, 삽입, 제거 연산의 시간 복잡도가 O(1)이기 때문에 해당 연산이 많은 경우 효율적이다. - 하지만 들어온 순서를 반영하지 않기 때문에 들어온 순서 정보가 필요 없을 때 사용해야 한다. ▶ 어떻게 쓰나? 선형 자료구조가 아니기 때문에 버킷에 저장되는 위치를 Hash 함수를 이용해 구한다. 버킷의 해당 인덱스에 데이터를 저장한다. ▶ HashMap의 문제점 - 충돌 이 때 Key는 String이 될 수도 있고, 객체도 될 수 있기 때문에 가능한 경.. 2024. 4. 15. [알고리즘] 그리디 알고리즘이란? 그리디 알고리즘이란 무엇인가? (What) 현재 상태에서 최선의 선택을 반복하는 알고리즘. 아이디어가 간단하다. 전체는 모르겠고 지금 눈 앞의 선택들 중 가장 좋은 선택을 하겠다는 것. 특징 -> 구현이 매우 쉬움 (How는 쉬움) -> dp나 분할 정복과 같이 목적이 한정되지 않고 범용적으로 쓰일 수 있는 알고리즘. 언제 쓰는가? (Why) 항상 최적해를 보장하지 않는다. 때문에 언제 쓸 수 있는지를 파악하는 것이 중요하다. 조건 2가지 optional substructure 최적 부분 구조 가질 때 greedy choice property 그리디 우선 선택 - 한번의 선택이 다음 선택과 무관할 때(영향을 주지 않을 때) 최적 부분 구조란 무엇인가? 부분 문제의 최적해가 전체 문제의 최적해를 구성하는 .. 2024. 3. 27. [알고리즘] DP - 예시 문제들 1. Fibbonacci 수 계산하기 2. 계단 오르는 경우의 수 3. 도미노 타일링 -> 2 * N 크기의 벽을 2 * 1, 1 * 2 크기의 타일로 채울려고 하는 경우 1) subproblem dp[i-1] dp[i-2] 2) 점화식 dp[i] = dp[i-1] + dp[i-2] 3) dp 테이블 채우기 - tabulation 4. 최대합 계산하기 5. zig-zag 수열 6. LCS(Longest Common Subsequence) 계산하기 문제 정의 대표적인 DP 문제로 두 문자열 X, Y의 가장 긴 공통 부문자열을 찾는 문제임. 활용 DNA 시퀀스가 서로 얼마나 가까운 유전자인지 LCS 길이를 통해 알 수 있다. -> 유전 공학에 쓰인다고 교수님께서 말씀해주셨다 어떻게 풀까? 두 문자열이 주어지.. 2024. 3. 4. [알고리즘] 그래프란? & 탐색 알고리즘이란? 그래프란 무엇인가? (What) 정점(노드)들의 연결 관계를 간선(엣지)을 이용하여 표현한 자료구조 => 그래프를 만든다는 것은 정점(node)과 간선(edge)을 정의하는 것 그래프는 언제 써야하는가? (Why) 자료구조이기 때문에 데이터를 저장하고 싶을 때 사용해야함. 자료구조 - 선형 / 비선형이 있음. 비선형 자료구조 - 그래프, 트리가 있음. 그래프는 트리와 달리 계층이 없고, 루프가 있을 수 있음. => 따라서 자료구조를 쓰고 싶은데, 비선형이고 계층이 없고 루프가 있을 수 있는 구조가 적합할 때 ! 그래프를 사용하는 것이 좋음. 그래프를 컴퓨터에 저장하는 방법 (How) 1. 인접 행렬 장점 - 구현이 쉬움, 연결되어 있는지 판단 빠름 단점 - 메모리 낭비가 많아짐 (노드 개수 ^ 2) 2... 2024. 3. 4. 이전 1 2 3 4 다음
