Algorithm94 [알고리즘 문제풀이] 백준 16172 나는친구가적다(Large) / JAVA코드 https://www.acmicpc.net/problem/16172 16172번: 나는 친구가 적다 (Large) 첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 www.acmicpc.net 참조 개념 2022.01.12 - [Algorithm/개념] - [알고리즘 개념] KMP - 문자열 검색 알고리즘(JAVA 코드) /** * * KMP 사용 풀이 * * 1. 정규식으로 숫자 제거(replaceAll 시간복잡도 O(N)) * * 2. KMP 실행 O(N+M) * * 총 시간복잡도 O(N+M) */ import java.util.*; impor.. 2022. 1. 17. [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java 세그먼트 트리란 특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리. ex) 특정 구간 합,최소값,최대값,평균값 등등 Segment : 부분.분할.나누다.분할하다. 시간복잡도 데이터 변경: O(logN) 연산: O(logN) 데이터 변경할때마다 M번 연산: O((logN +logN)*M) = O(MlogN) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 어떤 N.. 2022. 1. 17. [알고리즘 문제풀이] 백준 2098 외판원순회 (JAVA코드) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 실패해서 타 블로그들을 참조해서 풀은 문제 /** * * 실패 ㅠ * * 본인에서 시작해서 본인으로 돌아오는 가장 적은 비용을 쓴 경로 * * 외판원 순회 알고리즘 사용.. * * DP + dfs + 비트마스킹 * * DP[현재도시][방문했던도시정보(bit)] = 이후에 방문하는것들 포함한 최소비용 * * 어느 도시에서 출발했던지 최소비용 사이클을 찾는거기때문.. 2022. 1. 16. [알고리즘 문제풀이] 백준 2234 성곽 (JAVA코드) https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net /** * * 비트마스크 문제 * * 성의 크기와 각 벽의 위치가 주어짐 * * 1. 각 벽을 비트단위로 해당위치 저장 * * 2. bfs로 방 개수 파악 및 방 별 넓이 확인 * 1) visited에 현재 위치가 몇번방인지 저장 * 2) 해시맵에 방번호 : 방사이즈로 저장 * * 3. visited(현재위치 방번호)를 4방향 돌면서 다른 방 만났을때, * 현재방 사이즈 + 다른방 사이즈가 .. 2022. 1. 16. [알고리즘 문제풀이] 백준 1701 Cubeditor (JAVA코드) https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 관련 개념 : KMP 2022.01.12 - [Algorithm/개념] - [알고리즘 개념] KMP - 문자열 검색 알고리즘(JAVA 코드) /** * * 문자열 문제 * * 1. kmp 알고리즘 중 부분 문자열 내부에 패턴 파악 코드 사용 * * 2. 패턴 경계 길이 중 가장 긴 것 출력 * * 3. 하지만 기존 코드로는 앞에서부터만 체크하니, 전체 문자열 .. 2022. 1. 15. [알고리즘 개념] 비트마스크(Bitmask) 비트 마스크를 설명하기 앞서, 비트를 알아야한다. 잘 알면 아래부터 보면 됨! 더보기 비트(Bit) 컴퓨터는 이진수를 통해서 모든 자료를 표현한다. 여기서 사용하는 이진수가 데이터의 최소 단위 Bit(binary Disit)이다. 비트는 0 또는 1의 값을 가지며, n개의 비트는 2^0~2^n-1까지 표현 가능하다. 1 = 2^0 = 1 10 = 2^1 = 2 100 = 2^2 = 4 111 = 2^2+2^1+2^0 = 7 3자리의 비트는 1~2^n-1 까지 표현가능 비트 연산자 및 용어 정리 최상위 비트(MSB): 2^n-1 비트 최하위 비트(LSB): 2^0 비트 비트가 켜져있다: 1 비트가 꺼져있다: 0 int는 4byte 총 32비트로 되어있다. ( 최상위 비트는 부호비트 1: -, 0:+) in.. 2022. 1. 14. [알고리즘 문제풀이] 백준 2667_단지번호붙이기(JAVA) https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net /** * dfs& bfs 풀이(bfs 사용) * * 1. 지도를 돌면서, 집을 만나면 bfs 실행 * * 2. bfs로 방문여부 및 개수 파악(각 번호 카운트 증가) * * 3. bfs 종료 시 각 카운트 번호 출력 * * 4. 다시 지도 돌면서 체크(방문여부로 체크된 곳은 건너뛰기) */ import java.util.*; import java.io.*; public class BJ2667_단지.. 2022. 1. 14. [알고리즘 문제풀이] 백준 1992 쿼드트리(JAVA) https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net /** * 분할정복 문제 * * 1) 숫자 파악 * * 2) 전체 숫자가 같지 않으면, 4분할 * * 3) 각 분할정보를 기록 */ import java.util.*; import java.io.*; public class BJ1992_쿼드트리 { public static int[][] arr; public static BufferedWriter bw = new BufferedWrit.. 2022. 1. 14. 이전 1 ··· 8 9 10 11 12 다음
