본문 바로가기

알고리즘 공부 및 문제 풀이/백준(BOJ)

 (220)
[boj] 백준 20207 달력 (Java) - 그리디 [문제] https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net [풀이] s~e일까지 cnt를 증가시켜준다. 캘린더의 일정이 끊이지 않고 연속된 길이가 잘라야 할 코팅지의 width가 되고 이때의 height는 그 날의 최대 일정의 수이다. [코드] package 그리디; import java.util.*; import java.io.*; public class boj_20207_달력 { static int n; static int[] cnt; public sta..
[boj] 백준 1548 부분 삼각 수열 (Java) - 완전탐색 [문제] https://www.acmicpc.net/problem/1548 1548번: 부분 삼각 수열 세 수 x, y, z가 x+y>z, x+z>y, y+z>x의 관계를 만족하면, 세 수는 삼각관계에 있다고 한다. 마찬가지로 길이가 N인 수열 B(b[0], b[1], ..., b[n-1])의 모든 b[i], b[j], b[k]가 삼각관계에 있으면 이 수열은 삼각 www.acmicpc.net [풀이] 먼저 삼각관계를 이루기 위해서는 오름차순으로 정렬했을 때 인덱스가 0, 1, ...., k 에 대해서 arr[0]+arr[1] > arr[k] 를 만족해야 한다. 가장 작은 두 수의 합이 가장 큰 수보다 크다면 세 수 x, y, z에 대해서 x+y>z, x+z>y, y+z>x의 관계를 만족할 것이기 때문이다..
[boj] 백준 17413 단어 뒤집기 (Java) - 스택 [문제] https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net [풀이] 스택을 이용해서 태그가 아닌 단어가 나오면 뒤집어서 저장해준다. [코드] package heap_stack_dequeue; import java.io.*; import java.util.*; public class boj_17413_단어뒤집기 { static String s; public static void main(String[] args) t..
[boj] 백준 15661 스타트 링크 (Java) - 완전탐색 [문제] https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net [풀이] 이런 조합+완전탐색 유형의 문제가 최근 코테에 꼭 한 문제씩은 출제되는 것 같다.. 팀은 1명 이상으로 구성되면 된다. 따라서 1명~n/2명까지의 팀원에 대해서 선택될 수 있는 모든 조합을 찾는다. 예를 들어 6명이면 3명을 뽑는 조합까지만 구하면 된다. 그 이후 4명을 뽑는 조합은 어차피 2명을 뽑는 조합에서 구해졌을 것이기 때문에...
[boj] 백준 12933 오리 (Java) - 그리디 [문제] https://www.acmicpc.net/problem/12933 12933번: 오리 첫째 줄에 영선이가 녹음한 소리가 주어진다. 소리의 길이는 5보다 크거나 같고, 2500보다 작거나 같은 자연수이고, 'q','u','a','c','k'로만 이루어져 있다. www.acmicpc.net [풀이] 연속되는 'quack'을 찾아 '.'으로 치환시켜주고 전체 문자열 개수에서 5씩 차감시킨다. 연속되는 'quack'을 찾을 수 있다면 오리 개수를 증가시키고, 이후 남은 문자 개수가 0이라면 정답을 출력한다. 연속되는 'quack'을 찾을 수 없다면 잘못된 오리 울음이므로 -1을 출력한다. quqacukqauackck ..q..u..a....ck //처음 for문 돈 이후 ............... ..
[boj] 백준 2615 오목 (Java) - 완전탐색 [문제] https://www.acmicpc.net/problem/2615 [풀이] 완전 탐색 문제인데..신경써야 할 부분이 몇 가지 존재한다. 1. 오목이 완성될 경우, 가장 왼쪽에 있는 돌의 좌표를 출력해야 한다. 이를 위해서 탐색 시 j가 증가하는 순 -> i가 증가하는 순으로 2중 for문을 돌린다. 방향도 기준점이 가장 왼쪽이 되도록 오른쪽, 아래쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선 4 방향으로 정하였다. 2. 육목인 경우를 포함해서는 안된다! 따라서 반대 방향에 대해서도 탐색을 진행해서 cnt를 증가시켜 준 후 오목인지 비교해야 한다. 그렇지 않으면 한쪽 방향으로 오목이 완성되어 정답으로 출력할 수 있다...코테에서 히든테케였으면 오백퍼 걸렸을 것 같은 함정..ㅎ [코드] package..
[boj] 백준 1890 점프 (Java) - dp [문제] https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net [풀이] 가장 왼쪽 위 칸에서 시작해서 아래쪽, 오른쪽으로만 이동 가능하다. 가장 왼 쪽 윗 칸에서 이동한 경우만 dp에 반영해주기 위해 dp[0][0] = 1로 둔다. 2중 for문을 돌면서 아래로 이동할 수 있는 경우, 즉 i+move가 범위 안에 있는 경우 dp[i+move][j] += dp[i][j] 이고, 오른쪽으로 이동할 수 있는 경우, 즉 j+move가 범위 안에 ..
[boj] 백준 2346 풍선 터뜨리기 (Java) - Deque [문제] https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net [풀이] 1. 첫번째 풍선을 터뜨리고 이동 칸수를 얻는다. 2. 이동 칸 수가 양수이면 이동 칸 수 - 1 동안 Deque의 앞에 있는 숫자를 뒤로 이동시킨다. 그 후 가장 앞에 있는 풍선을 터뜨린다. 3. 이동 칸 수가 음수이면 -(이동 칸 수) -1 동안 Deque의 뒤에 있는 숫자를 앞으로 이동시킨다. 그 후 가장 뒤에 있는 풍선을 터뜨린다. Deque이 비어있지 ..

티스토리툴바