깊이 우선 탐색(DFS)

• DFS는 가능한 모든 경로(후보)를 탐색한다. =>따라서, 불필요할 것 같은 경로를 사전에 차단하거나 하는 등의 행동이 없으므로 경우의 수를 줄이지 못한다.

백트래킹(Backtracking)

• 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아 간다.

• 코딩에서는 반복문의 횟수를 줄일 수 있어 효율적이다.

• 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미 => 가지치기 =>가지치기를 얼마나 잘하느냐에 따라 효율성이 결정되게 된다.

  정리

  • 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
  • 즉, 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지않고 가지치기 하는 것
  • DFS등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.

백트래킹 기법의 유망성 판단 해가 될 가능성이 있다면 유망하다(promising)고 하며, 유망하지 않은 노드에 가지 않는 것을 가지치기(pruning)한다.

지난 10월 26일 부터 11월 23일까지 4주동안 우아한 형제들에서 주최한 "우테코(우아한 테크코스)의 프리코스"를 참여하게 되었다.
여태까지 우테코의 프리코스는 코딩테스트를 합격한 사람들만 참여할 수 있도록 하였는데 이번 5기의 경우는 우테코를 지원한 모든 지원자들이 참여할 수 있어서 나를 성장시킬 수 있는 좋은 기회라 생각되었고, 국비 교육을 듣는 도중에도 한치의 망설임 없이 지원하게 되었다.

4주동안의 프리코스 과제들에 대해 회고를 해보고자 한다.

1주차 - 온보딩

📕1주차 코드 보러가기

수요일 3시에 미션이 올라오자마자 설레는 마음으로 확인하였다. 1주차 미션은 온보딩이었다. 문제는 총 7문제였고 문제의 난이도를 확인해보니 1주차는 개발 환경 세팅과 익숙해지라고 난이도를 낮게 설정하신 것 같았다.

1주차에는 별다른 요구사항은 없었고, 기능을 해결하는 것에 초점을 둔 것 같았다. 문제를 하나하나씩 읽어가면서 어떻게 풀지 머릿속에서 정리를 하였고 어떤 함수가 필요할 지 아래의 사진과 같이 각 문제마다 주석으로 적어 정리해놓았다.

문제를 풀면서 고민을 많이했던 문제는 2번과 7번이었다. 두 문제에 대해서 자세하게 얘기해보겠다.

[Problem 2]

[Problem 2]

🚀 기능 요구 사항

암호문을 좋아하는 괴짜 개발자 브라운이 이번에는 중복 문자를 이용한 새로운 암호를 만들었다. 예를 들어 "browoanoommnaon"이라는 암호문은 다음과 같은 순서로 해독할 수 있다.

1. "browoanoommnaon"
2. "browoannaon"
3. "browoaaon"
4. "browoon"
5. "brown"
   임의의 문자열 cryptogram이 매개변수로 주어질 때, 연속하는 중복 문자들을 삭제한 결과를 return 하도록 solution 메서드를 완성하라.

처음 이 문제를 보고 "스택을 쓰면 간단하게 풀리겠구나"라는 생각을 했다.

--1차 문제 해결 과정--
1. 문자를 처음부터 하나씩 꺼내서 스택이 비어있으면 문자를 스택에 넣고,
2. 스택의 맨 위 값을 꺼내서 문자와 같으면 스택에서 제거
3. 스택에 들어있는 값들을 출력

이 과정을 통해 문제를 해결하였다. 모두 해결한 줄 알았지만 Slack을 보다가 내 방식이 틀렸다는 것을 알게 되었다.

문제를 대충 읽은 나머지 가장 중요한 문구을 놓친 것이다. 바로 "연속하는 중복 문자들" 이었다.

내가 풀은 방식은 연속하는 2개의 중복 문자들만 확인하고 제거하는 방법이었는데, 만약 중복하는 문자가 3개 이상이라면 내 코드로 해결되지 않는다는 것을 깨닫고 다시 코드를 뜯어고치기 시작했다.

결국 처음에는 스택을 이용하여 코드를 작성했지만 고친 코드에서는 List를 이용하였다.

--최종 문제 해결 과정--
1. String 타입의 문자열을 하나씩 분리하여 List에 넣는다.
2. 이중 for문을 이용해 list의 앞문자와 뒤 문자들를 비교하여 같은 문자를 모두 제거한다.
3. 위의 과정을 반복한다.
4. 리스트의 문자들을 합쳐서 출력한다.

