kkoon9

더 깔끔한 노션을 원한다면 세그먼트 트리(Segment Tree) 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행 www.notion.so 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행 구간 트리(Segment Tree)는 이 트리 구조의 이점을 살려서 특정 구간에서의 최대, 최소 값등을 빠르게 구할 수 있도록 합니다. 특히, 일차원 배열의 특정 구간에 대한 질문들(최대, 최소, 합 등)을 빠르게 구하는데 사용. 즉, 구간의 개수가 클 때 세그먼트 트리를 생각하자. Segment Tree를 이용하여 특정 구간의 값(최대, 최소, 합 등)을 미리 전처리해서 부모 노드에 저장한다. 그로 인해 훨씬 더 빠른 시간에 탐색할 수 있다. 1. S..

DFS/BFS(완전탐색) 2583(영역구하기) 2667(단지번호붙이기) 1759(암호만들기) 1987(알파벳) 2580(스토쿠) 14889(스타트와 링크) : DFS(조합 : 중요) 9019(DSLR) 5014(스타트링크) 15684(사다리 조작) 16956(늑대와 양) 2468(안전영역) 6593(상범 빌딩) 13459(구슬탈출) 13460(구슬찰출 2) 12851(숨바꼭질 2) 13913(숨바꼭질 4) 15653(구슬탈출 4) 2210(숫자판 점프) 1780(종이의 개수-분할정복) 14502(연구소) 17141(연구소 2) 17142(연구소 3) 17090(미로 탈출하기) 3055(탈출) 14923(미로탈출) 1726(로봇) 4991(로봇청소기 : BFS, DFS) 15684(사다리 조작) 시뮬레이션..

더 깔끔한 노션을 원한다면 Baekjoon 9935 문자열 폭발 - 메모리 초과 String 메모리 초과 때문에 마음 고생을 하게 했던 문제. www.notion.so 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net String 메모리 초과 때문에 마음 고생을 하게 했던 문제. 처음 생각 - contains, replace 문제 보고 바로 떠오른건 contains, replace였다. private static void P9935() throws Exception { BufferedReader..

4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마�� www.acmicpc.net 2020년 코딩 테스트 문제와 비슷하여 풀어보았다. 처음 생각 - 괄호 개수 문제를 읽어보면 stack을 사용해야 한다고 느껴진다. 하지만 괄호 개수만 체크하면서 풀 수 있지 않을까 생각이 들었다. private static boolean isCheckString(String str) { int small = 0; int big = 0; for(int i = 0 ;i

문제 링크 로마 숫자 문제 요약 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같다. 입력으로 주어진 두 수를 더한 값을 첫째 줄에 아라비아숫자로 출력하고 둘째 줄에는 로마 숫자로 출력한다. 함수 설명 strNum : 로마 숫자를 아라비아 숫자로 바꿔주는 함수 numStr : 아라비아 숫자를 로마 숫자로 바꿔주는 함수 문제 해답 #include #include using namespace std; #define I 1 #define V 5 #define X 10 #define L 50 #define C 100 #define D 500 #define M 1000 int strNum(string str1); void numStr(int res); int..

문제 링크 바이러스 문제 요약 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다. 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘을 사용하여 1번 컴퓨터에 연결되어 있는 컴퓨터의 개수를 출력하면 된다. 문제 해답 #include using namespace std; const int N_MAX = 100 + 1; bool check[N_MAX..

문제 링크 줄 세우기 문제 요약 첫째 줄에는 학생의 수가 주어지고 둘째 줄에는 줄을 선 차례대로 학생들이 뽑은 번호가 주어진다. 학생의 수가 100 이하이고, 학생들이 뽑는 번호는 0 또는 자연수이며 학생들이 뽑은 번호 사이에는 빈 칸이 하나씩 있다. 학생들이 처음에 줄을 선 순서대로 1번부터 번호를 매길 때, 첫째 줄에 학생들이 최종적으로 줄을 선 순서를 그 번호로 출력한다. 학생 번호 사이에는 한 칸의 공백을 출력한다.list 입력 값이 0이면 서 있는 자리 그대로, x면 x칸 앞에 서게 된다. list에 메소드인 insert를 활용하여 문제를 해결하였다.문제 해답 #include #include using namespace std; int main(void) { int N, x; list l; ci..

문제 링크 일곱난쟁이 문제 요약 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다. 브루트 포스 정답을 찾을 때까지 반복문이 진행되므로 브루트 포스 문제이다. 조건문과 반복문을 잘 짜주면 어렵지 않게 문제를 해결할 수 있다. 문제 해답 #include #include using namespace std; const int SIZE = 9; // 난쟁이의 수 const int Height = -100; int main(void) { int arr[SIZE]; /* 난쟁이들의 키 */ int ..