본문 바로가기

전체 글242

[백준] 17836: 공주님을 구해라! - JAVA https://www.acmicpc.net/problem/17836 풀이그래프 탐색 문제. (1, 1)에서 (N, M)까지 최단 시간으로 가야 한다. T라는 제한 시간이 있고, 벽은 지나갈 수 없으며, 무기를 찾으면 벽도 통과할 수 있다. 즉, 무기가 있고 없고 두 경우를 방문 처리를 따로 해야 하는 문제이다. class를 만들어 좌표와 시간, 무기가 있는지 정보를 담았다. bfs 탐색을 통해 (0, 0)부터 진행했다. 시간이 T 초 이상이면 진행을 멈췄고, 그전에 목적지에 도착했으면 출력 후 멈췄다. 사방 탐색 후 다음 칸으로 넘어갈 때 무기가 있는지 없는지에 따라 다르게 처리했다.  메모리: 16148KB시간: 176ms언어: Java 11import java.io.*;import java.util... 2024. 5. 12.
[백준] 2143: 두 배열의 합 - JAVA https://www.acmicpc.net/problem/2143 풀이배열 2개가 주어지고 배열들의 부 배열들을 합하여 T를 만들는 경우의 수를 찾는 문제이다. 두 가지 방법으로 풀 수 있는 문제였다. 첫 번째로 생각한 방법은 Map을 사용해 containsKey를 이용하는 방법이었다. 배열 A의 부 배열들의 합을 map에 저장해 놓는다. 배열 B의 부 배열의 합을 구하면서 T에서 뺀 값이 A의 map에 있다면 map의 value 만큼 카운트하여 더해준다. 이 방법으로 제출하고 다른 풀이들을 보니 이분 탐색으로 푸는 방법도 있었다. List에 부 배열들을 저장하고 이분 탐색을 위해 정렬한다. ListA에서 값을 꺼내면서 T - 꺼낸 값을 찾을 값으로 하여 ListB에서 이분탐색을 통해 찾는다. 개수가 여.. 2024. 5. 12.
[데이터베이스] [MySQL] 전문 검색(FullText Search) 전문 검색(FullText Search)컬럼에서 키워드로 검색하기위한 방법이다. 단어에서 일부만 일치하는 내용을 검색할 수 있다. 일부만 검색하는 경우에도 FullText인덱스를 사용할 수 있기 때문에 Like문을 이용한 조회보다 더 빠른 검색이 가능하다.  인덱싱 방식인덱싱 방식으로는 Stopword방식과 N-gram방식이 있다. StopwordStopword방식은 내용을 공백, Tab, 문장 기호를 구분자로 하며, 사용자가 정의한 문자열을 구분자로 할 수도 있다. 공백을 기준으로 나눈 단어들을 저장하여 완전히 일치한 단어만 결과에 포함된다. 예를 들어 테이블에 다음과 같이 저장이 되어있다고 하자. 1. 우리 집 강아지는 복슬강아지 2. 우리집 강아지는 복슬강아지 3. 우리집강아지는복슬강아지 "우리"이.. 2024. 5. 12.
[백준] 20303: 할로윈의 양아치 - JAVA https://www.acmicpc.net/problem/20303 풀이dp와 분리집합을 이용하는 문제. 사탕을 최대로 뺏어야 하는 문제였다. 친구들로부터 사탕을 뺏는데, K명 미만으로부터 사탕을 빼앗아야 한다. 한 친구의 사탕을 뺏으면 그와 친구인 친구들의 사탕을 함께 뺏는다. 각 친구별로 사탕의 개수를 알고 있고, 누구와 친구 관계를 갖고있는지 주어진다. 따라서, 분리집합(union-find)을 이용해 친구별로 그룹을 만들어 그룹별로 몇 명인지 몇 개의 사탕을 가지고 있는지 저장한다. 저장된 자료를 통해 배낭문제 알고리즘을 적용하여 최대 K-1명일 때 최댓값을 구했다.  메모리: 875636KB시간: 1152ms언어: Java 11import java.io.*;import java.util.*;pub.. 2024. 5. 12.
[백준] 23083: 꿀벌 승연이 - JAVA https://www.acmicpc.net/problem/23083 풀이경로의 개수를 세야 하는 DP문제. 벌집 구조이다. 아래쪽, 오른쪽 위, 오른쪽 아래 3가지 방향으로 이동할 수 있다. bottom-up으로 진행을 하면 오른쪽 위로 이동할 때 처리가 곤란할 것 같아서 top-down방식을 채택했다. dp배열의 초기값을 -1로 설정하고 -1이 아닌 경우에는 dp배열의 값이 설정되었다는 것이므로 dp배열의 값을 반환했다. 구멍뚫린 칸은 0으로, (1, 1)은 1로 설정했다. 현재 칸을 (r, c)라고 할때 c가 2의 배수인 경우와 아닌 경우 탐색 해야 하는 배열이 달랐다.if(c % 2 == 0) { return dp[r][c] = (doDp(r + 1, c - 1) + doDp(r, c - 1).. 2024. 5. 12.
[백준] 12850: 본대 산책2 - JAVA https://www.acmicpc.net/problem/12850 풀이결론부터 말하면 분할정복을 통해 행렬의 거듭제곱을 하는 문제였다. 각각의 포인트에서 연결된 길을 이차원배열에 저장했다. 초기 배열을 V1이라고 하면 V1[a][b]는 a에서 b로 1분만에 갈 수 있는 경로의 수를 의미한다. V1을 제곱한 것을 V2라고 하면 V2[a][b]는 a에서 b로 2분만에 갈 수 있는 경우의 수이다. 즉, Vx[a][b]는 a에서 b로 x분만에 갈 수 있는 경우의 수를 의미한다. 따라서 주어진 D만큼 V행렬을 제곱하여 V[0][0]을 구하면 D분만에 0에서 0으로 갈 수 있는 경우의 수이다. 분할정복은 doPow함수로 구현했고, 행렬의 곱셈은 multiply함수로 구현했다.  메모리: 14256KB시간: 124.. 2024. 5. 12.
[백준] 1717: 집합의 표현 - JAVA https://www.acmicpc.net/problem/1717 풀이자료구조, 서로소집합 문제. 집합들이 있고, 합집합연산과 서로 같은 집합인지 확인하는 연산이 있다. 배열을 집합의 개수만큼 만들고 자신의 번호로 초기화 한다. 자신의 그룹을 찾는 함수, 그룹을 합치는 함수, 같은 그룹인지 확인하는 함수 3가지를 구현해야 한다. 자신의 그룹을 찾는 findGroup 함수에서는 배열의 값을 findGroup의 결과값으로 갱신하면서 어떤 그룹에 속해있는지 찾는다. 그룹을 합치는 grouping 함수에서는 findGroup을 한 결과들을 이용해 두 집합을 하나의 그룹으로 묶어준다. 같은 그룹인지 확인하는 check 함수에서는 마찬가지로 findGroup을 한 결과가 서로 같은지 여부를 판단한다.  메모리: 5.. 2024. 5. 12.
[백준] 15729: 방탈출 - JAVA https://www.acmicpc.net/problem/15729 풀이그리디 문제. 불이 켜진 상태를 주어진 상태와 똑같게 만들어야 한다. 스위치는 자신과 오른쪽 두 개 스위치를 한번에 누르게 된다. 왼쪽부터 탐색할 때 이전 스위치에는 영향을 주지 않는다는 것. 왼쪽부터 오른쪽으로 탐색하며 정답과 상태가 다른 스위치만 눌러가며 카운트했다.  메모리: 77944KB시간: 440ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu.. 2024. 5. 12.
[백준] 14890: 경사로 - JAVA https://www.acmicpc.net/problem/14890 풀이구현 문제 였다. 이전 칸과 비교하여 체크해주는 문제. 높이가 이전과 같다면 지나갈 수 있고, 1 차이나면 경사로를 설치해야 한다. 경사로의 높이는 1로, 길이는 L로 고정되어 있어서 이전 칸과 1 차이날 때,  L길이의 for문을 통해 경사로를 놓을 수 있는지 탐색했다. 경사로의 바닥면의 높이가 다 같은지, 이미 설치된 경사로가 없는지 체크해 주었다. 이차원배열의 행과 열을 모두 체크해야 했다. 함수를 재사용 하기 위해 탐색할 부분을 일차원배열로 만들어 하나의 함수를 이용했다.  메모리: 15048KB시간: 144ms언어: Java 11import java.io.*;import java.util.*;public class Main .. 2024. 5. 12.
[백준] 1535: 안녕 - JAVA https://www.acmicpc.net/problem/1535 풀이DP, 배낭 문제. 인사를 할때마다 체력을 잃고 기쁨을 얻는다. 체력 100에서 시작해서 0이 되면 죽는다. dp배열을 dp[사람의 수][100] 으로 설정했다. 사람마다 잃는 체력, 얻는 기쁨을 통해 이전 dp배열과 비교해준다. 점화식은 다음과 같다.dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - L[i]] + J[i]);  메모리: 14196KB시간: 176ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 12.

티스토리툴바