위의 문제 해결 과정으로 문제를 해결하였지만 지금와서 코드를 다시 보니 이중 for문 안에 이중 if문 안에 for문... 끔찍해보인다.... 차차 시간날 때 코드를 수정해야겠다!!

[Problem 7]

[Problem 7]

🚀 기능 요구 사항

레벨 2의 팀 프로젝트 미션으로 SNS(Social Networking Service)를 만들고자 하는 팀이 있다. 팀에 속한 크루 중 평소 알고리즘에 관심이 많은 미스터코는 친구 추천 알고리즘을 구현하고자 아래와 같은 규칙을 세웠다.

• 사용자와 함께 아는 친구의 수 = 10점
• 사용자의 타임 라인에 방문한 횟수 = 1점
  사용자 아이디 user와 친구 관계 정보 friends, 사용자 타임 라인 방문 기록 visitors가 매개변수로 주어질 때, 미스터코의 친구 추천 규칙에 따라 점수가 가장 높은 순으로 정렬하여 최대 5명을 return 하도록 solution 메서드를 완성하라. 이때 추천 점수가 0점인 경우 추천하지 않으며, 추천 점수가 같은 경우는 이름순으로 정렬한다.
  

  제한사항

• user는 길이가 1 이상 30 이하인 문자열이다.
• friends는 길이가 1 이상 10,000 이하인 리스트/배열이다.
• friends의 각 원소는 길이가 2인 리스트/배열로 [아이디 A, 아이디 B] 순으로 들어있다.
  • A와 B는 친구라는 의미이다.
  • 아이디는 길이가 1 이상 30 이하인 문자열이다.
• visitors는 길이가 0 이상 10,000 이하인 리스트/배열이다.
• 사용자 아이디는 알파벳 소문자로만 이루어져 있다.
• 동일한 친구 관계가 중복해서 주어지지 않는다.
• 추천할 친구가 없는 경우는 주어지지 않는다.
  

  실행 결과 예시

  

역시 마지막 문제인 만큼 문제를 이해하는데 오래 걸렸다...

이 문제에서 고려해야 할 점

1. friends 배열에서 user가 0번 index, 1번 index 모두 있을 수 있다는 것
2. 이미 친구인 사람은 제외 시켜야한다는 것
3. 방문자에서 한 사람이 여러번 방문할 수 있다는 것

위의 부분들을 고려하여 문제를 해결하였다.

--문제 해결 과정--
1. user의 친구 추출하여 List에 저장
2. user와 함께 아는 친구 추출하여 List에 저장
3. 방문자 추출하여 Map에 저장
4. 점수 List 내림차순 정렬
5. Map의 key값 추출하여 List에 저장
6. 이미 친구인 사람 추출
7. 5번 List에서 이미 친구인 사람 삭제하여 출력

하나의 메서드 안에서 코드가 길어지는 것이 싫어 쪼개고 쪼갰던 것 같다. 살짝 돌아가는 느낌이 있고, 2번과 마찬가지로 들여쓰기가 많다... 7번 문제도 마찬가지로 시간을 내서 수정을 해야할 것 같다.

그 중 고쳐야 할 첫번째는 *이미 친구인 사람을 List에 담아두지 않고 바로 삭제할 수 있도록 * 하면 좋을 것 같다.

결론

1주차 프리코스 과제들을 모두 구현에 성공하여서 뿌듯하긴 하지만 주로 기능 중심으로 구현을 하다보니 클린하지 못한 코드가 나왔다. 그때의 나를 반성하며, 클린한 코드로 만들기 위해 코드를 수정하러 가야겠다...
다음 포스팅은 2주차 프리코스 회고록으로 돌아오겠다. (1주차 피드백 내용은 2주차 서론에 적도록 하겠다.)

<문제 설명>

<입출력 값>

<문제 해석> 자연수 n이 주어졌을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴해라.

