본문 바로가기

🔎 Algorithm/💻 문제 풀이16

[백준] 2493. 탑 문제 풀이 처음에는 배열의 끝에서부터 탐색을 시작해서 자신보다 큰 값을 만날 때까지의 모든 요소들을 같이 초기화하는 방식을 생각했다. 하지만 이 경우에는 아래 방향의 화살표 모양(ex. 5 2 1 3 4) 경우를 커버하지 못해서 다른 방법을 생각해봤다. 최종적으로는 스택 두개를 사용해서 하나의 스택(A)은 입력 순서대로 들어가 있고 나머지(B)는 꺼낸 값을 저장했다. 꺼낸 값을 B 스택에 넣기 전에 B스택의 top이 더 작은 경우에는 꺼낸 값의 인덱스가 top의 결과가 된다. 인덱스를 찾는 방법에 대해서는 Map을 통해서 초기 입력시 해당 값을 key로 인덱스를 value로 저장해서 O(1)로 찾을 수 있도록 했다. Map을 통한 구현 import java.io.BufferedReader; import .. 2021. 2. 4.

[백준] 1436. 영화감독 슘 문제 풀이 찾은 규칙은 다음과 같다. prefix를 0부터 시작해서 유지하고 1사이클이 끝나면 prefix를 증가시킨다. 처음 0~5까지는 prefix와 666사이에 붙힌다. ex) 1666, 2666, 11666 prefix 6이 나오면 뒤에서 만들 수 있는 조합의 개수가 늘어남 ex) prefix 1 => 뒤에 10개 / prefix 16 ⇒ 뒤에 100개 / prefix 166 ⇒ 뒤에 조합 1000개 결론은 1사이클은 6 + (10^prefix의 6의 개수) + 3 의 규칙을 가지게 된다. 다 푼뒤에 생각해보니 Input이 작아서 1부터 모든 수를 돌며 666이 포함될 경우 카운트 하는 방법도 가능할 것 같다. import java.util.Scanner; public class Solution .. 2021. 2. 3.

[백준] 1018. 체스판 다시 칠하기 문제 풀이 처음에는 입력의 크기를 주의깊게 보지 않아서 완전탐색의 방식을 생각하지 못했다. 다른 방법을 아무리 생각해봐도 떠오르지 않아서 천천히 다시 생각해봤는데 N과 M의 범위가 50이고 가능한 모든 8x8 정사각형을 검사하더라도 충분히 커버 가능하다고 생각해서 완전탐색으로 풀었다. 완전탐색을 할 때, 처음 시작이 W인 경우와 B인 경우 모두 수행하도록 했다. 조금 헤맸던 부분은 prev를 유지하면서 prev와 현재 값이 같으면 카운트를 해주는 방식으로 구현했는데 줄이 바뀔 때마다 prev의 값이 한 번 더 변경되어야 하는 부분이었다. 그래서 처음 행을 제외한 모든 행의 첫 열은 prev를 한 번 더 변경해주는 방식으로 구현하였다. 구현 코드는 아래와 같다. import java.io.BufferedR.. 2021. 2. 2.

[백준] 2146. 다리 만들기 문제 풀이 먼저 각 섬을 구분하기 위해 1이 아닌 수(2,3,4...)로 초기화 시켜주었다. 그런 다음 각 섬마다 탐색을 진행함에 있어 시작 집합을 섬의 경계 (주위에 0이 존재하는 칸)를 잡고 다른 섬을 만나기 전까지 bfs를 수행하면서 최소거리를 구하는 방식으로 진행했다. 여기서 distance가 증가하는 시점에 대해서 고민을 많이 했는데 아래 코드처럼 BFS의 Level을 판단하기 위해 초기 bounday의 사이즈를 구하고 이에 대해서 반복문을 도는 방식으로 Level을 판단했다. 그리고 초기 풀이는 50%가 넘어갈 때 메모리 초과가 발생했는데, BFS를 수행할 때 visited를 체크하지 않아서 많은 중복이 발생했던 것이 문제였다. 그리고 visited를 갱신하는 위치가 current의 시점에서 .. 2021. 2. 2.

이전 1 2 3 다음

티스토리툴바