알고리즘22 [JAVA] 백준 - 검문 2981 (정수론, 유클리드 호제법) https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 이 문제는 정말 수학문제였습니다. 정답률이 21프로 밖에 안되는데 그 이유는 완전 탐색의 경우 시간초과가 나기 때문입니다. 최악의 경우를 생각해보자. 먼저 M의 범위를 알아야합니다. 결론부터 이야기하면 M은 1보다 큰수이며 주어진 N개의 수 중에서 가장 큰수보다 작은 수입니다. 예를 들어, 주어진 수가 2, 3, 8 ,15 라면 M 의 범위는 2~14 입니다. 왜냐하면 M이 가장 큰 수라고 가정 해보면 주어진 수.. 2022. 3. 29. [JAVA] 백준 1379 와 세제곱 (백트래킹 , 정수론) https://www.acmicpc.net/problem/2731 2731번: 1379와 세제곱 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄 부터 T개 줄에는 테스트 케이스의 정보가 주어진다. 각 테스트 케이스는 숫자 하나로 이루어져 있고, 이 수는 문제에서 설명한 S이다. S는 www.acmicpc.net 문제 테스트 케이스 및 정답 http://acmgnyr.org/year2005/problems.shtml 2005 ACM Greater New York Regional Collegiate Programming Contest acmgnyr.org 세제곱 해서 1으로 끝나는 숫자는 어떻게 찾을 수 있을까요? 0부터 9까지 다 곱해보는 겁니다. 0*0*0 = 0 1*1*1 = 1 2*2*2 =.. 2022. 3. 19. [JAVA] 백준 변형 계단수 18244 (다이나믹프로그래밍) https://www.acmicpc.net/problem/18244 18244번: 변형 계단 수 첫째 줄에 정답을 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net "쉬운 계단수" 문제를 먼저 풀고 나면 좀 더 쉽게 접근 할 수 있습니다. 접근방법이 비슷하기 때문입니다. https://onejunu.tistory.com/143?category=882099 [JAVA] 백준 쉬운 계단 수 10844 (다이나믹 프로그래밍) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 위 노트를 보면서 간단하게 설명해보겠습니다. 만약 길이가 a.. 2022. 3. 18. [JAVA] 백준 쉬운 계단 수 10844 (다이나믹 프로그래밍) https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 위 노트를 보면서 간단하게 설명해보겠습니다. 만약 길이가 a 이고 마지막 숫자가 b 인 수가 있습니다. 다음숫자인 c는 어떤 숫자가 와야할까요? c 는 b가 9보다 작다면 b+1이 와야하고 b가 0보다 크다면 b-1이 올 수 있습니다. 예를 들어, b=8인경우를 생각해보겠습니다. 그러면 다음에 올 수 있는 숫자는 7과 9입니다. b=0인 경우를 생각하면 다음에 올 수 있는 숫자는 1 밖에 없습니다. b=9인 경우는 다음에 올 수 있는 숫자는 8 밖에 없습니다. 위 내용을 바탕으로 점화식을 세워 볼겁니다. 먼저 .. 2022. 3. 18. [JAVA] 2021 카카오문제 - 메뉴 리뉴얼 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 💡 개요 문제는 보고 오셨다고 생각하고 바로 풀이 하겠습니다. dfs 재귀를 통한 완전탐색 하셔도 되지만 저는 비트마스킹을 통한 완전탐색을 선택했습니다. 그 이유는 단어의 특징때문입니다. 하나의 주문에 들어가는 메뉴는 중복되는 알파벳이 없다는 점 때문입니다. 알파벳은 아래처럼 각각 하나의 숫자에 대응됩니다. 'A' - 1 'B' - 1 2022. 3. 15. [JAVA] 백준 K번째 최단경로 찾기 1854 (다익스트라) 만약 다익스트라 알고리즘이 어떤거였는지 다시 상기해보려면 아래 링크 참고해주시기 바랍니다. 이번 문제는 다익스트라 개념을 응용한 쉽지 않은 문제였습니다. 메모리 제한과 더불어 속도제약이 까다로웠습니다. https://onejunu.tistory.com/87 [JAVA] 백준 최단 경로 1753 ( 다익스트라 알고리즘) www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는.. onejunu.tistory.com 그래도 다익스트라에 대해 간단히 언급해보겠습니다. 우선순위 큐를 이용한 다익스트라 알고리즘을 설명하기 .. 2022. 3. 12. [JAVA] 백준 - 레이저 통신 6087 (BFS) (테스트케이스 제공) www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 시작점 부터 도착점 까지 BFS 로 최소 개수의 거울 수를 업데이트한다. 처음에는 DFS로 쉽게 풀 수있을 거 같았지만 100 * 100 배열을 돌리니까 stackoverflow 가 발생했다. BFS 로 최소 거울 수 를 업데이트 해야한다. # 풀이 1. 클래스 정의 static class Pair{ int x,y,dir,mirror; public Pair(int x, int y, int dir, in.. 2020. 10. 15. [JAVA] 오픈채팅방 (2019 kakao 프로그래머스) 문제의 핵심은 "마지막에 바꾼 닉네임이 진짜 닉네임" 이라는 것이다. 만약 record의 리스트가 아래처럼 주어졌다고 가정하자. ex) record ["Enter id1 A","Enter id2 B","Leave A","Enter id1 B", "Change id2 C"] 그리고 비어있는 HashMap 초기화 한다. 이유는 고유한 아이디마다 하나의 닉네임을 결국에 가지게 될것이기 때문이다. 뒤에서 부터 아이디가 HashMap에 있는지 검색하고 없으면 추가한다. record 의 크기가 5이므로 뒤에서 부터 총 5번의 과정에서 HashMap이 어떻게 변화하는지 보자. 1) { "id2":"C" } 2) {"id1":"B","id2":"C"} 3) {"id1":"B","id2":"C"} 4) {"id1":"B.. 2020. 8. 25. [JAVA] 가사검색 (kakao 2020 프로그래머스) trie 자료구조로 문제를 푼다. 1) 문자열 저장 만약 "fla","fly","ka" 문자열들을 가진다면 트라이 자료구조는 아래처럼 될 것이다. 2) 길이정보 저장하기 만약 쿼리를 "fro??"로 준다면 fro 로 시작하고 5글자인 모든 문자열의 수를 알아야 한다. 본인은 각 노드마다 문자열들의 수를 저장하는 해시맵을 각각의 노드마다 추가했다. 1)에서의 정보를 바탕으로 자료구조를 수정하면 다음과 같다. (x:y) 의 의미는 x길이의 문자열의 수는 y 다. 즉, (3:2) 는 길이가 3인 문자열의 수가 2개 있다는 뜻이다. 문제) 쿼리가 "fl?"로 왔다면 답) 파란박스에서 lenHashMap.get(3) "?" 로 시작하는 문자열은 문자열을 거꾸로 만들어서 똑같이 구현하면 된다. import java.. 2020. 8. 24. 이전 1 2 3 다음