<문제 해결> 피보나치 수열은 알고리즘 문제에서 많이 봐서 그런지 친근했다. 피보나치 수열을 배열에 넣어주고 for문을 돌려서 차례대로 값을 구해준다. n번째 값을 구해주면 끝!
처음에는 a[n] % 1234567 만 해줬는데 몇개는 통과하고 몇개는 실패가 떴다. 이유를 찾다가 피보나치 수열 계산을 해줄 때 a[i]와 a[i+1]도 1234567로 나눈 값으로 바꿔줬더니 성공하였다.
** 78번째 이후부터는 표현은 되지만 '안전한 정수 계산'을 보장하지 못한다 따라서 (A+B)%C = ((A%C)+(B%C))%C 라는 수의 속성을 통해 F(n)%1234567 = ((F(n-1)%1234567)+(F(n-2)%1234567))%1234567 을 해줘야한다는 글을 참고하여 깨닫게 되었다.

<내 코드>

``` class Solution { public int solution(int n) { int answer = 0;

    int[] a = new int[n+1];
    a[0] = 0;
    a[1] = 1;
    for(int i=0;i<=n-2;i++){
        a[i+2] = (a[i]% 1234567) + (a[i+1] % 1234567);
    }
    answer = a[n] % 1234567;
    return answer;
}

}```

<문제 설명>

<입출력 값>

<문제 해석> 자연수 n을 연속하는 자연수들의 합으로 표현할 수 있는 개수를 구해라. +자기 자신

<문제 해결> n은 1을 감소시킨다. (자기 자신 말고 그 전 값으로 계산하기 위함) n이 0보다 클 동안 cnt를 1씩 증가시키고 n은 n - cnt가 된다. 만약에 n % cnt == 0 이면 answer의 값을 증가시킨다.

<내 코드>

class Solution { public int solution(int n) { int answer = 0; int cnt = 1; // 수열의 크기 n--; while (n > 0) { cnt++; n = n - cnt; if (n % cnt == 0) { answer++; } } return answer+1; } }

<문제 설명>

<입출력 값>

<문제 해석> -로또 순위 -6개 일치 : 1등 -5개 일치 : 2등 -4개 일치 : 3등 -3개 일치 : 4등 -2개 일치 : 5등 -그 외 : 6등
-로또 번호가 0 인 것은 번호를 알 수 없다는 뜻
해당 로또의 최대 등수와 최저 등수를 도출하라.

<문제 해결>

1. 먼저 해당 로또의 0의 갯수를 구한다. => 0의 개수에 따라 최대, 최저를 구할 수 있다.
2. 해당 로또와 당첨 복권의 일치하는 숫자의 개수을 구한다. 0의 개수 -> zeroCount / 일치하는 숫자의 개수 -> count
   최대 일치하는 숫자의 개수(max) => 일치하는 숫자의 개수 + 0의 개수 (count + zeroCount) 최소 일치하는 숫자의 개수(count) => 일치하는 숫자의 개수 (count)
   단, max와 count가 0일 경우에는 1로 바꿔준다.
   

최종 등수 최대 등수 : 7 - max 최저 등수 : 7 - count

<내 코드>

class Solution {
    public int[] solution(int[] lottos, int[] win_nums) {

        int zeroCount =0;
        int count =0;
        int max=0;

        for(int lotto : lottos){
            if(lotto == 0) {
                zeroCount++;
            }
            for(int win_num : win_nums){
                if(lotto == win_num){
                    count++;
                }
            }
        }

        max = zeroCount + count;
        if(max == 0){
            max =1;
        }
        if(count == 0){
            count =1;
        }

        int answer[] = {7-max, 7-count};

        return answer;
    }
}

<문제 설명>

<입출력 값>

<문제 해석> -괄호가 알맞게 짝 지어졌는지 유무를 리턴한다.

<문제 해결>

1. Stack을 이용하여 문제를 해결하려고 하였다.
2. for문을 이용하여 만약 ")" 일 때, 스택의 맨 위의 값이 ")"이고 스택이 비어있지 않는다면 스택의 맨 위의 값을 pop 시킨다.
3. 만약 ")" 이라면, 스택에 push 한다. 까지만 하고 코드를 돌렸을 때, 에러가 났다. 그 이유는
4. s의 첫번째 괄호가 ")" 인 경우
5. for문이 끝났을 때 stack이 비어있지 않는다는 경우 였다.
   if 문을 이용해 위의 2가지의 경우를 구현해주었다. 다행히 잘 실행되었고 통과하였다.

<내 코드>

import java.util.*;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        Stack<Character> stack = new Stack<>();
        if(s.charAt(0) ==')'){
                return false;
            }
        for(int i=0;i<s.length();i++){
            if(s.charAt(i) == ')'){
                if(!stack.isEmpty() && stack.peek() == '('){
                    stack.pop();
                }else{
                    return false;
                }
            }else{
                stack.push(s.charAt(i));
            }
        }
        if(!stack.empty()){
            return false;
        }
        return answer;
    }
}

