kkoon9

더 깔끔한 노션을 원한다면 Baekjoon 1759 암호 만들기 - BackTracking 설계 www.notion.so 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1. input char[] password = new char[L]; visit = new boolean[C]; charArr = new char[C]; String[] strArr = br.readLine().split(" "); for (int i = 0; i < C; i++) { charArr[i] = strArr[i].charAt(0); ..

더 깔끔한 노션을 원한다면 Baekjoon 9012 괄호 - Stack Stack www.notion.so 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net Stack 라이브 코딩에서 나올법한 문제이므로 다시 풀어보았다. 괄호가 올바른 괄호인지 확인하는 함수 : isVPS private boolean isVPS(char[] PS, Stack stack) { for (int i = 0; i < PS.length; i++) { char ch = PS[i]; if (ch == ')') ..

더 깔끔한 노션을 원한다면 Baekjoon 2667 단지번호붙이기 - DFS DFS www.notion.so 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net DFS 앞서 풀었던 영역 구하기와 같은 문제이다. 영역 구하기를 혼자 해결하지 못했더라면 이 문제를 풀어보면 좋다. 1. [1,1]에서 [N,N]까지 loof 진행 for (int i = 1; i 0 && x = 0 && x < N && y < M; } }

더 깔끔한 노션을 원한다면 Baekjoon 2583 영역 구하기 - DFS DFS www.notion.so 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS DFS에 대표적인 문제이다. 1. [0,0]에서 [N,M]까지 loof 진행 for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) { if (visit[j][i] || map[j][i]) continue; visit[j][i] = true; DFS(j, i); width.add(c..

더 깔끔한 노션을 원한다면 Baekjoon 2042 구간 합 구하기 - 세그먼트 트리(구간 합, 수정) 세그먼트 트리 www.notion.so 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 세그먼트 트리 최솟값 문제에서 배운 세그먼트 트리를 응용하여 변경 및 구간 합 문제를 풀이하였다. 최솟값을 구하는 문제와 달리 구간합에서는 init과 query가 변경되어야 했고 update가 추가됐다. 수의 범위가 굉장히 크므로 long 자료형을 써야한다. ..

더 깔끔한 노션을 원한다면 Baekjoon 10868 최솟값 - 세그먼트 트리 처음 생각 - copyOfRange www.notion.so 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 처음 생각 - copyOfRange [a,b] 구간을 copyOfRange를 통해 잘라서 최솟값을 구하는 방법을 택했다. for(int index = 1; index

더 깔끔한 노션을 원한다면 세그먼트 트리(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(사다리 조작) 시뮬레이션..