본문 바로가기

Algorithm

[Combination]- Java코드 (DFS, BFS 방식 -성능비교)
2021. 12. 20. 알고리즘 문제를 풀때, 조합 개념이 요구되는 경우가 많이 존재한다. 조합을 구현하는 범용적인 두가지 방법을 익혀 코테와 실무에서 직접 코딩하기 위해 정리한다. input 으로 들어온 문자열에서 문자 n개 중 r개를 선택하는 경우의 값을 배열에 저장해 반환하는 코드를 만들어보겠다. 1. 백트레킹 방법 백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말합니다. 최적화 문제와 결정 문제를 푸는 방법이 됩니다. 조합에서 백트레킹은 한 요소마다 선택과, 비선택 두가지의 경우로 진행됩니다. // 사용 예시 : 문자열 값, 선택여부 체크 배열 chosen, 시작위치 start, 전체개수 n, 앞으로 선택할 개수 r) static void comb..
[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 ... 순서로 진행된다 설계 ..
[그래프] 방의 개수 - Java코드 ★★★★★ 매우 어려움
2021. 8. 26. https://programmers.co.kr/learn/courses/30/lessons/49190?language=java 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 문제 설계 오랫동안 생각해보면서 설계에 결론을 내렸다. 1. (0,0)에서 계속적인 좌표값이 반드시 필요하다. 2. 어디로 이동했는지에 대한 방향정보가 필요하다. (방향정보를 저장하지않더라도, 다음좌표에대한 연결정보가 필요) 3. 새로운 간선으로 좌표에 두번째 접근시, 방이 생긴다! (HashSet에 지나가는좌표를 저장해줘야 함) + 위에 세가지가 핵심이지만, 대각선에 대해서도 생각을 해야한다. 뱀처럼 끊어지지않..
[그래프] 순위 - Java코드
2021. 8. 26. https://programmers.co.kr/learn/courses/30/lessons/49191?language=java 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제 문제 이해 입출력 설명에 집중할 필요가 있다. 문제가 실질적인 경기와 다르게 계산된다. 승패라기보다 절대적 전투력 정도로 생각해야 될 것같다. 먼저 A->B , B->C이면 A->C도 성립한다. 설계 질문하기란에서 보니 다엑스트라, 플로이드 워셜 알고리즘을 쓴다는 말이 많지만, 모르니깐 원초적인 접근으로 풀어보겠다. 승패여부를 기록할 NxN 크기의 매트릭스를 만들어서 승 1 , 패 -1 자신은 0으로 초기화해준다. ex> n=5, resu..
[그래프] 가장 먼 노드 - Java코드 ★★★
2021. 8. 26. https://programmers.co.kr/learn/courses/30/lessons/49189# 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제 설계 그래프 탐색은 이미 bfs, dfs 파트에서 하였다. 이문제는 1에서 시작해서 넓이 level을 중심으로 단계적 탐색이 이루어져야 하므로 bfs문제로 보았다. 1로 부터 단계적으로 넓이중심에 탐색을 진행하면서, 반복적으로 진행해야하므로 Queue를 이용해서 1을 기준으로 단계별로 저 add, poll를 반복해준다 여기서 순회한 간선에 대해서는 배열 flag를 이용하거나, set을 이용해주면 되는데, 나는 set 자료구조..
[이분탐색] 징검다리 - Java 코드 ★★★★
2021. 8. 18. https://programmers.co.kr/learn/courses/30/lessons/43236?language=java 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 레벨 4지만 정말 어려웠다. 문제 이해 예제를 기준으로 다시 정리해보면 0 ~ 25 사이거리에 [2,11,14,17,21] 위치에 돌들이 존재하는 상황이며, 0 ~ 25 사이에서 어떤 위치값이 N개의 돌을 제거 했을때, 가질수 있는 최소 거리값들 중 최대값일까?이다. 예제와 같이 5개의 돌의 위치가 주어지면, 돌과 돌사이거리..
[이분탐색] 입국심사 - Java코드 ★★★
2021. 8. 17. https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제 이해 몇 분이 가장 최적의 시간인지를 찾으면 된다. 시간을 탐색할 범위는 1 ~ N x times[LastIndex] 이다. 이 범위 안에서 이분탐색을 통해, 해당시간에 n명을 만족하는 경우를 찾아 반환해주면 된다. 주의 문제에서 input의 범위는 n은 총 10억명까지, 대기시간은 총 10억 분까지도 들어올수있다. 이분탐색의 맨 우측 끝값이 최악의 경우 1..
[DFS/BFS] 여행경로 - Java코드 ★★★
2021. 8. 12. https://programmers.co.kr/learn/courses/30/lessons/43164?language=java 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 풀이 import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; class 여행경로 { /* 테스트 1 〉통과 (78.43ms, 106MB) 테스트 2 〉통과 (8.62ms, 81.2MB) 테스트 3 〉통과 (..
[DFS/BFS] 단어변환 - Java코드 ★★
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설계 DFS / BFS 을 통해 결과를 구하는 로직은 어렵지 않지만, 여러가지 클래스와 인터페이스의 존재를 알고 사용하는것이, 간결하면서도 효율적인 코드를 만들 수 있다고 생각되므로 Stream() 클래스에 대해서 좀더 공부해야할것같다. 풀이 import java.util.ArrayList..
[DFS/BFS] 네트워크 - Java코드
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설계 노드별 간선의 연결여부가 네트워크수를 결정 짓는다. Top으로부터 연결된 아이들을 제거해가면서 네트워크수를 Count해주면 될것 같다. 나는 computers[i][i]값이 무조건 1이라는 속성을 이용해서 Flag로 활용하여 이미 연결된 네트워크라는 것을 확인 할때마다 0으로 바꿔주었다. (잘못된) 풀이 class Solution { static..
[DFS/BFS] 타겟넘버 - Java코드
2021. 8. 11. https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 설계 쉽습니다. 사칙연산도 2개만 존재하고, 이전에 동적계획법에서 N으로의 표현문제를 풀었었기에, 비슷하면서도 난이도가 낮은 DFS로 판단하고 풀었습니다. 결과를 저장하는 answer 변수를 전역으로 선언하여 반환하지 않는 재귀함수로 구현하여 경우의 수를 순회하였습니다. 풀이 class Solution ..

티스토리툴바