코드를 짤 때 예외인 경우를 잘 파악하고 해결해야겠다!

<문제 설명>

<입출력 값>

<문제 해석> -A, B의 배열 값들 중 하나씩을 골라 곱해서 각각을 더한 값 중 가장 최솟값을 리턴한다.

<문제 해결>

1. A 배열과 B 배열을 오름차순으로 정렬한다.
2. for문을 이용하여 A 배열의 값 중 하나, B 배열의 값 중 하나를 뽑는다.
3. 최솟값을 구하기 위한 방법으로는 A 배열의 가장 작은 값과 B 배열의 가장 큰 값을 더한다.

<내 코드>

import java.util.*;
class Solution
{
    public int solution(int []A, int []B){
        int answer = 0;

        Arrays.sort(A);
        Arrays.sort(B);

        for(int i=0;i<A.length;i++){
           answer += A[i] * B[B.length-i-1];
        }
        return answer;
    }
}

<문제 설명>

<입출력 예>

<문제 해석> -공백으로 구분된 숫자들 중 최댓값과 최솟값을 출력하라

<문제 해결>

1. 공백으로 구분된 숫자들을 공백을 기준으로 split() 함수를 이용하여 배열에 담아준다.
2. min 값과 max값을 배열의 0번째로 지정한다.
3. 배열의 크기만큼 for문을 돌리고
4. for문 안에서 if문으로 배열을 비교해 최댓값과 최솟값을 찾는다.
5. 문자열 answer안에 담아주고 리턴한다.

<내 코드>

import java.util.*;
class Solution {
    public String solution(String s) {
        String answer = "";
        String[] ss = s.split(" ");
        String max =ss[0];
        String min =ss[0];
        for(int i=0;i<ss.length-1;i++){
            if(Integer.parseInt(ss[i+1]) >Integer.parseInt(max)){
                max = ss[i+1];
            }
            if(Integer.parseInt(ss[i+1]) < Integer.parseInt(min)){
                min = ss[i+1];
            }
        }       
        answer = min + " " +max
        return answer;
    }
}

프로그래머스에서 문제는 꾸준히 푸는데 블로그에 적는 게 밀리는 일이 많아졌다.
제때제때 적어야겠다....😂

<문제 설명>

<입출력 예>

<문제 해석> -n : 인원 수 -게임이 끝나는 경우

1. 앞에 나왔던 단어를 똑같이 말하는 경우
2. 앞사람이 말한 단어의 맨 뒷 글자와 다음 사람이 말하는 단어의 맨 앞글자가 다를경우

-게임이 끝나지 않으면 [0, 0]

<문제 해결> aa : answer[0] / aa2 : answer[1] a : 앞사람 단어의 마지막 글자 / b : 나의 첫번째 글자 먼저, 차례인 사람이 말한 단어가 앞에 나왔던 단어인지 비교하였다. 만약 앞에 단어가 있다면 aa와 aa2를 계산 후에 배열 answer에 넣어주고 for문을 빠져나온다. 단어가 없다면, 본인 차례의 앞글자와 앞사람의 뒷글자를 비교하였다. 만약 비교했을때 두 글자가 다르다면 aa와 aa2를 계산 후에 배열 answer에 넣어주고 for문을 빠져나온다. 둘 다 해당되지않는다면 배열 answer에 [0, 0]을 넣어주도록 하였다.

<내 코드>

<문제 설명>

<입출력 예>

<문제 해석> 문제 설명이 길어서 이해하는 데 꽤나 걸렸다. -점프를 하면 점프 수 만큼 건전지 소모 -순간이동을하면 (현재까지 온 거리) X 2 칸 이동 => 건전지 소모 x -점프를 해서 도착하거나 순간이동을 써서 도착하는 것은 본인 마음 -건전지 최소로 이용해서 도착

