백준6 2018 카카오 블라인드 채용 - [1차] 셔틀버스 문제 해석 해당 문제는 구현 문제입니다. 문제에서 주어진 힌트와 제한사항을 바탕으로 아래와 같이 발생 가능한 상황을 시간 순서대로 분류했습니다. 버스 운행시간 이전(~09:00) 탑승대기 크루의 수 >= 최대 운행 가능한 사람 수 버스 운행 시작 이후(09:00~) 버스가 모두 돌기 전에 탑승 대기 크루의 수 >= 최대 운행 가능한 사람 수 버스 운행이 종료된 시점에 탑승 대기 크루의 수 == 최대 운행 가능한 사람 수 버스 운행이 종료된 시점에 탑승대기 크루의 수 < 최대 운행 가능한 사람 수 풀이 최초에 문제에 대한 명확한 정의를 하지 않고 코드부터 작성했을 때 2시간이 걸려도 풀지 못했는데 정의를 완벽히 마치고 풀이에 들어 갔을 때는 30분 만에 해결이 됐습니다. 구현 문제에서는 문제에 대한 "명확.. 2021. 8. 16. 백준 3954 Brainf**k 인터프리터 문제 해석 출력이 Terminates이거나 Loops x y 이기 때문에 입력의 마지막인 프로그램 입력 부분은 무시해도 무관 [ ]이 do-while 반복문과 같이 동작함 50,000,000 5천만 번 이상 실행 시 종료되지 않는다면 무한루프 판정 구현이 어려운 문제는 아니었지만 골드 1 레벨인 이유는 "무한루프" 일 때 해당 구간을 정확히 구하는 마지막 처리가 까다로운 이유인 것 같다. ( 나도 이 부분에서 매우 오랜 시간 고민했다 ) 풀이 기본적으로 탐색 시간을 최소화시키기 위해 한 쌍인 각 괄호의 위치를 pos배열에 저장하였다. 마지막 무한루프 위치 처리에 대해서 다양한 생각을 해보았지만 실패했다. 무한루프 판정 시 실행 중인 루프를 포함한 가장 바깥의 루프 ==> + [ - [ ] + + ] 같은.. 2021. 2. 3. 탐색 알고리즘 - BFS(넓이 우선 탐색) 다양한 탐색 알고리즘 중 하나인 BFS를 알아보자 BFS는 Breadth First Search의 줄임말로 DFS의 반대 개념이라고 생각하면 된다 (DFS 설명) 아래 트리구조를 보자 DFS가 root node(최상단의 node)부터 시작하여 좌측 끝 3번 노드까지 탐색하고 중앙 4번 노드를 탐색한다반면 BFS는 root node에 바로 맞닿아있는 2,3,4번 노드를 순차적으로 탐색한다 탐색 순서를 알아봤으니 BFS 구현의 특징을 살펴보자 1. 자료구조 Queue를 사용한다 -> 1번 node와 맞닿아있는 2,3,4번 노드를 모두 큐에 넣은 후 큐에서 2번 노드를 뽑고 2번의 자식 노드들을 큐에 담는다 이런 간단한 로직을 반복하면 된다. 2. 재귀문을 사용할 필요 없이 반복문 하나로 탐색이 가능하다. w.. 2020. 9. 15. 백준 5373 큐빙 이 문제는 친구가 추천해줘서 풀어본 순수 구현 문제이다. 문제 이름 그대로 큐브를 하는 것을 떠올리면서 행렬들의 값을 만지면 되는 간단한(?) 문제이다. 풀이 필요한 알고리즘은 딱히 보이지 않았고 시간과 노력으로 풀 수 있는 문제인 듯 코딩을 시작하기 전 노트에 6면의 움직임을 직접 그리면서 표현해보고 연계적인 동작을 설계하는 시간을 가진다면 막힘없이 코드를 작성할 수 있을 것이다! 소스코드가 너무 복잡하고 반복적이어서 "윗면"의 코드만 일부 발췌해왔다. 코드 static void cubing(char face, char direc) { char[] tmp = new char[3]; char[][] change = new char[3][3]; switch(face) { case 'U' : if(direc.. 2020. 9. 1. 에라토스테네스의 체 - 소수 구하기 먼저 소수(Prime Number)에 대해 이해하고 넘어가야겠다. 소수는 1을 제외한 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. 즉, 13은 1 X 13 말고는 성립하는 식이 없기 때문에 소수이다. 이 소수를 구하는 가장 최적화된 방법으로 알려진 것이 바로 에라토스테네스의 체이다. 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수 판정법이다. 쉽고 빠른 이해를 위해 간단한 예시와 함께 알아보자. Q) 120까지의 자연수 중 소수를 구하라. 알고리즘은 아주 간단하다. 2부터 120까지 순차적으로 탐색하며 자신의 1,2,3..... 배인 수들을 삭제한다. 이때 이미 삭제된 숫자는 탐색할 필요가 없다. 즉, 아래 그램처럼 탐색 순서는 2,3,5,7,11.... 2020. 8. 23. 백준 N9251_LCS(Longest Common Subsequence) 문제 LCS는 Longest Common Substring과 Sequence가 있습니다. 이 두 가지의 차이는 LCS가 비교 문자열에서의 연속여부 입니다. 주어진 두 문자열(길이가 다를 수 있음)의 공통된 문자열 중 가장 긴 길이를 탐색하는 문제입니다. 완전탐색으로도 풀이는 가능합니다. 이럴 경우 시간복잡도가 최악의 경우 O(n^n)로 매우 크기 때문에 DP를 이용해야 합니다. 연속되지 않은 문자들을 뽑아도 되지만 순서는 지켜야 하는 조건을 이용하면 문자열 1에 대해 문자열 2를 0번 인덱스부터 점차 비교하는 방식으로 해결이 가능합니다. 풀이 먼저 DP를 아래 matrix처럼 선언합니다. 여기서 각 0번 index를 0으로 초기화시켜둔 상태로 가정하고 진행하는 이유는 만약 두 문자열 중 하나라도 null.. 2020. 8. 12. 이전 1 다음
