본문 바로가기

분류 전체보기

 (146)
구간 테크닉 모음(슬라이딩 윈도우 & 누적합) 이번에 새로 알았거나, 알고는 있었지만 정작 실전에서는 몇번 써본 적 없는 구간합과 관련된 몇가지 테크닉에 대해 다뤄보려 한다. 슬라이딩 윈도우 & 두 포인터양수가 들어있는 배열에서 구간합이 특정 값인 개수를 구할 때 자주 사용하는 알고리즘이다.두 포인터는 시작점과 끝 점을 가리키는 두개의 포인터가 상황에 따라 움직임에 따라 구간의 길이가 유동적으로 바뀌고, 슬라이딩 윈도우는 시작점과 끝점 사이의 간격을 지정한 후, 배열 내에서 한칸씩 전진하며 마치 창문이 미끄러지듯이 작동한다는 점이 다르다. 하지만 두 알고리즘 모두 '해당 알고리즘만' 사용하는 문제는 별로 없다. 사용 시 핵심은 시간복잡도를 줄이는 것이기 때문이다. 두 알고리즘 모두 보통 O(n^2)만큼의 시간이 걸리는 작업을 O(n)만큼만 걸리도록..
JUNGOL #5652 주유소 && #2574 사회망 서비스(복습) https://jungol.co.kr/problem/5652 문제 N개의 노드로 이루어진 트리가 있다. 이 트리의 각 노드에 주유소를 적절히 설치하여 트리 내에서 길이가 K인 모든 경로에 대해서주유소가 없는 길이 없도록 하려 한다. 이때, 설치해야 하는 주유소의 개수의 최솟값을 구하시오.(단, 경로의 길이란 처음 노드와 끝 노드를 잇는 간선의 개수를 의미한다.) (2 문제 관찰문제를 관찰해보니 문제 전체의 느낌이 사회망 서비스와 매우 비슷하게 느껴졌다.단지 다른 점은 주유소의 경우에는 트리 내에서 길이가 K인 모든 경로에서 주유소가 포함되어야 하는 반면, 사회망서비스는 길이가 1인 경로로 연결된 노드들 중에서 하나만 얼리어답터여도 된다는 점 정도이다. 사회망서비스에서 문제를 어떻게 해결했는지 떠올려봤..
JUNGOL #6247 최소리프노드 c++ https://jungol.co.kr/problem/6247 간단한 문제일 수록 발상의 전환이 매우 중요하다는 것을 깨닫게 해준 문제인 것 같다. 문제N개의 노드로 이루어진 트리가 있다. 여기서 트리의 리프노드의 개수가 최소가 되도록 K개의 리프노드를 제거하였을 때, 최소리프노드의 값을 구해야 하는 문제이다. 제한 : (0 시도 + 접근 1. 문제상황 관찰문제에서 요구하는 것이 '리프노드 개수 최소화'이므로 리프노드의 개수가 줄어드는 상황에 대해서 생각해보자.일직선 방향으로 이어지는(진출차수가 1인) 편향 서브 트리에서는 노드를 제거하여도 리프노드의 개수가 줄어들지 않는다.노드를 삭제하면 그의 부모노드가 루트노드가 되어버리기 때문이다. 때문에, 2개 이상의 자식을 가진 노드에서 하나의 자식을 삭제하..
JUNGOL 백열등 2 https://jungol.co.kr/problem/6326문제 N개의 전등이 가로 일렬로 늘어서 있으며 왼쪽부터 순서대로 1 에서 N 까지의 번호가 매겨져 있다.각 조명의 색상은 빨간색, 녹색 또는 파란색 중 하나다.전등들의 색은 문자열 S로 표시되고, i ( 1≤i≤N ) 번째 전등의 색은 S의 i번째 문자가 R이면 빨강, G이면 녹색, B이면 청색이며, 처음에는 모든 전등이 켜져있다.켜져있는 전등이 한 개 이상 있으면, 아래 세 종류의 조작을 좋아하는 순서로 좋아하는 횟수 실시할 수 있다 (조작을 한 번도 하지 않아도 상관 없다).A 원을 지불하고 켜진 전등 중에서 가장 왼쪽에 있는 것을 끈다.B 원을 지불하고 켜진 전등 중에서 가장 오른쪽에 있는 것을 끈다.C 원을 지불하고 켜진 전등을 한 개 선..
DOJ Array and Counting 2 c++ https://dojoi.xyz/ko/problems/85 #85 Array and Counting 2arraycount2 -Unknowndojoi.xyz 문제 양의 정수 N과 길이가 N인 수열 A=[A1​,A2​,⋯,AN​]이 주어진다. 다음 조건을 만족하는 정수 순서쌍 (l,r)(l,r)의 개수를 구하여라.1≤ l ≤ r ≤ N부분 수열 [Al​,Al+1​,⋯,Ar​]의 산술평균이 정수이다.N은 200000이하의 정수, 1 접근 & 풀이처음에는 산술평균이 정수라는 조건이 크게 와닿지 않았다.그리고 Ai의 제한은 왜 그리 작은지도 이해가 가지 않았다. 중앙값으로 뭔가를 해야 하나? 아니면 누적합과 구간 길이를 이용해서 뭔가 수학적으로 풀어야 하나?? 와 같은 생각을 했다. 그리고 일주일이 지나 평균을..
HTML / JS / CSS 수업분 정리 수업을 듣다가 지금까지 배운 내용을 정리하지 않으면 이해를 못할 것 같은 불안감이 들어 한번 크게 정리하고 가겠다.배운 내용이 추가될 때 마다 추가하도록 하겠다. HTML이란?HTML (Hypertext Markup Language,하이퍼텍스트 마크업 언어)는 프로그래밍 언어는 아니고, 우리가 보는 웹페이지가 어떻게 구조화되어 있는지 브라우저로 하여금 알 수 있도록 하는 마크업 언어입니다. 이는 개발자로 하여금 복잡하게도 간단하게도 프로그래밍 할 수 있습니다. HTML은 elements로 구성되어 있으며, 이들은 적절한 방법으로 나타내고 실행하기 위해 각 컨텐츠의 여러 부분들을 감싸고 마크업 합니다. tags 는 웹 상의 다른 페이지로 이동하게 하는 하이퍼링크 내용들을 생성하거나, 단어를 강조하는 등의 ..
2026 상반기 회고 + 하반기 목표 벌써 6월의 시작이다.즉, 2026년도 절반 가까이 지나갔다는 것이다. 지금까지 많은 일들이 있었다. 방학이었던 1~2월, 학기초 3월, 시험기간 4월, 수학여행과 정올이 있었던 5월 등...간단히만 늘어놓아도 크고 작은 이벤트들이 많았는데, 이에 대해 느낀점과 배운점을 간단히 정리하고 남은 하반기에 대한 대략적인계획을 세워보려고 한다. 2026 1.1 ~ 2026 2.28 (방학 + 수학공부)학원과 독서실에 다니며 공부했다. 작년과 다른 점은 더 늦게 자고 늦게 일어났다는 점.이번 방학을 보내며 느낀 가장 큰 점은 일정한 생활패턴이 매우 매우 매우! 중요하다는 사실이다.이번 여름 방학에도 학원을 다니게 된다면 수면 사이클 관리가 핵심이 될 것 같다. 방학 동안에는 거의 수학을 위주로 공부했다. 지금 ..
2026 05.10 정보올림피아드 1차 후기 종료 후 3시간 뒤에 남기는 따끈따끈한 후기이다.결론부터 말하자면 2교시는 어느정도 만족하지만 1교시 이산수학이 많이 아쉬웠던 시험이었다. 일단 2교시 문제부터 알아보자. 00:00 ~ 00:12학생들의 집이 수직선 상의 좌표로 주어졌을 때, 왼쪽 오른쪽으로 k1/ k2 만큼 떨어져 있는 사람들의 수를 구하는 문제였다.문제를 처음 읽고는 pq인가?, n제한이 50만이라서 뭔가 정렬을 해야 할 것 같긴 한데...와 같은 여러가지 생각을 했다.예제를 직접 종이에 그려보고 각 학생별로 집의 좌표 x 주변의 범위 내에 있는 학생들의 수를 빠르게 구하는 방법은 뭘까? 라는 생각을 하며 풀이의 단서를 찾아나갔다. 00:12 ~ 00:16학생의 학교를 인덱스로 하여 같은 학교의 학생끼리만 정보를 저장해놓은 이차원..
완전이진트리 전위, 중위, 후위 순회 - 배열구현 #include #include int n;int* tree;void inorder(int idx, int maxn) { if(idx > maxn)return; inorder(idx*2, maxn); printf("%d ", tree[idx]); inorder(idx*2+1, maxn);}void preorder(int idx, int maxn) { if(idx > maxn)return; printf("%d ", tree[idx]); preorder(idx*2, maxn); preorder(idx*2+1, maxn);}void postorder(int idx, int maxn) { if(idx > maxn)return; postorder(idx*2, maxn); postorder(idx*2+1, maxn..
Good Bye BOJ! 백준에서 알고리즘 공부를 처음 시작하던 때가 어제 같은데 벌써 서비스 종료라니 시간이 참 빠른 것 같습니다..백준 덕분에 알고리즘을 쉽고 재밌게 공부할 수 있었다고 생각합니다.처음으로 스스로 생각해서 문제를 풀어낸 경험, 한 문제를 20번 넘게 틀려본 경험, 플레티넘 티어를 달성한 후 처음으로 난이도 기여를 했을 때의 기쁨, 등은 아직도 제 기억 속에 생생하게 남아있는 것 같습니다.오늘 굿바이 BOJ를 치고 얻은 배경에 적힌 말이 인상깊었습니다."Think, Create, Solve"문제에 대해서 고민하고 시도하고, 실패하고, 마침내 그 문제를 풀어내는 과정에서 얻는 즐거움은 저에게 PS를 계속할 수 있도록 하는 원동력이 되었던 것 같습니다.앞으로도 꾸준히 어떤 문제에 대해 생각하고 생각을 구현해내는 ..

티스토리툴바