본문 바로가기

전체 글263

[9663] N-Queen , 자바 , dfs(백트래킹) 1. 문제레벨: G4알고리즘: dfs(백트래킹)풀이시간: 30분힌트 참조 유무: 유https://www.acmicpc.net/problem/96632. 문제 풀이실패 시도:서로 공격하지 않는 경우의 수로 구하려고 하였으나 N^2 C N 의 시간 복잡도가 나왔습니다. 이는 한 눈에 봐도 큰 경우의 수 입니다. 아무리 백트래킹을 한다그래도 N = 15, 시간제한 = 10초 안에 불가능할 거라 판단하였습니다.전체 경우의 수 - 서로 공격하는 경우 로 구하려고 하였으나 서로 공격하는 경우에서 2 ~ N이 서로 공격하는 경우를 구할 때 중복이 발생함으로 중복을 해결하는 과정이 너무 복잡해보였습니다.  잘못된 방법인 냄새실패 원인: N^2 C N에 대한 오해N^2 C N은 "N^2개의 칸에서 N개의 퀸을 선택하여 .. 2025. 1. 19.
[백준 1799] 비숍 / 자바 / 백트래킹 + 분할정복 #문제레벨: G1알고리즘: 백트래킹 + 분할정복풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1799#문제 풀이완전탐색을 할 경우 2의 100승으로 무조건 시간초과입니다. 그렇다 하면 조금 더 긍정적으로 생각해보겠습니다. 흰색칸 비숍과 검정칸 비숍은 서로 영향을 줄 수 없습니다. 그래서 우린 흰색칸 비숍과 검정칸 비숍을 나누어서 탐색하게 된다면2^50 + 2^50 으로 아까보다 나아졌습니다. 그래도 우린 시간초과에 걸립니다. 그렇다면 우리에겐 dp가 남아있습니다. 위 문제를 dp로 풀 경우를 생각하면 비트마스킹 dp을 생각해볼 수 있습니다. 이차원배열을 100자리의 비트마스킹으로 표현하는 것입니다. 그러나 대각선의 겹치는 비숍이 있는지 검사하기에는 까다로울 .. 2025. 1. 18.
[백준 16234] 인구 이동 / 자바 / bfs #문제레벨: G4알고리즘: bfs풀이시간: 50분힌트 참조 유무:https://www.acmicpc.net/problem/16234#문제 풀이특정 국가(A)를 기준점으로 삼고 그 국가와 연할될 수 있는 국가(B)를 찾고 B와 연합될 수 있는 국가를 찾고(C) 반복한다. 이 형식 어디서 보지 않았는가? 4방향+bfs(or dfs)이다. 그런데 bfs 한 번으로 모든 국가를 다 탐색할 수는 없다. 그래서 이중 for문으로 모든 국가를 돌대 visited =false(방문하지 않은) 곳만 bfs(or dfs)를 돌린다. 코드는 둘 다 첨부하겠다.코드를 보면 bfs(or dfs)를 마치고나서 인구이동을 시킨다. bfs로 인접국가를 순회하는 김에 인구이동까지 하면 안되나? 라는 충동이 들었지만, 구현이 복잡하고 .. 2025. 1. 17.
JVM(with 컴파일 과정) 1. 자바자바는 OS에 독립적인 특성을 가지고 있습니다. 그게 가능한 이유는 JVM(Java Virtual Machine) 때문입니다. JVM의 어떤 기능 때문에 OS에 독립적으로 실행시킬 수 있는지 자바 컴파일 과정을 통해 알아보겠습니다.2. 컴파일 과정자바 소스코드가(.java) 자바 컴파일러(javac)를 통해 자바 바이트 코드로 변환됩니다.(.class)컴파일된 바이트코드(.class)를 JVM의 클래스로더(Class Loader)에게 전달합니다.클래스 로더는 동적로딩(Dynamic Loading)을 통해 필요한 클래스들을 로딩 및 링크하여 런타임 데이터 영역(Runtime Data Area의 Method Area), 즉 JVM의 메모리에 올립니다.메모리에 올리는 과정은 총 3가지 과정을 거칩니다.. 2025. 1. 16.
자바 가비지 컬렉션 CMS → G1 GC → ZGC 버전 별 발전과정 1. Java의 GC 발전 과정 개요Java에서 GC(Garbage Collector)는 메모리 관리를 자동화하여 개발자가 메모리 할당 및 해제를 직접 처리하지 않아도 되도록 합니다. 초기에는 Serial GC와 Parallel GC가 사용되었지만, 애플리케이션의 규모와 성능 요구사항이 증가함에 따라 CMS (Concurrent Mark Sweep), G1 GC (Garbage First), ZGC (Z Garbage Collector) 등이 도입되었습니다.각 GC는 Java의 메모리 관리와 Pause Time을 줄이고 성능을 향상시키기 위해 설계되었습니다.2. CMS (Concurrent Mark Sweep)2.1 동작방식Initial Mark: 살아있는 객체를 찾기 위한 초기 마킹 (STW 발생)Ol.. 2025. 1. 10.
자바 버전 별 선택 이유 LTS(Long Term Support) 버전을 선택하는 것이 안정적인 운영에 유리하기 때문에 LTS 버전만 기록하겠습니다.Java 8 : 2030년 12월까지Java 11 : 2026년 9월까지Java 17 : 2029년 9월까지Java 21 (2031년까지 지원)Java 8 (LTS)선택 이유:안정성이 매우 높고 레거시 시스템과 호환성 우수Lambda와 Stream API 도입으로 함수형 프로그래밍 지원서드파티 라이브러리 지원이 가장 풍부Java 11 (LTS)Spring Boot 2.x의 권장 버전 - Spring Framework 5 -가비지 컬렉터 성능 향상Java 11의 기본 가비지 수집기는 G1GC(가비지 우선 가비지 수집기)전체 힙을 일정 크기로 나누어 영역 별로 가장 많은 가비지가 쌓인 .. 2025. 1. 10.
[Real MySQL 9장] 옵티마이저와 힌트 1. 개요옵티마이저는 MYSQL에서 최적의 쿼리 실행계획을 수립하는 기능입니다.1.1 쿼리 실행 절차SQL파서: 사용자로부터 요청된 SQL 문장을 쪼개서 MYSQL 서버가 이해할 수있는 수준으로 분리(파스 트리)합니다.옵티마이저: 파싱 정보를 보면서 어떤 테이블부터 읽을지, 어떤 인덱스를 이용해 테이블을 이용해 읽을지 선택합니다.MYSQL 엔진, 스토리지 엔진: 두 번째 단계에서 결정된 테이블의 읽기 순서나 선택된 인덱스를 이용해 스토리지 엔진으로부터 데이터를 가져옵니다.1.2 옵티마이저의 종류옵티마이저는 테이터 베이스 서버에서 두뇌와 같은 역할을 담당합니다.규칙 기반 최적화(RBO, Rule-Based Optimizer)초기 버전에 많이 사용내장된 우선순위에 따라 실행 계획 수립통계 정보(테이블의 레코.. 2025. 1. 9.
[Real MYSQL 10장] 실행 계획 옵티마이저가 항상 좋은 실행 계획을 만들어낼 수 있는 것은 아닙니다.그렇기 때문에 DBMS 서버에서는 이를 보완할 수 있도록 EXPLAIN 명령으로 옵티마이저가 수립한 실행 계획을 확인할 수 있습니다.1. 통계 정보MySQL 5.7 까지는 테이블과 인덱스에 대한 정보를 가지고 실행 계획을 수립했습니다.MySQL 8.0 부터는 인덱스되지 않은 칼럼들에 대해서도 데이터 분포도를 수집해서 저장하는 히스토그램 정보가 도입됐습니다.1.1 테이블 및 인덱스 통계 정보MySQL 서버의 통계 정보 MySQL 5.5 버전 까지는 각 테이블의 통계 정보가 메모리에서만 관리되어서 서버 재시작시 모두 사라졌습니다.이후의 버전에서는 각 테이블의 통계 정보를 mysql 데이터베이스의 innodb_index_stats 테이블과 i.. 2025. 1. 3.
동시성 문제 해결 1. 문제리뷰삭제 요청에서 단일결과를 예상했지만, 9개의 결과를 리턴한다고 합니다. 예상대로라면 리뷰좋아요는 member당 하나씩 밖에 갖지 못합니다.1-1. 문제 원인리뷰를 저장할 때 동시성 이슈가 발생해서 그렇습니다.Transaction1과 Transaction2가 거의 동시에 시작되어 각각 BEGIN을 합니다.두 트랜잭션 모두 memberId=1, reviewId=1인 데이터를 찾기 위해 findByMemberIdAndReviewId를 호출합니다.빨간색 박스로 표시된 Race Condition 구간에서:Transaction1이 조회했을 때 "결과 없음"을 받습니다 (아직 좋아요가 없으므로)Transaction2도 조회했을 때 "결과 없음"을 받습니다 (Transaction1이 아직 커밋하지 않았으므.. 2024. 12. 22.

티스토리툴바