glenn

문제해석문제 해석하는데 너무 많은 시간이 소요됬다.  머리가 나쁜걸까..아래는 그림으로 간단하게 표현했다.  모두 참고하시길.. 아래 개념은 기본으로 알아야함.◎ 큐 pop() : 선입 선출◎ 스택 pop() : 후입 선출 입력값1줄 : 42줄 : 0 – 큐        1 – 스택        1 – 스택        0 – 큐3줄 : 1 2 3 4(위 자료구조의 첫번째 값)4줄 : 3 (길이 3인 수열)5줄 : 2 4 7 (위 수열의 값)    코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Deque;im..

코딩테스트/[ 알고리즘 ] 2024. 10. 30. 18:09

문제수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세..

코딩테스트/[ 알고리즘 풀이 ] 2024. 7. 29. 12:58

문제설명명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다. 아래 표는 4가지 명함의 가로 길이와 세로 길이를 나타냅니다.가장 긴 가로 길이와 세로 길이가 각각 80, 70이기 때문에 80(가로) x 70(세로) 크기의 지갑을 만들면 모든 명함들을 수납할 수 있습니다. 하지만 2번 명함을 가로로 눕혀 수납한다면 80(가로) x 50(세로) 크기의 지갑으로 모든 명함들을 수납할 수 있습니다. 이때의 지갑 크기는 4000(=80 x 50)입니다. 모든 명함의 가로 길이와 세로 길이를 나타내는..

코딩테스트/[ 알고리즘 풀이 ] 2024. 7. 28. 20:16

문제설명전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. -구조대 : 119 -박준영 : 97 674 223 -지영석 : 11 9552 4421전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.  제한사항phone_book의 길이는 1 이상 1,000,000 이하입니다.각 전화번호의 길이는 1 이상 20 이하입니다.같은 전화번호가 중복해서 들어있지 않습니다. 입출력 예제   입출력..

코딩테스트/[ 알고리즘 풀이 ] 2024. 6. 18. 09:19

문제 설명수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요  제한사항- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. - completion의 길이는 participant의 길이보다 1 작습니다. - 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. - 참가자 중에는 동명이인이 있을 수 있습니다.  입출력 예    풀이1. 배열 정렬// hash관련 문제라는걸 인지 못하고..

코딩테스트/[ 알고리즘 풀이 ] 2024. 6. 3. 16:49

백트래킹 이란?재귀적으로 문제를 해결하는 기법으로, 가능한 모든 해를 탐색하면서 불가능한 해를 만났을 때는 되돌아가서 다른 경로를 탐색하는 방식.  백트래킹 단계백트래킹의 구조는 기본적으로 DFS(깊이 우선 탐색)를 기반으로 하되, 조건문을 사용하여 불가능한 경로를 조기에 포기하는 방식이며 이를 통해 불필요한 탐색을 줄이고 효율적으로 해를 찾는다.해 탐색: 현재 경로를 확장하여 해를 탐색한다.유효성 검사: 현재 경로가 유효한지 검사 후 유효하지 않으면 그 경로를 포기하고 돌아간다.완전성 검사: 현재 경로가 완전한 해인지 검사한다. 완전한 해라면 결과를 기록한다.백트래킹: 위 단계들을 반복하며, 모든 가능성을 탐색한다.  백트래킹 사용백트래킹은 퍼즐 문제(예: 미로 찾기, N-퀸 문제), 제약 만족 문제,..

코딩테스트/[ 알고리즘 ] 2024. 5. 20. 14:28

선택정렬이란? 처음 배열 탐색 시 최소값을 찾은 후 가장 첫번째 배열값과 자리를 바꾸는 방식. 시간복잡도 O(n^2)이며 큰 데이터셋에는 적합하지 않다. 따라서 큰 데이터셋에는 퀵, 힙, 병합정렬등을 고려. 선택정렬 흐름도 배열내 최솟값을 찾음 최솟값을 맨앞자리 값과 swap 이미 자리교체된 값의 다음값을 첫번째로 기준으로 삼고 1,2 번 과정 반복 round 9는 8번돌면 최종적으로 마지막 값은 정렬이 되있으므로 skip 자바 구현 public class Selection_Sort { public static void selection_sort(int[] a) { selection_sort(a, a.length); } private static void selection_sort(int[] a, int..

코딩테스트/[ 알고리즘 ] 2024. 4. 9. 16:04

이분탐색이란? 정렬된 배열 또는 리스트에서 특정 값을 찾는 고속 탐색 방법. 이진 탐색은 탐색범위를 1/2로 줄이며 탐색하기에, 선형탐색에 비해 빠르다. BUT 배열, 리스트는 정열되어 있어야 한다는 전제조건 배열의 '중간 값'을 선택 후 찾는값과 비교. 중간값이 찾는값보다 크면 '배열의 왼쪽 부분'에서 탐색 시작. 중간값이 찾는값보다 작으면 '배열의 오른쪽 부분'에서 탐색 시작. 위 과정 반복 시간복잡도 비교 순차적 탐색은 최악의 경우 배열의 끝까지 탐색하지만, 이분탐색은 1/2씩 범위를 줄여서 탐색하므로 빠르다. 방식 시간복잡도 순차적 탐색 O(n) 이분 탐 O(logn) 자바 구현 - 반복문으로 구현 public static boolean BSearch(int[] arr, int n) { int l..

코딩테스트/[ 알고리즘 ] 2024. 4. 8. 17:25