본문 바로가기

Algorithm/Weekly Solved

[백준 1695] 팰린드롬 만들기 - Java 코드
2022. 5. 6. https://www.acmicpc.net/problem/1695 1695번: 팰린드롬 만들기 앞에서 뒤로 보나, 뒤에서 앞으로 보나 같은 수열을 팰린드롬 이라고 한다. 예를 들어 {1}, {1, 2, 1}, {1, 2, 2, 1}과 같은 수열은 팰린드롬 이지만, {1, 2, 3}, {1, 2, 3, 2} 등은 팰린드롬이 아니다. 한 수열 www.acmicpc.net 문제 이해 앞뒤가 똑같은 번호를 팰린드롬이라 한다. 입력 수가 주어지면, 해당 수열에 몇번의 숫자를 끼워 넣어야 팰린드롬으로 만들수 있는지를 구한다. 이 문제는 이차원 배열 DP를 만들어서 최솟값 메모이제이션을 통해 답을 구한다. 풀이 DP 배열은 n x n 크기로 선언후 -1로 채운다. 그리고 입력받은 arr값에 양 끝을 비교해가면서 팰린..
[백준 2632] 피자판매 - Java 코드
2022. 5. 6. https://www.acmicpc.net/problem/2632 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 문제 이해 나는 이 문제를 어떻게 이분탐색으로 풀어야 할지 모르겠다. 분명 이분탐색을 더 공부하고 싶어서 골랐지만... 경우의 수 문제는 그냥 해당 경우의 수를 구하는 방법밖에 생각이 나지 않았다. 풀이 경우의 수를 구해주는 풀이법 피자마다 각각 조합의 값이 몇개가 나오는지 count해주는 DP 배열을 만들었다. 피자의 조합의 경우의 수를 Count할 때, 몇가지 예외사항이 있..
[백준 1780] 종이의 개수 - Java 코드 (분할정복)
2022. 4. 18. https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다. 만약 종이가 모두 같은 수 www.acmicpc.net 문제 이해 분할정복은 매트릭스가 주어지며, 잘라야하는 숫자의 k승 이하로 주어진다. 해당 문제는 3의 k승 이하로 주어졌으며, 3으로 분할정복할때 나누어 떨어지는 input임을 알 수 있다. 풀이 입력은 BufferedReader로 결과는 HashMap에 -1, 0 , 1을 각각 저장해주는 형태로 구현하였다. 물론 3칸짜리 배열을 이용해도 괜찮다. import java.io.Buffer..
[백준 1922] 네트워크 연결 - Java코드 (크루스칼)
2022. 4. 9. https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 문제 이해 문제 이해는 어렵지 않다. N개의 노드에 대한 M개의 간선정보(from , to , cost) 가 입력되는데 , 모든 노드를 연결되는 최소비용을 구해주면 된다. 방법 이해 ★ 최소비용, 최단거리 그래프 (노드) 연결 문제를 MST , Minimum Spanning Tree (최소신장트리) 라고 말한다. Greedy (탐욕법) 문제유형 중에 대표적인 유형의 문제이다. 이런 MST 유형의 문제를 푸는 정형화된 알고리즘이 존재하는데, 바로 그 유명한 "크루스칼(Kruskal)..
[백준 1431] 시리얼 번호 (정렬) - Java코드
2022. 2. 17. https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 문제 이해 문자열을 입력받는값들을 배열에 저장하고 Comparator를 활용해서 잘 정렬해주어 출력하면 된다. 정렬에 3가지 기준은 아래와 같이 작성하였다. 길이를 비교는 length로 비교 문자열에서 숫자만 추출하여 합을 구하는 부분은 Regular Expression을 통한 치환후 for으로 합을 구하는 함수생성 마지막 사전순은 String.compareTo 메소드를 말한다. 풀이 imp..
[KAKAO 2021] 합승 택시 요금 - Java 코드 (Dijkstra) ★★★★
2022. 1. 19. https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 문제 이해 출발지점이 정해져있고, a,b를 포함하는 최단경로를 구하는 문제이기때문에..
[백준 1753] 최단경로 -Java코드 (Dijkstra)★★★
2022. 1. 19. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 설계 이 문제는 그래프의 최소경로값을 구하는 문제이다. 최소경로 문제는 BFS, Floyd Warshall(플로이드 와샬), 다익스트라(Dijkstra) 알고리즘 등으로 풀 수 있다. 가중치 개념이 없는 단순 최소경로문제 -> BFS 가중치 개념이 있는 한 노드기준의 최소경로값 -> Dijkstra (다익스트라) 가중치 개념이 있는 모든 노드기준의 최소경..
[백준 2606] 바이러스 - Java 코드
2022. 1. 17. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 접근 네트워크에 대한 입력값들을 이차원 배열에 담고, 방문여부를 체크할 Bool 배열을 선언하여 dfs를 구현해주었다. 풀이 import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int ..
[2021 KAKAO] 순위검색 - Java코드
2021. 12. 6. https://programmers.co.kr/learn/courses/30/lessons/72412
[백준 1920] 수찾기 - Java코드
2021. 12. 6. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 설계 해시셋을 이용해서 포함여부를 검사해주었다. 풀이 public class 수찾기 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); HashSet set = new HashSet(); for(int i=0;i
[2021 KAKAO] 메뉴 리뉴얼 - Java코드 ★★★
2021. 11. 30. https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제 설계 함수에서 받아드리는 INPUT 메뉴들을 원하는 갯수의 Course 조합으로 돌려가며 HashMap에 Combination을 저장해주고, 그 값을 Value기준으로 정렬하여 Max값의 조합을 결과로 Return해주도록 풀었다. 여기서 중요한건 메뉴의 조합이 X,Y 나 Y,X나 똑같은 메뉴조합이기 떄문에, HashMap에 넣어줄때, 반드시 키가되는 Stri..
[백준 1316] 그룹 단어 체커 - Java 코드
2021. 11. 30. https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 문제 설계 메인과 처리함수를 나누어 설계하려 한다. 메인에서는 Scanner를 이용해 입력받을 단어수를 N을 입력받으면, 해당 수만큼 for문을 돌려가며 처리함수를 불러 결과값을 구해 출력하게 한다. 처리함수는 입력받은 문자열을 받아서 char 별로 set 자료구조를 이용해 검사할 것이다. set은 중복검사에 용이하고 빠른 접근이 가능한 자료구조이기에 문제를 보자마..
[2021 KAKAO] 신규 아이디 추천 - Java코드
2021. 11. 24. https://programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제 풀이 String 클래스에 기본메소드 사용에 대한 문제이다. 그중에서도 정규표현식을 얼마만큼 아느냐가 코드를 간결하고 깔끔하게 짜는 방법이라 할 수 있겠다. class Solution { public String solution(String new_id){ new_id = new_id.toLowerCase().replaceAll("[^-_.a-z0-..
[백준 2941] 크로아티아 알파벳 - Java 코드
2021. 11. 24. https://www.acmicpc.net/problem/2941 2941번: 크로아티아 알파벳 예전에는 운영체제에서 크로아티아 알파벳을 입력할 수가 없었다. 따라서, 다음과 같이 크로아티아 알파벳을 변경해서 입력했다. 크로아티아 알파벳 변경 č c= ć c- dž dz= đ d- lj lj nj nj š s= ž z= www.acmicpc.net 오랫만에 백준문제를 풀게되어, 문제 제출 양식을 몰라 찾아보았다. 기본적으로 class명을 Main으로 고정시키고, main 메소드를 구현하되, 표준입력을 받는 형식으로 구현하면된다. public class Main { public static void main(String[] args) { // 구현 코드 } } 문제 설계 바꾸고자 하는 알파벳을 저장해두고,..
[위클리챌린지] 8주 - 최소 직사각형 - Java코드
2021. 10. 25. https://programmers.co.kr/learn/courses/30/lessons/86491?language=java 코딩테스트 연습 - 8주차_최소직사각형 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 문제 풀이 public static int solution(int[][] sizes) { int x=0,y=0,tmp; for(int i=0;i
[위클리챌린지] 7주 - 입실 퇴실 - Java코드
2021. 9. 24. https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 문제 풀이 package WEEKLY; import java.util.ArrayList; public class 입실퇴실 { public static int[] solution(int[] enter, int[] leave) { int len = enter.length; int[] answer = new int[len]; ArrayList list = new Arr..
[위클리챌린지] 6주 - 복서 정렬하기 - Java코드
2021. 9. 24. https://programmers.co.kr/learn/courses/30/lessons/85002#qna 코딩테스트 연습 - 6주차_복서 정렬하기 복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요 programmers.co.kr 문제 이해 객체 정렬 문제이다. 승률 > 무거운 사람을 이긴 횟수 > 내 몸무게 > 순번 순서로 복서를 정렬해주면된다 객체를 만드는게 깔끔하지만, 1000명 이하의 input이 정해져있으므로 사용이 편한 이차원배열로 문제를 풀었다. 포인트 자바로 푸는경우, 핵심은 Arrays.sort에 comparator사용..
[위클리챌린지] 5주 - 모음사전 - Java코드
2021. 9. 1. https://programmers.co.kr/learn/courses/30/lessons/84512#qna 코딩테스트 연습 - 5주차 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 문제 이해 문제가 정해진 단어 안에서 규칙만 찾으면 되게 쉬울것 같다. 사전에 순서를 먼저 살펴보자 A - AA - AAA - AAAA - AAAAA - AAAAE - AAAAI - AAAAO - AAAAU AAAE AAAEA -AAAEE - AAAEI - AAAEO - AAAEU ... 순서로 진행된다 설계 ..

티스토리툴바