본문 바로가기

자바13

[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] 2021 카카오문제 - 메뉴 리뉴얼 https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 💡 개요 문제는 보고 오셨다고 생각하고 바로 풀이 하겠습니다. dfs 재귀를 통한 완전탐색 하셔도 되지만 저는 비트마스킹을 통한 완전탐색을 선택했습니다. 그 이유는 단어의 특징때문입니다. 하나의 주문에 들어가는 메뉴는 중복되는 알파벳이 없다는 점 때문입니다. 알파벳은 아래처럼 각각 하나의 숫자에 대응됩니다. 'A' - 1 'B' - 1 2022. 3. 15.
[JAVA] 지형이동 - 프로그래머스 이때까지 배운 알고리즘들을 정리하기 딱 좋은 문제. 난이도가 4인 이유는 아마 구현해야할 양이 많아서 인듯 하다. 1. BFS or DFS 로 그룹 나누기 만약 height 가 3일 때 land가 아래와 같다면 land[3][3] 1 1 13 5 1 12 7 6 11 원하는 결과인 group[3][3] 는 아래와 같다. group의 각 원소는 그룹 번호를 의미한다. 2. 인접리스트 생성하기 인접행렬로 할시 아래 처럼 메모리 초과난다. 인접 리스트의 결과물은 아래처럼 될것이다. 3. 거리가 작은 순으로 정렬하기 새로운 리스트와 클래스를 만들어서 정렬한다. gn 은 다음 그룹번호다. list 는 인접리스트를 말한다. Node 라는 클래스 인데 Node 는 원소로 a,b,d를 가진다. 즉, 그룹번호 a와 그룹.. 2020. 9. 26.
[JAVA] 백준- 연산자 끼워 넣기 14888 www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 중복된 연산자에 대해서 따로 처리를 해야하는가 생각했는데, 중복계산해도 경우의 수가 10! 밖에 안되서 전체 순열 탐색으로 돌렸더니 통과되었다. import java.util.Scanner; class Main{ static int n; static int[] nums; static int[] operators; static int max = -987.. 2020. 9. 21.
[JAVA] 부등호 (백준 2529 ) www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력� www.acmicpc.net 부등호의 수가 3 개 이며 서로 다른 한 자리 숫자 는 4 개 라고 가정해보자. 숫자 0부터9 까지 숫자들 중에 4개를 선택해서 모든 경우의 수를 따져야 하는가?? 그렇지 않다. 가장 작은수와 가장 큰 수를 구하는 것이 목적이기 때문에 가장 작은 수와 가장 큰 수의 조합은 이미 정해져 있다. 12,3,4 와 2,3,4,5 를 선택했다고 가정했을 때, 가장 작은 수는 1,2,3,4 에서 나올것이다. 마찬가지로.. 2020. 9. 21.
[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.
[JAVA] 메모리 사용량과 시간을 줄이는 간단한 아이디어 문제는 백준 2573번 문제로 진행했다. https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 � www.acmicpc.net 1. 문제 풀이 1) 2차원 배월의 모든 원소가 0인가? 그렇다면 6)으로 간다. 그게 아니라 하나라도 0보다 큰 수가 있다면 2)번으로간다. 2) answer 를 1증가 시킨다. 3) 2차원 배열을 1년이 지난 배열로 만든다. 4) bfs를 이용해 영역의 수를 카운트하고 2이상이면 ok에 표시하고 6)번으로 간다. 5) 2)반복한다. 6) ok가.. 2020. 8. 20.
[JAVA] 토마토 (백준 7569) 이 문제는 2차원이 아니라 3차원으로 bfs푸는 것이다. 또한 익기 시작하는 지점이 정해진 것도 아니며 여러개가 있을 수도 있고 없을 수도 있다. 관건은 모든 토마토가 익었는지 확인하는 것과 모두 익었다면 며칠이 걸리는지 구하는 것이 핵심이다. 본인이 접근한 방법대로 2층짜리 3x3 토마토상자가 있다고 가정하고 풀어보는 예시를 보자. 예) (z,x,y) 에서 z 는 높이이며 , x 는 가로, y는 세로다. x,y,z 모두 0부터 시작한다. 시작전 ( 0초 ) 큐에 남은 좌표 : (0,1,1) 1층 0 0 0 0 1 0 0 0 0 2층 0 0 0 0 0 0 0 0 0 1초후 큐에 남은 좌표: (0,0,1) , (0,1,0), (0,2,1) , (0,1,2) 1층 0 2 0 2 1 2 0 2 0 2층 0 0.. 2020. 8. 15.
[JAVA / PYTHON] 연구소 3 (백준 17142) - 삼성기출 자바로 bfs,dfs 문제를 풀어본적이 없어서 간단한 bfs 문제를 풀어보려고 시도했다. 이전에 삼성 sw 역량테스트를 준비하면서 파이썬으로 쉽게 풀었지만 이제는 자바에 익숙해 지고 싶어서 자바로 풀어보았다. 자바로 풀면서 놀랐던것은 왜 순열과 조합과 관련한 라이브러리가 없는 걸까... 물론 분명히 있을거 같은데 본인이 못찾는 것일 수도 있다. 귀찮지만 직접 조합을 구현했다. 조합은 dfs로 구현하였다. 문제를 푸는 알고리즘은 그림으로 표현하겠다. 위와 같은 연구소 배열이 있다고 하자. 값이 2인것은 바이러스가 놓일 수 있는 위치다. 바이러스가 놓인 위치가 아니다. 이 중에서 2개를 활성화 한다고 하면 활성화 한곳은 0 으로 바꾸고 visited 에서 해당위치에 1로 바꿔준다. 또한 비활성화한 곳은 -1.. 2020. 8. 1.