<문제 해결> 입출력 예에서 도착 지점이 5000일때를 생각하면서 문제를 어떻게 풀지 고민하였다. "5000으로 갈때 2500일때 순간이동을 써서 한번에 5000으로 이동하면 되지않나?" "그럼 1250일때 2500으로 순간이동? 625일 때 1250으로 순간이동?" 하면서 2로 계속 나누어 갔다. 625는 홀수라 2로 나누면 순간이동을 못하는데.. ==> 홀수면 -1을 해서 짝수로 만들어 주면 되는구나! (이때 점프를 해서 건전지 1 소모)

결론 : n을 2로 나누어서 홀수면 건전지 1 소모,n = n-1 / 짝수면 n = n/2

<내 코드>

강의 웹 사이트 1seok2jo

💻Features

1seok2jo에서는 다음과 같은 기능을 제공합니다.

1. 유저(회원, 강사, 관리자) - 회원가입, 로그인, 장바구니
  -회원 : 회원가입, 로그인, 마이페이지 (프로필, 내 학습, 내 게시판, 내 결제내역), 장바구니, 강의 듣기 , 수강 신청
  -강사 : 강사 신청, 내 강의 게시판, 내 매출 내역 
  -관리자 : 회원 관리, 강의 관리, 게시판 관리 , 매출 관리
2. 강의 - 강의 추가, 삭제, 수정
3. 게시판 - 자유게시판, 공지사항, QNA, 고객센터, 수강평
4. 강의 결제, 환불

🙆‍♀️Member

🎬Work Flow

📃ERD

📍System Architecture

📢Notion

📕Notion

♣Github

🔍Github

📸실행화면

숫자 문자열과 영단어 <문제 설명>

<입출력 예>

문제를 보고 영어문자에 해당하는 숫자를 대신 써준다? 라는 생각을 했고 문자열을 구분해야하나 라는 생각과 함께 split() 함수가 떠올랐다. split() 함수를 쓰려고 여러가지 시도를 해봤지만 해결되지않았고 split()함수를 쓰는 게 아닌 것 같다 라는 결론을 내렸다. 다시 천천히 생각 끝에 해당하는 숫자를 대신 써준다 라는 말에서 "대신" 이라는 말이 뇌리에 박혔고 replace() 함수가 떠올랐다.

<내가 쓴 코드>

"zero"부터 "nine"을 배열 안에 넣어주고 for문을 이용해 문자열 s안에 있는 영어단어를 하나씩 해당하는 배열의 순서와 바꿔주도록 하였다.

처음에는 split()함수를 쓰려고 했던 것이 Java 함수들을 완벽하게 숙지하지 못하고 있었다는 것을 의미한다고 깨달았다. 어떤 상황에서 어떤 함수를 써야할지 바로 알기 위해 Java의 함수들을 무!조!건! 알아놔야겠다.

*split(String regex) : 특정 기준으로 문자열을 분리할 때 *replace(char oldChar, char newChar) : 문자 또는 문자열을 변환하고 리턴

앞으로의 코딩테스트 준비를 위해 programmers school의 코딩문제들을 풀기로 했다.

로그인 성공?

<문제설명>

<입출력 예>

문제를 보고 for문으로 배열에 있는 값들을 비교하고 if문을 써서 아이디와 비밀번호를 확인하는 방식을 생각했다.

1. 아이디만 맞고 비밀번호 틀리면 => "wrong pw"
2. 아이디와 비밀번호 둘 다 틀리면 => "fail"
3. 아이디와 비밀번호 둘 다 맞으면 => "login"

<내가 쓴 코드>

❗풀면서 한가지 조심해야 할 점❗ 처음에는 if문에서 문자열 비교할때 "=="을 써서 통과가 되지 않았다. 문자열 비교는 "=="을 쓰는 것이 아니라 .equals()를 써야 한다는 것! 꼭 명심하기로!!!

항상 다른 분들의 개발 일지만 봐왔던 내가 드디어!! 개발 일지를 쓰려고 한다😉

---

현재의 마음은 설렘 반, 두려움 반이다.

예전부터 쓰고 싶었던 개발 일지를 쓰려고 하니 막상 무엇을 적어야 할지 감이 안온다.

개발 일지 공간에는 매일매일 공부를 한 내용과 문제가 발생했다면 어떻게 해결했는지, 프로젝트에 대한 내용, 코딩테스트 준비 과정에 대해 적으려고 한다.

신입 개발자의 개발 성장 stroy를 잘 지켜봐주길 바랍니다!!😊