devInfo

[프로그래머스/Java] 1,2,3 떨어트리기

문제 https://school.programmers.co.kr/learn/courses/30/lessons/150364 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 해당 문제는 특정 알고리즘 문제가 아닌 구현 문제로 판단하여 모든 기능을 차례대로 구현했다. 그 과정에서 숫자를 어떤 순서로 내려야하는지 많은 고민을 했다. 결과만 말하자면 계속 임의의 수를 내려보내 받은 숫자의 개수를 저장하고, 이를 target 숫자를 만들수 있냐 없냐로 분기처리하였다. 우리가 떨어뜨릴 수 있는 숫자는 1,2,3밖에 없으므로 아래와 같은 공식으로 모든 노드가 ..

[백준/Java] 17472: 다리 만들기 2

문제 풀이 해당 문제는 그래프 탐색, 브루트포스, 최소 스패닝 트리 알고리즘을 모두 사용해야 풀 수 있는 문제이다. 1. 섬의 개수 확인 및 섬 넘버링 : 그래프 탐색 2. 각 섬의 거리 구하기 : 브루트포스 3. 최소의 길이의 다리 구하기 : 최소 스패닝 트리 1. 섬의 개수 확인 및 섬 넘버링 : 그래프 탐색 int[][] visited = new int[N][M]; int count = 1; for(int y = 0; y < N; y++) { for(int x = 0; x < M; x++) { if(board[y][x] == 0 || visited[y][x] != 0 )continue; ArrayDeque dq = new ArrayDeque(); dq.add(new Pos(x,y)); while(!..

[백준 / Java] 2110번: 공유기 설치

문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는..

[백준/Java] 1517번: 버블 소트(병합 정렬[Merge Sort])

문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다. 입력 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |..

문자열 매칭 알고리즘(KMP)

문자열 매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다. 워드파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 단순 문자열 알고리즘 가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다. 검색할 문자열 ABDEGH 찾는 문자열 DE 가장 앞부분부터 찾는 문자열이 매칭될 때 까지 탐색을 시작한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어졌으면 탐색을 종료한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 이 알고리즘은 이중포문으로 시간복잡도..

[백준 / Java] 1194번: 달이 차오른다, 가자.

문제 지금 민식이가 계획한 여행은 달이 맨 처음 뜨기 시작할 때 부터, 준비했던 여행길이다. 하지만, 매번 달이 차오를 때마다 민식이는 어쩔 수 없는 현실의 벽 앞에서 다짐을 포기하고 말았다. 민식이는 매번 자신의 다짐을 말하려고 노력했지만, 말을 하면 아무도 못 알아들을 것만 같아서, 지레 겁먹고 벙어리가 되어버렸다. 결국 민식이는 모두 잠든 새벽 네시 반쯤 홀로 일어나, 창 밖에 떠있는 달을 보았다. 하루밖에 남지 않았다. 달은 내일이면 다 차오른다. 이번이 마지막기회다. 이걸 놓치면 영영 못간다. 영식이는 민식이가 오늘도 여태것처럼 그냥 잠 들어버려서 못 갈지도 모른다고 생각했다. 하지만 그러기엔 민식이의 눈에는 저기 뜬 달이 너무나 떨렸다. 민식이는 지금 미로 속에 있다. 미로는 직사각형 모양이고..