📚 문제 1802번: 종이 접기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 1000보다 작거나 같은 자연수이다. 둘째 줄부터 T개의 줄에 각각의 종이가 어떻게 접혀있는지가 주어진다. 종이의 정보는 문자열로 주어지며, 1 www.acmicpc.net 🔍 아이디어 종이의 반을 접는 경우 A | B 와 같다면 A와 B는 접는기준으로 대칭적이라는 특징이 있다. 해당 특징을 이용하여 중간점을 기준으로 A와 B가 대칭인지 확인하고 A와 B종이도 종이의 절반을 기준으로 대칭적인지 계속해서 재귀적으로 탐색한다. 예제 입력 3 0 000 1000110 예제 출력 YES NO YES 📝 풀이 import java.io.BufferedReader; import java.io.IOException; import j..
📚 문제 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 🔍 아이디어 1. 재귀적 풀이는 숫자 3개를 고르는 과정이 조합과 같기 때문에 해당 방식을 이용하였습니다. 2. 반복문 풀이는 숫자 3개를 고르는 과정을 3중 포문을 이용해서 arr에서 i, j, k숫자를 뽑는 경우에 대해서 목푯값과 비교하여 문제를 해결할 수 있습니다. 📝 풀이 1. 재귀적 import java.io.BufferedReader; impor..
✨ HINT 숫자를 아예 4,7로 구성해 보는 방식 숫자를 4,7로 구성한 후에 a와 b사이에 속하는지 확인하는 방식 📚 문제 1527번: 금민수의 개수 첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 🔍 아이디어 범위가 1~1,000,000,000이기 때문에 모든 수에 대해서 4,7로 이루어져 있는지 판단하는 것이 시간이 너무 오래 걸릴 것이라 생각하였습니다. 다른 방법은 아예 숫자 자체를 4,7로 이루어지게 한 후에 min, max사이에 해당 값이 있는지를 판단하는 것이 낫다고 생각하여 해당 방식을 이용하였습니다. Int형의 범위..
처음 백준 알고리즘을 풀면서 귀찮게 하는 요인들 중 제출 시의 지정형식, 어디까지 돌아갔는지 모르는 것들의 요인이 있습니다. 기본적인 설정 1. 자신이 주로 사용하는 풀이 언어 설정을 설정합니다. 설정-> 언어그룹에서 자신의 언어를 드래그 앤 드롭을 사용하여 위로 올려주면 됩니다. 추가로 공개/비공개 여부는 언어그룹 및 소스코드 공개 배너에서 설정하면 됩니다. 사용하지 않는 언어는 언어 배너에서 같은 방식으로 드래그 앤 드롭하여 변경하면 됩니다. 2. solved.ac : 유저들의 랭킹과 자신의 랭킹을 볼 수 있습니다, 추가로 문제의 난이도를 표시해 줍니다. 상단의 유저이름 오른쪽 설정으로 들어가서 solved.ac를 활성화합니다.(저는 사용 중이기에 해당 선택이 없습니댜..) 또한 보기 탭에서 문제의 ..
📚 문제 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 🔍 아이디어 그리디 알고리즘으로 해결하였습니다. 해당 문제는 과제의 마감일과 과제의 점수를 주고 최대 얻을 수 있는 과제 점수를 찾는 문제입니다. 저의 경우는 보통의 그리디와 같은 문제인줄 알고 먼저 배열을 마감일을 기준으로 오름 차순 정렬하였습니다. 그 이후에 마감일을 돌면서 해당 마감일 안에 해결할 수 있는 과제들이 있는 경우 우선순위 큐에 넣고 큐에 값이 있는 경우 해당 날자에 해결 할 수 있는 문제가 있는 것임으로 점수가 가장 큰 것을 리턴하도록 하였습니다. 하지만 예제 출력 값과 달라 문제..
📚 문제 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 🔍 아이디어 https://mathbang.net/101#gsc.tab=0 두 원의 위치관계, 내접, 외접 위치관계 또 나오네요. 이번에는 두 원의 위치관계에요. 위치관계 마지막이니까 정신 바짝 차리고 따라오세요. 원과 직선의 위치관계, 원의 할선과 접선, 접점에서 했던 것처럼 두 원이 어떤 관 mathbang.net 내접과 외접에 관한 문제입니다. 각 점을 기준으로 r 떨어진 거리에 사람이 있는경우는 원을 그려서 해당 해당 호 안에 사람이 있어야 한다는 소리로 인식했습니다. 따라서 두 원의 내접과, 외접..
📚 문제 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 🔍 아이디어 단순한 위상정렬 문제입니다. 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예 ko.wikipedia.org 과거에 다른 블로그에 작성한 글입니다. 위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬..
📚 문제 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 🔍 아이디어 오랜만에 풀어본 위상정렬 문제였습니다. https://lahezy.tistory.com/40 (제가 과거에 작성한 위상정렬 관련 글입니다) 위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬 알고리즘의 일종으로, 순서가 있는 작업을 차례대로 수행해야 하는 경우 사용할 수 있는 알고리즘이다. 방향 그래프로의 모든 그래프를 방향을 거스르지 않도록 순서 la..
📚 문제 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 🔍 아이디어 처음에는 a, b를 비교해서 lcs 문자열을 구하고 c와 비교하는 형식으로 구했더니 틀렸다. 해당 방법은 최대 값을 기준으로 하기 때문에 abc 모두에 대해서 최댓값으로 확신할 수 없다. 예를 들어(반례) a: abcdeqfpk b: qfpkabcde c: qpk 와 같은 경우 a,b에 대해서 bcdef이지만 abc전체에 대해서는 qpk이다. 따라서 abc에 대해서 항상 최장 공통 문자열이 아닌 것이다. 따라서 abc모두에 대해서 3차원 배열로 계산해야 ..
📚 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 🔍 아이디어 사이클 생성 시에 그래프가 아니다. 1. BFS/ DFS로 탐색 연결된 노드를 탐색한다, 만약 방문했던 노드를 재방문 시에는 사이클 이므로 트리 개수에서 제외한다(-1), 다른 경우는 탐색 시작 시점의 노드에서 (+1) 2. Union Find 정점이 들어오면 두 정점의 부모정정을 찾고 union한다. 만약 부모정점이 동일하면 사이클인 경우이다. 따라서 부모..
