알고리즘 공부 및 문제 풀이 (317) 썸네일형 리스트형 [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이 비어있지 .. [boj] 백준 16508 전공책 (Java) - 완전탐색 [문제] https://www.acmicpc.net/problem/16508 16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net [풀이] 정석적인 완전탐색 문제~ 전공책을 선택하는 경우, 선택하지 않는 경우 2가지에 대해 모두 dfs를 돌려준다. 전공책을 선택하는 경우 해당 전공책의 포함된 모든 알파벳들을 1씩 증가시켜 준다. 모든 전공책에 대한 선택이 끝난 후, 선택된 전공책들에 포함된 알파벳들의 select[] 값이 만들고자 하는 문자열의 알파벳들인 count[] 보다 작은 값이 존재한다면 불가능한 조합이므로 fa.. [boj] 백준 14501 퇴사 (Java) - 완전탐색 [문제] https://www.acmicpc.net/problem/14501 [풀이] 경우는 2가지이다. 1. 상담을 하는 경우. 그날의 비용과 그 다음 할 수 있는 상담일로 이동한다. 2. 상담을 하지 않는 경우. 비용 합은 그대로이고, 다음 날로 이동한다. 상담일이 n일을 벗어나면 안되기 때문에 범위를 체크해준 후 dfs를 호출했다. [코드] package 브루트포스; import java.util.*; import java.io.*; public class boj_14501_퇴사 { static int n; static int[] ti; static int[] pi; static int answer = -1; public static void main(String[] args) throws Exce.. [pro] 프로그래머스 SQL level4 입양 시각 구하기(2) - GROUP BY, RECURSIVE CTE [문제] https://school.programmers.co.kr/learn/courses/30/lessons/59413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 0~23 의 모든 시각이 나타나야 한다. 이를 위해 재귀 쿼리 기법을 이용해서 가상 테이블을 만들어 둘 수 있다. 재귀 쿼리 기법 WITH RECURSIVE cte AS ( -- Non-Recursive 문장(첫번째 루프에서만 실행됨) SELECT 1 AS n UNION ALL -- (반드시 필요) -- Recursive 문장 SELECT n + 1 AS num FROM cte .. 이전 1 2 3 4 5 ··· 40 다음