본문 바로가기

알고리즘

 (56)
백준 20127 <Y-수열> 이 문제는 어떻게 흐름을 파악하고 문제에서 말하는 것이 무엇인가! 하는 문제이다. 이 문제의 핵심은 앞에 있는 수열을 뒤로 옮겨서 증가, 또는 감소가 되는지이다. 즉 앞에 있는 수열을 최대 한번! 이동하는 것이다. 이 문제를 생각해보면 n^2 해서도 풀 수 있지만 그렇게 된다면 100만의 제곱! 시간 초과이다. 즉 n번의 탐색으로 증가가 되는지, 또 n번 돌려서 감소가 되는지를 찾는 문제이다. 문제 풀이 증가수열 먼저 --> 탐색하면서 감소하는 구간 있으면 count를 증가 현재까지의 증가수열 개수를 저장 count가 1 넘으면 한 번만으로 안됨 return 1번이면 맨 처음 수와 맨 마지막 비교해서 맨 처음수가 맨 마지막보다 작으면 증가수열 개수를 result로, 0 이면 result=0 감소 수열 -..
백준 8972 <미친 아두이노> 일반적인 시뮬레이션이다. 이러한 문제는 삼성에 나올법한 유형은 문제이기 때문에 풀어보길 추천한다. 문제 풀이 종수의 아두이노를 움직인다. 미친 아두이노와 만나면 return 미친 아두이노가 담긴 queue를 이용해 8방향으로 움직여보고 가장 짧은 거리로 이동 새로운 맵에 체크를 한다. 만약 종수 아두이노와 만났다 return 미친 아두이노의 위치에 왔다 그 자리를 B--> 터짐 표시를 한다. 새로운 맵을 기존 맵에 옮기면서 미친 아두이노가 터지지 않았다면 queue에 담아준다. 이 그림 처럼 계속 진행해주면 풀리는 문제이다. 미친 아두이노를 queue에서 꺼내서 이동해준다. 미친 아두이노의 다음 위치를 체크해주는 과정 생존한 미친 아두이노를 큐에 다시 넣어준다. 이 과정을 반복하면 해결할 수 있는 문제이..
백준 11967 <불켜기> 그래프 문제이긴 하지만 일반적인 BFS와 DFS랑은 다르게 생각이 필요한 문제였다. 이동을 할 때 불이 켜져 있으면 이동이 가능하기 때문에 이동을 할 수 있는 위치가 불이 켜져 있으면 계속 진행해주도록 생각해줘야 하는 문제이다. 문제 풀이 큐에서 꺼내 그 지점에서 불을 켜준다. 그리고 이동한 장소에서 4방향을 갈수 있다고 표시해준다. 이동할 장소를 표시한 이차원배열에서 불이 켜져 있고 방문을 안 했고 이동할 수 있다면 큐에 넣어준다. 즉 불을 키고 이동할 장소인지 계속 찾아주는 전체 탐색인 것이다. 생각해보니 총 맵의 크기가 100*100 이므로 제곱을 돌아도 1억이므로 시간이 넘치지 않는다. 이러한 예제가 주어진다면 처음 시작은 이러할 것이다. 이런 흐름으로 진행 될것이고 2,2는 킬 수 있는 것이 없..
백준 1525 <퍼즐> 이 문제는 어떻게 하면 메모리를 효과적으로 관리하면서 방문처리를 해주는가에 집중이 필요한 문제였다. 그래서 나는 이문제의 맵의 상태를 String으로 만들어 hashmap에 관리함으로써 메모리를 줄여 나갔다. 문제 풀이 각각의 맵의 상태를 String으로 저장해서 count와 함께 현재 비어있는 위치를 보관하는 class를 선언했다. 비어있는 위치에서 4방향으로 검색한 뒤 string으로 만들고 hashmap에 저장되어있으면 패스하고 저장 안 되어있으면 hashmap에 넣어주고 queue에도 넣어주었다. 현재 상태를 배열그대로 저장하게 되면 메모리를 많이 차지하기 때문에 줄여주었다. 다음 방향 숫자와 현재 위치의 0을 바꿔주고 string으로 출력하는 과정이다. 이러한 과정이 계속 반복되고 결과와 같다면..
백준 1756 <피자 굽기> 문제 풀이 1. 오븐의 깊이를 위에서부터 넣으면서 현재까지 가장 좁은 길이를 다음 깊이에 넣는다. 2. 이분 탐색을 이용해서 피자를 어디 위에 올릴 수 있는지 알아낸다. 3. 피자를 올린 깊이와 맨 위의 깊이 사이를 계속해서 이분 탐색한다. 4. 올릴 수 없다면 음수가 될 것이다. 생각이 많이 필요했던 문제 중 하나이다. 골드 5라는 수준을 못 믿었던... 일단 문제를 보면 완 탐으로 풀면 되지 않을까? 했지만 그렇게 되면 300000^2 이므로 당연히 터진다. 그렇다면 생각할 부분은 어떻게 자신보다 크거나 같은 아래쪽에 넣을 수 있을까를 먼저 생각해야 한다. 문제 풀 결국은 위에서 넣었을 때 자신보다 작은 지점 바로 위층에 쌓이게 되는 것이다. 이 지점을 찾는 것은 의외로 생각만 한다면 간단해질 것이다..
백준 14698 <전생했더니 슬라인 연구자였던 건에 대하여(HARD)> 이 문제의 핵심은 어떻게 큰 수를 적게 곱하는가이다. 이렇게 슬라임이 있다면 이렇게 이렇게 작은 수를 먼저 곱하는 게 적절할 것이다. 그러므로 작은수끼리 먼저 곱하는 게 적절하니 우선순위 큐를 사용하면 되는 문제이다. 이 문제에서 어려웠던 점은 long값의 계산이었다. 이러한 값이 넘어가는 것을 잘 처리한다면 쉽게 풀리는 문제 유형이다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; public class Main { static int divide=1..
swea 1868 <파핑파핑 지뢰찾기 > swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이 문제는 DFS 또는 BFS 문제의 심화 문제이다. 이문제에서 알아야 할 것은 어디를 먼저 클릭해야 더욱 많이 퍼지는 가이다. 이것을 알아보기 위해서 이 그림을 보자 이 모양을 보면 알 수 있듯이 지뢰가 8방향으로 없는 곳을 먼저 터트리게 되면 계속해져 퍼질 수 있다. 문제 풀이 클릭할 수 있는 위치를 모두 Queue 에 넣는다...
swea 5643 <[Professional] 키 순서> swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXQsLWKd5cDFAUo&categoryId=AWXQsLWKd5cDFAUo&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이문제는 DFS, BFS를 하는 심화과정의 문제이다. 신선한 문제이므로 한번 풀어보는 것을 추천한다. 이문제를 푸는 방법은 2가지가 있다. 이 문제의 핵심은 자기보다 작은 것이 몇 개인지, 그리고 자신보다 큰 것들이 몇 개 있는지를 판단하는 문제이다. 첫번째 방법 자신보다 큰 인원들을 담는 ArrayList와 자신보다 작은 인원을 ..
백준 10800 <컬러볼> 이 문제는 각각 모든 수를 탐색한다고 하면 200000*200000=N^2 이므로 시간 초과가 난다. 이 문제는 가장 작은수또는 가장 큰 수부터 시작해서 자신의 색을 제외하고 나머지의 합을 구하는 그런 문제이다. 즉 그러기 위해서는 누적합이라는 것을 이용해야한다. 문제 풀이 각각의 색마다 총합을 저장한다 --> 배열에 저장 자신의 번호와 색, 크기를 담은 배열을 크기순으로 정렬한다. 뒤에서부터 자신의 색을 제외한 다른 합의 값을 자신의 번호에 저장한다. 이때 주의할 점은 같은 무게를 따로 처리해야 한다는 것이다. 이렇게 다음을 계산할 준비를 한다. 3번 과정에서 이렇게 흐름으로 흘러가게 된다. 이때 조심해야 할 것은 다음 꺼낼 것도 크기가 같은 경우가 있기 때문에 Queue에 같은 무게들을 넣어서 처리를..
SWEA 5656 <[모의 SW 역량테스트] 벽돌 깨기> swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo&categoryId=AWXRQm6qfL0DFAUo&categoryType=CODE&&& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이러한 문제는 삼성 역량테스트에 주로 나오는 시뮬레이션 유형이다. 문제 풀이 W, 열의 개수 중에 N개를 중복 조합으로 선택한다. 그 위치에 구슬을 떨어트린후 BFS로 이어나가면서 터트린다. 벽돌을 바닥까지 내려준다. 남아있는 개수가 가장 작은 수를 출력한다. 이 문제는 이렇게 적으면 간단하지만 중간에 실수를 하게 되면 꼬이게..

티스토리툴바