일지 & 개발

문제 요약알고리즘 분류: deque, 문자형, ASCII난이도:  Silver3문제내용:가장 처음에 가져온 카드는 자신의 앞에 놓는다.그다음부터는 가져온 카드를 자신의 앞에 놓인 카드들의 가장 왼쪽, 또는 가장 오른쪽에 놓는다. N장의 카드에 적혀있는 알파벳의 처음 순서가 주어질 때, 태욱이가 만들 수 있는 카드 문자열 중 사전 순으로 가장 빠른 문자열을 출력하는 프로그램을 작성하시오.사이트: https://www.acmicpc.net/problem/13417문제풀이 이번 문제에서는 데크활용 하는 문제이다.데크 자료구조는 앞뒤로 삽입, 삭제가 용이 하는 점에서 이용하면 앞에 문자보다 우선 순위가 크면 뒤로 추가 하고 작으면 앞으로 추가만 하면 된다. 하지만 문자형은 단순하게 크기 비교 처리하기가 힘들다 ..

문제 요약알고리즘 분류: 그리디난이도:  Silver5문제내용:2원, 5원 동전으로 거스름 돈을 줄수 있다.거스름돈이 N일때 최소 동전 개수를 구하여라(안되면 -1로 출력하여)사이트: https://www.acmicpc.net/problem/14916  문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 최대 거스름돈이 10만이라서 모든 경우의 수를 구하면 시간 초과가 나서 O(N) 탐색으로 푸는 방법을 찾아야 될것이다. 그래서 이번 문제는 그리디로 풀것이다. 그리디에 대한 설명은아래글로 확인 해보면 된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알..

문제 요약알고리즘 분류: 그리디난이도: Broze1문제내용:다음중 2가지 마법만 사용 할수있다.생성 마법: 고양이 1$1$마리를 마도카의 집에 생성한다.복제 마법: 현재 k개 있으면 k마리 이하만 복제 가능하다.사이트: https://www.acmicpc.net/problem/27961문제풀이 이번 문제는 전체 경우의 수를 탐색하기에는 10^12승 숫자 만큼 탐색하면 시간 초과가 나서 안될것이다. 그래서 O(logN)만큼 나오도록 구현 해야 한다. 그래서 이 문제는 그리디로 접근해야 한다. 그리디에 관련 내용은 아래글에서 확인해보면된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택..

문제 요약알고리즘 분류: DFS, BFS, 그래프난이도: Gold4문제내용: 사이트:https://www.acmicpc.net/problem/25195

문제 요약알고리즘 분류: BFS, DFS난이도: Silver2문제내용:사이트: https://www.acmicpc.net/problem/2644문제풀이 CodePython Javaimport java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Map> adj = new HashMap(); int N ..

문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:1번부터 N개번 징검 다리가 있다.첫 징검다리는 아무대나 점프할수 있다.그 다음 징검다리는 이전 이동한 거리보다 1이상 더 긴거리로 이동해야 한다.N번 까지 최대 몇번 건널수 있는지 구하여리첫줄에 케이스 T가 주어지고 각 케이스마다 N이 주어진다.사이트: https://www.acmicpc.net/problem/11561 문제풀이이번 문제에서 최대 징검다리수가 10^16 이다. 이정도 숫자이면 1 부터 10^16까지 탐색하면 시간초과가 나올것이다. O(N) 탐색이 아닌 O(logN)의 탐색으로 처리할수 있도록 해야 시간복잡도 문제를 해결할수 있다. 그래서 이번 문제는 이진 탐새으로 풀어야 할수 있다. 이진 탐색 관련글은 아래에서 확인..

문제 요약알고리즘 분류: 이진 탐색, 수학난이도: Silver3문제내용:X: 게임 횟수, Y: 이긴 횟수, Z: 승률(정수)계속 이긴다고 가정 했을때 몇판 더해야 승률이 변하는지 구하여라 만약 변하지 못하면 -1로 반환 하여라사이트: https://www.acmicpc.net/problem/1072 문제풀이 이번 문제는 하나씩 +1 씩 대입해서 정답은 나오지만 최대 숫자가 100억이다. 그리고 승률은 소수가 아닌 정수이다. 그럼 변화할라면 1%올라가야 하는데 1000억기준으로 올라갈라면 최대 10억번을 탐색 해야 한다. 그럼 초당 연산 1억기준으로 O(N)탐색 하면 오류가 날수 있다. 그래서  O(logN)탐색 시간초과 이내로 끝내야 통과가 된다. 그래서 이진탐색으로 해결할것이다. 이진탐색에 대한 내용은..

문제 요약 알고리즘 분류: 수학, 구현 난이도: Bronze1 문제내용: 두 사람의 이름을 알파벳 대문자로 표현한 뒤, 한 글자씩 번갈아가며 적는다. 이름이 남 경우 맨 뒤에 적는다. 알파벳을 대응하는 숫자로 바꾸고 각 숫자와 그 숫자의 오른쪽 숫자와 더한 것을 밑에 적는다. 더한 숫자가 10이 넘을 경우엔 일의 자리 수만 남긴다. 이 과정을 반복하여 숫자가 2개만 남았을 때까지 반복 한다. 사이트: https://www.acmicpc.net/problem/17269 17269번: 이름궁합 테스트 시윤이는 좋아하는 이성이 생기면 가장 먼저 이름궁합부터 본다. 이름궁합을 보는 방법은 간단하다. 먼저 이름을 알파벳 대문자로 적는다. 각 알파벳 대문자에는 다음과 같이 알파벳을 적는데 www.acmicpc.ne..