Algorithms

[Graph+BFS] 백준 7576 토마토

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 카테캠 코테에서 출제된 문제와 매우 유사해서 기록해둔다. 그땐 시간이 없어서 침착하게 조건 체크를 못했는데, 다시한번 이 문제로 풀이 방식을 점검해보았다. 꼭 이런 류의 문제 풀이 방식에 익숙해지도록 하자. package baekjoon; import java.io.*; import java.util.*; public class Main { //창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수 //모든 토마토가 익어있는 상태..

그래프 이론 톺아보기

그래프 이론 트리와 그래프의 차이점 그래프는 트리와 다르게 루트노드가 없고 부모-자식 관계가 없다. 인접 리스트 or 인접 행렬로 구현된다. 들어가기 앞서, 다익스트라 알고리즘은 인접 리스트로, 플로이드-워셜 알고리즘은 인접 행렬로 구현된다. 다익스트라 알고리즘 현재까지 알려진 것 중, 가장 짧은 거리에 있는 노드를 선택하기가 핵심. → 그리디 알고리즘에 속함. 왜 인접 리스트로 구현되는 것이 유리한가? 모든 노드 쌍에 대하여 공간 만들지 않아도 되기 때문에 메모리가 효율적이라는 점. 연결된 노드를 찾기 위해 모든 노드를 탐색할 필요가 없다는 점 다익스트라 알고리즘은 시작 노드 지정 작업이 필요하다. 방문 여부를 체크하는 배열 또한 필요하다. → 아직 방문하지 않은 노드 중 최소 거리를 가진 노드를 찾고..

[투포인터] 백준 20922 겹치는 건 싫어

20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 시간초과 코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringToke..

[백트래킹] 눈덩이 굴리기, 근손실, 1,2,3 더하기 2

21735 눈덩이 굴리기 21735번: 눈덩이 굴리기 눈송이들이 많은 동네인 숙명여대 앞마당에서 눈사람 만들기 대회를 연다. 앞마당의 길이는 $N$이고 위치 $1$부터 위치 $N$ 까지만 눈이 쌓여있다. 위치 $i$에 눈이 $a_i$만큼 쌓여있다. 대회 규칙은 www.acmicpc.net //size=눈덩이크기, pos=이동거리, time=소요시간 function back(size, pos, time){ if(pos == N or time==M) { answer = max(answer, size) } } if(i == 1) back(size+a[pos+i], pos+i, time+1) if(i==2) back(size/2+a[pos+i],pos+i, time+1) } 끝까지 도달하거나, 시간이 다 될 때..

[Greedy] 백준 2141 우체국

2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 해당 문제는 1시간 정도 고민하고 코드를 짜면서 도전했는데 이중for문을 써서 계속 시간 초과가 떴다. 이후에 이중for문을 사용하지 않는 다른 방법도 시도해 보았지만 점점 산으로 가는 것 같아서 결국 다른 분 코드를 참고했다. 풀이를 보자마자 아! 했다. 그리디 문제는 아이디어를 떠올리는 것이 가장 어려운 것 같다. 그리디로 풀 때는 구하고자 하는 것에 집중하면서 푸는 연습을 해..

[Greedy] 연속되는 조건이 있는 문제

연속되는 조건이 있는 문제 백준 20365 - 블로그2 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 해당 문제에서 가장 중요한 조건은 연속된 임의의 문제들을 선택한다는 것이다. 이러한 조건이 나오면 연속되는 문자를 하나의 집합으로 생각하고 중복되는 문자들은 제거해주고 저장해주자. 나는 굳이 배열을 쓰지 않고 StringBuilder(sb)만 사용해서 입력 받을 때 문자가 달라지는 경우만 Stringbuilder에 append 해주었다. 이렇게 되면 sb에는 BBR과 같이 연속되는 문자가 절대 존재하지 않게..