본문 바로가기
  • 주니어 개발자의
    RESTful 성장기

Algorithm13

[찾아라 프로그래밍 마에스터 - 게임 맵 최단거리] 문제 https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 분석 및 해결 정말 대표적인 BFS, DFS 그래프 탐색 문제였습니다. 하지만 최단 거리를 구할 때는 BFS가 짱짱맨이므로 BFS를 이용했다 import java.util.*; class Solution { public static int[] dy = {-1, 1, 0, 0}; public static .. 2021. 7. 26.
[연습 문제 - 이상한 문자 만들기] 문제 https://programmers.co.kr/learn/courses/30/lessons/12930 코딩테스트 연습 - 이상한 문자 만들기 문자열 s는 한 개 이상의 단어로 구성되어 있습니다. 각 단어는 하나 이상의 공백문자로 구분되어 있습니다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 programmers.co.kr 분석 및 해결 전체 문자열은 하나 이상의 공백을 기준으로 여러 개의 단어로 이루어져 있다. 여기서 중요한 포인트는 1개 정도로 볼 수 있다. 1. 주어진 문자열 s의 전체 인덱스를 기준으로 하는 것이 아닌 문자열 s에 포함되어 있는 문자열 각각에 대해서 이상한 문자를 구할 것. import java.util.*; class Solution { .. 2021. 7. 25.
[찾아라 프로그래밍 마에스터 - 포켓몬] 문제 https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 분석 및 접근 해당 문제는 단순히 중복을 제거한 후, 가져갈 수 있는 최대 포켓몬의 수를 구하는 문제이다. 중복을 제거할 수 있는 다양한 방법이 존재하겠지만, 필자는 Set Collection을 사용했다. Set은 Map과는 다르게 중복된 값을 가지지 않기 때문이다. 결론적으로, 포켓몬의 종류가 담긴 배열의 값을 모두 Set 변수에 담은 후 Set에 저장.. 2021. 7. 25.
[9935 문자열 폭발] 문제 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 접근 및 풀이 처음에 이 문제를 봤을 때는 너무나 당연하게 Cpp의 경우 find, Java의 경우 contains를 사용해 폭발 문자열이 존재하지 않을 때까지 기준 문자열에서 폭발 문자열을 삭제하면 되지 않나 싶었다. 하지만 그렇게 간단할 리가 있나.. 그렇게 접근하고 풀게 되면 당연하게 메모리초과 혹은 시간초과가 발생하게 된다. 그렇다면 어떻게 해야하는가? 만만한 게 스택이.. 2021. 7. 5.
[1446 지름길] 문제 - www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 분석 및 해결 단순한 bfs 문제였다. 지름길이 항상 |지름길 도착 위치 - 지름길 시작 위치| 보다 짧은 것은 아니라는 점을 주의해야 한다. 따라서, bfs를 통해 지름길을 이용하는 경우, 이용하지 않는 경우 모두에 대해서 탐색을 시도했다. 각 위치마다 모두 지름길을 가지고 있을 수도 있지만, 그렇지 않은 경우가 더 많을 거 같아 Map을 사용해서 graph를 구현했다. 소스 코드 impo.. 2021. 4. 15.
[18119 단어 암기] 문제 - www.acmicpc.net/problem/18119 18119번: 단어 암기 준석이는 영어 단어를 외우려고 한다. 사전에는 N가지 단어가 적혀 있다. 모든 단어는 소문자이다. 단어 안에 있는 모든 알파벳을 알 때, 그 단어를 완전히 안다고 한다. 다음과 같은 쿼리들이 주 www.acmicpc.net 분석 및 해결 기억하고 있는 알파벳의 상태가 매번 바뀌며, 알고 있는 알파벳 상태를 기준으로 N개의 쿼리에 대해 탐색을 실행해야 한다. 따라서, 쿼리의 개수 최대 10,000개, 각 쿼리의 최대 길이 1,000, 알고 있는 알파벳 상태의 변화 최대 10,000번이므로 최대 10의 11승으로 단순하게 반복문을 돌리게 되면 시간 초과가 발생하게 된다. 이런 경우, 비트마스킹을 사용하게 되면 탐색 시간을.. 2021. 4. 14.
[1715 카드 정렬하기] 문제 - www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 분석 및 해결 비교 횟수를 최소로 하기 위해서는 비교하는 대상 A, B의 합이 항상 가장 작아야 한다. 이 말은 즉, 카드들 중에서 가장 작은 묶음 2개를 선택하면 된다. 비교 이후, 합쳐진 카드 묶음은 새로운 카드 묶음이 되고, 하나의 카드 묶음이 될 때까지 앞의 과정을 반복해주면 된다. 우선순위 큐를 사용해 합쳐진 카드 묶음을 카드 묶음 목록에 추가함과 동시에 정렬이 되게 하면 문제를.. 2021. 4. 10.
[2075 N번째 큰 수] 문제 - www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 분석 및 해결 처음에 봤을 때는 뭔가 대단한 수학적 사고를 요하는 것 같았지만, 우선순위 큐를 이용해 쉽게 풀 수 있었다. 2차원 배열의 모든 원소를 우선순위 큐에 삽입하고, N번만큼 뽑아내면 된다. 소스 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Collections; import java.util... 2021. 4. 6.
[7795 먹을 것인가 먹힐 것인가] 문제 - www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 분석 및 해결 쉽게 말해 A배열 모든 원소에 대해서 B배열에서 자신보다 작은 원소들의 개수의 합을 구하는 문제이다. 지난 번에 포스팅한 '순위 검색'에서의 이분 탐색을 적용해 해결했다. 소스 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Array.. 2021. 4. 6.

티스토리툴바