코테 연습

처음에 문제를 확인했을 때 min()과 max()를 이용해서 풀면 될 것 같다는 생각이 가장 먼저 떠올랐는데, operations의 길이가 최대 1,000,000이라 더 효율적인 알고리즘을 사용해야되는 문제인줄 알았다.근데 그냥 풀린다... 그래서 파이썬으로 풀면 너무

기본적인 DP를 이용해서 풀이하였다.같은 레벨의 노드중에서 가장 좌측에 위치한 노드인 경우와 가장 우측에 위치한 노드인 경우만 따로 처리해주고, 나머지는 연결된 상위 레벨의 노드와 비교하여 더 큰 값을 이용해 구해주면 된다.

간단한 DFS/BFS 문제이다.각 노드를 순회하면서 아직 방문하지 않은 경우 answer+=1 해주고, 그 노드와 연결된 노드에 방문 처리를 해주는 방식이다.이렇게 모든 노드를 돌면 네트워크의 수를 구할 수 있다.

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)

백준 URL: \[https://solved.ac/contribute/2166|다각형의 면적]난이도 골드 5'신발끈 공식'에 의해서 쉽게 풀이할 수 있다.공식에 의한 풀이 방법을 알고 있다면 사실상 브론즈 수준의 문제이다.원래 공부한 내용을 obsidian에

백준 URL: 집합의 표현난이도 골드 5유니온 파인드를 사용하여 풀이했다.finder() 함수를 통해 노드들이 입력되었을 때 해당 노드들의 부모가 같도록 묶어주고, 부모 노드를 비교하였을 때 값이 같은 경우 같은 집합에 속하는 것으로 볼 수 있다.

백준 URL: \[https://solved.ac/contribute/17081|RPG Extreme]난이도 플래티넘 2특별한 알고리즘이 사용되지는 않았지만 구현량이 많은 빡구현 문제다.이런 구현을 할 때 특정 부분에서 틀리게 되면 디버그를 어떻게 할 것이냐가

백준 URL: https://solved.ac/contribute/3197(백조의 호수)난이도: 플래티넘 5가장 먼저, 문제의 첫 번째 문장에서 '두 마리의 백조가 호수에서 살고 있으며', '두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다'고 되어 있기 때

백준 URL: 벽 부수고 이동하기 4난이도 골드 2처음부터 빈 공간(0)에 대해 BFS 또는 DFS 처리 후, 벽이 존재하는 공간(1)을 기준으로 4방향의 값을 합치면 될거라는 풀이 방법을 떠올릴 수 있었다.다만 문제가 발생하는 부분은 크게 2가지가 있다.1\. 벽이

백준 URL: 문명난이도 플래티넘 4bfs를 진행하면서 각 문명에 대해 빈 공간일 경우 문명을 전파하고, 다른 문명일 경우 문명이 합쳐져있는 상태인지 확인하고, 서로 다른 문명일 경우 하나로 묶으면 될 것이라고 생각했다.서로 다른 문명인지를 구별하고 문명을 묶는 방법은

백준 URL: 열쇠난이도 골드 1건물의 바깥에서 시작한다는 것은 모든 가장자리를 통해 드나들 수 있음을 나타낸다. 즉, 가장자리를 시작 지점으로 하여 q에 넣어주면 쉽게 구현이 쉬워진다.유의할 점은 시작 지점이 문이던, 열쇠던, 문서던 상관 없이 벽만 아니면 시작 지점

백준 URL: 계단 수난이도 골드 1쉬운 계단 수의 심화 문제이다.0~9를 모두 포함해야 한다는 것은, 다음과 같은 수를 의미한다.그런데, 조금만 생각해보면 알 수 있겠지만 계단 수는 수들이 모두 인접해 있고, 9->0으로의 이동이 불가능하기 때문에, 0에 대한 방문

문제 URL: 나무 섭지난이도 Lv.3남우를 기준으로 출구에 대한 BFS를 하고, 출구를 기준으로 유령에 대한 BFS를 수행해서 반환된 값을 비교하면 쉽게 풀 수 있다.

백준 URL: 큐빙난이도 플래티넘 5다음과 같은 형태로 큐브를 일차원 배열에 저장하고, 필요한 부분만 가져와서 rotate 해주면 문제의 요구사항을 쉽게 구현할 수 있을 거라고 생각했다.유의해야할 사항은 큐브를 돌린다는 것은 다음의 요소에 대해 제어해야 한다는 것을 나

백준 URL: 철로난이도 골드 2

백준 URL: 호텔난이도 골드 4풀이 방법은 다음과 같다.1\. DP 테이블을 초기화한다. 한번에 홍보로 얻을 수 있는 사람 수가 100명이기 때문에 c+101(100명 + 인덱싱으로 인한 1)로 크기를 잡아준다. 0명을 모으는데는 0원이 들기 때문에 dp\[0]=0이

백준 URL: 너 봄에는 캡사이신이 맛있단다난이도 골드 2이 문제는 N개의 메뉴에 대한 스코빌 지수가 주어졌을 때, 만들 수 있는 모든 메뉴 조합에 대한 '주헌 고통지수'를 구하는 것이고, '주헌고통지수'는 각 조합의 최댓값과 최솟값의 차이이다.그리고 모든 조합에 대해

백준 URL: 세 용액난이도 골드 3가장 간단한 방법은 세 개의 용액을 선택하는 모든 경우의 수를 탐색하는 것이다. 하지만 이 방법은 시간 복잡도가 O(N³)이 되어 N이 5,000일 경우 시간 초과가 발생한다.따라서 더 효율적인 접근 방식이 필요하다. 이 문제는 정렬

백준 URL: N포커난이도 골드 2'적어도 하나'라는 조건이 붙는 경우의 수 문제는 포함-배제의 원리(Principle of Inclusion-Exclusion)를 사용하여 푸는 것이 정석이다.직접 '포카드가 하나만 있을 때', '두 개 있을 때', ... 등을 계산하

백준 URL: 두 배열의 합난이도 골드 3이 문제는 두 배열 A와 B의 모든 부 배열(연속된 부분 배열)의 합을 각각 구한 뒤, A의 부 배열 합과 B의 부 배열 합을 더해서 목표값 T가 되는 쌍이 총 몇 개인지 찾는 것이다.다음과 같은 방식으로 접근하였다.1\. 배열

백준 URL: 책 페이지난이도 플래티넘 5해당 코드는 숫자를 가장 낮은 자릿수(일의 자리)부터 하나씩 처리하며 올라간다. 각 자릿수를 처리할 때마다 해당 자릿수에 0부터 9까지의 숫자가 몇 번 나타나는지를 계산하여 ans 배열에 누적한다.i는 현재 자릿수, c는 현재

백준 URL: 찾기난이도 플래티넘 5KMP 알고리즘은 '실패 함수' 또는 'Pi 배열'이라고 불리는 전처리 배열을 사용한다. pi\[i]의 값은 패턴의 0번 인덱스부터 i번 인덱스까지의 부분 문자열에서, 접두사(prefix)와 접미사(suffix)가 일치하는 가장 긴

백준 URL: 책 페이지난이도 골드 3i번째 행렬부터 j번째 행렬까지 곱하는 데 필요한 최소 곱셈 횟수를 저장하는 'dp' 테이블을 생성하였다. 점화식은 다음과 같다.dp\[i]\[j] = min(dp\[i]\[k] + dp\[k+1]\[j] + matrices\[i]

백준 URL: 트리와 쿼리난이도 골드 5간단한 트리 문제이다. 가장 끝에 있는 리프 노드에서부터 서브트리 크기를 계산하는 것이 핵심이다.여기까지는 입력을 받고 트리를 구성해주는 단계이다.가장 먼저 '인접한 노드를 가진 그래프' 입력받은 다음에 BFS로 '방향성을 가진