기록

문제https://programmers.co.kr/learn/courses/30/lessons/12929 코딩테스트 연습 - 올바른 괄호의 갯수올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모programmers.co.kr풀이1. 접근하기괄호쌍 2개를 이용한다고 할때, 아래와 같다.탐색하기문자열 뒤에 "("을 붙인다.올바른 괄호쌍이라면, 탐색을 계속한다. 문자열 뒤에 ")"을 붙인다.올바른 괄호쌍이라면, 탐색을 계속한다. 올바른 괄호쌍")"의 개수가 "("보다 많지 않다.2. 시간초과'('의 개수 기록하기더보기# "("의 개수를 기록하지 않음d..

문제https://programmers.co.kr/learn/courses/30/lessons/12942# 코딩테스트 연습 - 최적의 행렬 곱셈크기가 a by b인 행렬과 크기가 b by c 인 행렬이 있을 때, 두 행렬을 곱하기 위해서는 총 a x b x c 번 곱셈해야합니다. 예를 들어서 크기가 5 by 3인 행렬과 크기가 3 by 2인 행렬을 곱할때는 총 5 x 3 x 2 =programmers.co.kr풀이문제 접근하기행렬곱셈에는 결합법칙이 성립하므로 행렬을 곱하는 순서에 따라 곱셈의 횟수가 달라진다.dp를 사용해서 이 문제를 해결할 수 있다. 우선, N*N의 테이블을 작성한다. 테이블의 각 셀에는 아래에 해당하는 값을 적어 넣는다.dp[시작][끝] = (시작~끝) 범위에 있는 행렬을 모두 곱할 ..

문제https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4programmers.co.kr풀이신장트리모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프최소신장트리최소한의 비용으로 만들수 있는 신장트리크루스칼 알고리즘1. 간선을 비용이 적은 것부터 오름차순으로 정렬한다.2. 각 간선이 사이클을 발생시키는지 확인한다.2-1. 사이클을 발생시키지 않는다면 신장 트리에 포함한다.2-2. 사이클을 발생시키지 않는다면 신장 트리에 포함하지 않는다.풀이전체적인 틀은 dfs & bfs 와 같다.graph에 연결된 노드와 가중치를 저장한다.graph = {0..

문제https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4programmers.co.kr풀이간단한 다익스트라dfs & bfs 방식으로 각 노드를 탐색한다.중복을 체크하는 방식dfs & bfs 방식과 이 부분만 다르다지금의 방식이 이전보다 비용이 적게 들때만 탐색을 계속한다.개선된 다익스트라간단한 다익스트라에 탐색할 노드를 선정하는 방식이 개선되었다.최소 heap을 사용하여 가장 적은 비용이 드는 노드부터 검증한다.플로이드 워..

문제https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한programmers.co.kr풀이각 leaf node에서 가중치를 부모 노드로 옮긴다.이 과정을 leaf 노드가 사라질 때까지 반복한다. 시간초과dfs 나 bfs를 이용해서 모든 노드를 탐색하도록 했으나, 시간초과로 대부분의 테스트 케이스에서 통과하지 못했다. leaf node를 제거하면, 그 부모가 leaf node 후보가 되므로, 부모가 가진 간선개수를 이용해서 다음에 ..

문제 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 풀이 직전 노드의 방향 저장 자동차의 방향이 변경되지 않으면 100원, 자동차의 ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 1) two pointer 리스트를 직접 뒤집거나, 특정 원소를 제거하면 수행 시간이 오래 걸리므로 다른 방법을 생각했다. 리스트 뒤집기 리스트가 뒤집어 졌는지 여부를 저장하는 변수를 하나 두어, R이 나올 때 마다 이 값만 갱신했다. 원소 제거하기 리스트가 뒤집어지지 않았다면 왼쪽에서 원소를 꺼내고 리스트가 뒤집어졌다면 오른쪽에서 원소를 꺼낸다. (deque를 활용해도 된다.) 직접 리스트를 수정하지 않고, start point와 end p..

문제https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기[[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0programmers.co.kr풀이문제 풀이 방식을 간단하게 표현하면 아래와 같다.1. table에서 모든 퍼즐조각을 찾는다.2. game_board에서 모든 퍼즐..