1. 문제 2. 풀이 방법문제를 이해하기 위해 예제로 주어진 트리를 그려봤다. 루트가 주어지기에 자연스럽게 계층 구조가 형성된다. 서브트리의 개수는 곧 자기와 자식들의 정점 수를 모두 합친 수였다. 시간복잡도를 따져봤을 때 정점의 개수는 십만이고, 쿼리의 개수도 십만이기에 O(N)이나 O(logN)으로 풀어야할 것 같았다.어떻게하면 한 번의 쿼리 때 logN의 시간복잡도를 가질 수 있을까 고민해보다가 그냥 한 번 전체탐색을 돌려서 모든 정점의 서브트리의 개수를 구한 후 쿼리에 맞춰 답을 출력해주면 될 것 같았다. 서브트리를 구하는 방법은 재귀적으로 자식 노드들을 방문하면서 개수를 구하면 될 것 같아서 바로 코드로 옮겨봤다.우선 트리를 형성하기 위해 ArrayList 배열을 이용하였다. 아래와 같이 주어..
클래스내에 있는 함수를 테스트하기로 했다. 이때 고민된 것은 테스트 함수를 실행할 때마다 클래스 인스턴스를 만드는 것이었다.테스트 하려는 클래스는 생성자될 때 파싱해야 할 노드를 인자로 받는다. 그러면 매 테스트마다 다른 노드를 인자로 클래스를 만들어야 했다 이때 `fixture`를 사용하면 중복 코드를 줄이고 원하는 객체를 제공할 수 있다. 'pytest.fixture' 데코레이터를 작성하면 매 테스트 함수 호출 때마다 데코레이터를 붙인 함수를 실행한다. 이때 DB와 같은 클래스를 정의하거나 사전 준비 코드를 작성하면 테스트 함수마다 작성해야하는 코드 중복을 줄일 수 있다. @pytest.fixturedef call_parser(elem_manager): # CallParser 인스턴스를 생성하는..
1. 문제https://www.acmicpc.net/problem/15990 2. 접근문제가 너무 DP스러워서 바로 경우의 수들을 차례차례 써봤다. 처음에는 잘 안보였는데 연속해서 사용하면 안된다 조건에 집중해서 계속 생각해봤다. 1이 마지막에 나오면 그 후엔 2와 3만 올 수 있고 그러면 n-2와 n-3에서 정보를 가져와야 할텐데.. 또 마지막에 나오는 수를 저장하기 위해 2차원 배열을 사용해볼까! 하다가 점화식이 떠올랐다 나온 점화식은 아래와 같다dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % MODdp[i][2] = (dp[i-2][1] + dp[i-2][3]) % MODdp[i][3] = (dp[i-3][1] + dp[i-3][2]) % MOD-> result : dp[i][..
소마 프로젝트로 코드의 진행과정을 시각화 해주는 서비스를 만들기로 했다!우선 간단한 별찍기 로직을 시각화 먼저 해보기 했다. 목표 코드a = 8for i in range(a): print('*' * (i+1)) a = 8를 AST 트리로 변환 후 트리 출력하기import ast# 분석할 소스 코드source_code = """a = 8"""# 소스 코드를 AST로 파싱parsed_ast = ast.parse(source_code)# AST 트리를 출력def print_ast(node, level=0): print(' ' * level + ast.dump(node)) for child in ast.iter_child_nodes(node): print_ast(child, le..
macOS에서 파이썬 가상환경을 생성하려면 다음 단계를 따르세요. 1. 터미널을 엽니다.파이썬 3.7이 설치되어 있는지 확인합니다. 터미널에서 다음 명령어를 실행합니다.brew install python@3.7파이썬 3.7이 설치되어 있지 않은 경우, 파이썬 3.7을 설치해야 합니다. zshrc 파일에 alias python="which python3의 결과 경로" 한줄을 추가합니다.# python이 설치된 위치를 찾습니다.which python3# 환경변수 파일에 경로 지정vim ~/.zshrc# 수정사항 적용source ~/.zshrc 2. 가상환경을 생성할 디렉토리로 이동합니다. 다음 명령어를 사용하여 가상환경을 생성합니다. 여기서 myenv는 가상환경의 이름입니다. 원하는 다른 이름을 사용할 수 ..
1. 문제 2. 어떻게 풀까?MST의 비용을 구할 수 있어야 풀 수 있는 문제로 진행되는 라운드 동안 하나씩 가중치가 낮은 간선을 제거하면서 MST의 비용을 구하는 문제이다. 잊고 있던 MST 비용 구하는 개념을 다시 복습해보자Edge 간선을 우선순위 큐에 모두 삽입한다 가중치가 낮은(또는 높은)순으로 우선순위 큐에서 빼낸다Edge를 이루는 두 정점을 이을 시 싸이클이 형성되는지 확인한다 (find 연산)싸이클이 형성되지 않으면 해당 Edge를 MST를 이루는 간선으로 추가한다.간선의 개수가 N-1개가 되면 비용을 리턴한다. N-1개가 되지 못하면 MST 그래프를 만들 수 없다 먼저 MST를 구하는 코드를 짠다.public static int MST(int k, PriorityQueue pq){ i..
1. 문제 2. 접근고려해야 하는 조건은 다음과 같다1번에서 시작해서 N으로 끝내야 한다선택할 수 있는 도시는 최대 M개이다.a도시에서 b도시로 갈 때 경로가 여러개 주어질 수 있다. 최대값만 얻어야 한다 처음 접근은 다익스트라 알고리즘을 사용하는 것이었다. 최대 비용으로 노드를 선택했을 때를 구현하면 될 것 같았다. 하지만 중간에 구현하다가 기내식의 비용이 같을 때는 어떻게 처리하지? 의문이 들었고 그리디적 알고리즘으로 최적의 상황이 해가되는 다익스트라로는 풀 수 없는 것을 깨달았다. 어떻게 풀나 찾아봤더니 DP를 이용하는 문제였다. DP를 2차원 배열 DP[N][M] 선언하고 도시 N을 M번째로 선택했을 떄의 값을 구해준다.점화식은 다음과 같다` DP[b][M] = Math.max(DP[b][M..
1. 문제 2. 접근 입력값이 최대 10만이고 그래이드는 5개이므로 O(5n)으로 풀면 되지 않을까 생각했다. 처음 접근은 이전의 그레이드와 현재 그레이드를 비교해서 연속하면 누적 카운트를 더해주고, 연속이 끊기면 누적 카운트를 맥스값과 비교해서 갱신한 후 누적값을 초기화 시키는 것이었다. 하지만 틀렸다! 더 좋은 방법은 2차원 배열로 student[6][N]를 만들어서 진행하는 것이다. 처음 student 배열을 0으로 모두 초기화한 후, 차례대로 N번 루프를 돈다. 이때 n은 책상의 수로 입력으로 주어지는 n책상에 대한 그레이드 정보를 이용한다. grage1, grade2를 알아낸 후 이전의 값에 1을 더한다. 누적값을 알아야 하므로 이렇게 하면 변수 하나로 누적값을 관리할 수 있다. 그리고 연결이 ..
강의만 따라 칠 때는 몰랐는데 막상 아무것도 없이 해보니 DB 연결부터 막혔다. 그래도 무사히 성공해서 더 이상 헤매지 않도록 글을 작성해본다. 1. build.gradle 의존성 추가 데이터베이스로 JPA를 사용하기 위해 `build.gradle`에 의존성을 추가해준다. https://start.spring.io/ 페이지에서 스프링 부트 프로젝트를 만들 때 `spring data jpa`를 추가해주면 된다. 만약 그렇지 않을 시 아래처럼 의존성을 직접 추가해주면 된다. plugins { id 'java' id 'org.springframework.boot' version '3.2.4' id 'io.spring.dependency-management' version '1.1.4' } group = 'co..
MySQL 완전 삭제하고 재설치하기 (MacOS) MySQL 프로세스 죽이기 (homebrew로 설치했을 경우) brew services stop mysql 관련 파일 삭제하기 설치 경로 확인하기 방법1. which mysql /usr/local/bin/mysql homebrew로 삭제하기 brew uninstall --force mysql 혹은 방법 2. brew uninstall mysql --ignore-dependencies brew remove mysql brew cleanup 다음의 라인을 한줄씩 입력해서 삭제한다. sudo rm -rf /usr/local/mysql sudo rm -rf /usr/local/bin/mysql sudo rm -rf /usr/local/var/mysql sudo ..