[백준] 5547번 일루미네이션 _ Python
·
Algorithms/Graph
[초기 접근 방법] 1. 정육각형이므로, 6개의 지역에 접근해야 한다. - 짝수 행, 홀수 행에 따라 육각형의 탐색 범위가 달라진다. 2. 그런데 닫힌 구역을 어떻게 판단하지? - 이 부분에 대해서 visited[i][j] == 6 일 경우로 판단하자 라고 생각했지만, 닫힌 구역내의 육각형이 여러 개일 경우 불가한다.. [생각] 예전에 팀프로젝트로 미로찾기 알고리즘을 한 적이 있었는데, 기능 중 하나로 '닫힌 구역에 대해서 미로가 더 이상 탐색하지 않게끔 한다.' 가 떠올랐다. 각설하고, 생각을 해보았지만 닫힌 구역에 대한 판단에 대한 알고리즘이 떠오르지 않아 블로그를 참조했다. 1. 한 번에 바깥쪽의 공간 지역 전체 탐색하기 위해, 상하좌우 4개의 구역을 1칸씩 늘려준다. 2. 주변 6개의 인접 구역..
4주차. 이상현상, 함수적 종속성, 정규화
·
CS./데이터베이스
1~4. 이상 현상이 뭘까요? *주로 관계형 데이터베이스에서 발생하는 문제로, 데이터의 무결성이 깨지는 상황을 의미 1) 삽입 이상(Insertion Anomaly) - 데이터를 삽입하기 위해 필요한 정보가 부족한 상황 ex. 직원을 추가할 때 'IT' 부서가 없는데, 설정했을 때 2) 갱신 이상(Update Anomaly) - 중복된 정보로 인해 동일한 내용을 여러 번 갱신해야 하는 상황 ex. 부서 이름이 변경되면, 해당 부서에 있는 모든 직원 레코드 수정 3) 삭제 이상(Deletion Anomaly) - 특정 데이터를 삭제할 때, 그 정보와 관련된 다른 정보도 함께 삭제되는 상황 ex. 부서 정보를 삭제하면, 해당 부서에 있는 모든 직원 레코드 삭제 이러한 이상현상를 방지하기 위해 "데이터 정규화..
[백준] 16918번 봄버맨 _ Python
·
Algorithms/Graph
[초기 접근 방법] 1초 - 초기 상태 2초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 3초 - '초기 폭탄'의 인접 지역 펑! 4초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 5초 - 2초에 설치된 폭탄 펑! 6초 - 폭탄이 설치되어 있지 않은 모든 칸 폭탄 설치 7초 - 4초에 설치된 폭탄 펑! [생각] 홀수∙짝수 시간에 대한 규칙을 찾고, 폭탄을 구분해서 어떻게 터트릴까 고민했던 문제 왜 이렇게 오래 걸렸을까? → 머리로만 생각하지말고, 직접 메모로 기록하면서 반복되는 규칙을 찾자 [코드] # 풀이 시간 : 1시간 30분 # 시간복잡도 : O((N/2) * (5B + RC)) # N회 반복 # 홀수 : bfs 폭탄 터지기 (5개 간선, 폭탄 개수 B) # 짝수 : 모든 칸 폭탄 설치..
2. API 개발 고급 - 준비
·
Spring/JPA 2
- 앞으로 배울 내용 정리 1) 조회용 샘플 데이터 입력 (섹션 2.) - InitDB 생성 - DB 초기 데이터 구축 (Member, Book, OrderItem, Delivery, Order - persist) 2) 지연 로딩과 조회 성능 최적화 3) 컬렉션 조회 최적화 4) 페이징과 한계 돌파 5) OSIV와 성능 최적화
[백준] 2228번 구간 나누기 _ Python
·
Algorithms/DP
https://www.acmicpc.net/problem/2228 [초기 접근 방법] - 문제 이해 잘못 (2번 조건을 무시하고 '배열 구간 나누기'로 풀었다.) 그래도 이 때 문제 풀이를 적자면, 골드3 문제인데, dp[]가 1차원 배열이라니 뭔가 이상했어... [생각] 틀리고 '반례가 있을까?' 질문 게시판을 찾아보다가 접근이 아예 잘못된 것 같아서 구글링을 했다. 1. dp[i][j] : i개의 배열로, j개의 구간을 선택했을 때 구간합 최댓값 - 이 때 주의할 점은 배열을 이루는 수에는 음수도 있기에, -float('inf')로 초기화한다. 2. 점화식 1) 현재 구간을 유지하면서, i번째 값을 포함시키지 않았을 경우 dp[i][j] = max(dp[i][j], dp[i-1][j]) 2) 새로운 ..
[백준] 17626번 Four Squares _ Python
·
Algorithms/DP
[초기 접근 방법] 1. dp[i] : 합이 i가 되는 제곱수들의 최소 갯수 2. 점화식 dp[n] = min(dp[n], dp[n-제곱수] + 1) → 제곱수가 n보다 작을 때까지 비교 [생각] 문제에서 원하는 "합이 i가 되는 제곱수들의 최소 갯수"를 dp로 정의하고 풀면 되는 문제였어서, 쉽게 풀었던 것 같다. 아.. 시간 제한이 0.5초 이길래 시간초과가 나올까 봐 상수 시간복잡도까지 구했었다 [코드] # 풀이 시간 : 15분 # 시간복잡도 : O(N*sqrt(N)) → 1100만? # 공간복잡도 : O(n^2) # 참고 : - # 점화식을 세우자.. ㅎㅎ import math import sys input = sys.stdin.readline N = int(input()) # dp[i] : 합이..