프로젝트 기간

• 전체 기간 : 2023-12-04 ~ 2024-01-29
• 기획 / UI : 2023-12-04 ~ 2024-01-05
• 기능 구현 : 2024-01-05 ~ 2024-01-29
• 리팩토링 : 2024-02-14 ~ 2024-02-29

• Github : https://github.com/Strong-Potato/TripVote-FE
• 배포 링크 : https://tripvote.site/

  Test ID : test@test.com
  Test PW : 1q2w3e4r!Q

담당 파트 - 여행지 투표

** 기능 요약 ** (1) 투표하기 - 투표 CRUD, 투표하기, 투표 순위 정렬 (2) 여행지 후보 - 여행지 후보 추가&삭제, 메모 남기기, 메모 임시 저장 (3) 여행지 후보 지도 - 카카오맵으로 후보 보기

추가 페이지

1. 🤔 고민한 기능

(1)‘메모 작성 페이지’의 실시간 저장 기능

• 커스텀 훅 useGetSelectedArray을 이용하여 유저가 선택한 여행지 목록과 여행지에 작성한 메모를 실시간으로 로컬스토리지에 저장. 이는, 메모 작성 도중 유저가 페이지를 이탈했다 돌아와도 처음부터 작성할 필요가 없도록 하기 위함이다.

  • useGetSelectedArray

      import {RecoilState, useSetRecoilState} from 'recoil';
      import {SearchItemType} from '@/types/home';
      import {TaglineType} from '@/types/vote';
    
      // 다른 컴포넌트에서도 사용할 수 있도록 두 가지 타입 제시
      const useGetSelectedArray = <T extends SearchItemType | TaglineType>(selectedState: RecoilState<T[]>) => {
        const setSelectedState = useSetRecoilState(selectedState);
    
      // 체크박스 토글로 배열에 아이템 아이디 담기
        const toggleItemInNewArray = (data: T) => {
          setSelectedState((currentArray) => {
            const index = currentArray.findIndex((item) => item.id === data.id);
    
            if (index !== -1) {
              const newArray = [...currentArray.slice(0, index), ...currentArray.slice(index + 1)];
              return newArray;
            } else {
              const newArray = [...currentArray, data];
              return newArray;
            }
          });
        };
    
      // 메모 작성 시 기존 배열에 담기
        const setMemoArray = (data: T) => {
          setSelectedState((currentArray: T[]) => {
            const index = currentArray.findIndex((item) => item.id === data.id);
            if (index !== -1) {
              const newArray = [...currentArray];
              newArray[index] = data;
              return newArray;
            }
            return currentArray;
          });
        };
    
        return {toggleItemInNewArray, setMemoArray};
      };
    

• 또한, 글 작성 시 useDebounce를 이용하여 불필요하게 지속 저장되는 것을 방지

  • useDebounce

      const useDebounce = (value: string, delay: number) => {
        const [debouncedValue, setDebouncedValue] = useState(value);
    
        useEffect(() => {
          const timer = setTimeout(() => {
            setDebouncedValue(value);
          }, delay);
    
          return () => {
            clearTimeout(timer);
          };
        }, [value, delay]);
    
        return debouncedValue;
      };

(2) 재 사용 가능한 공용 컴포넌트

• 전체적으로 동일하게 사용되는 모달을 공용으로 만들어 pr을 통해 공유
  • 모달
• 공용 컴포넌트 이외에도 checkbox, avatar, button 등 chakra UI를 이용한 공용 스타일 테마도 적용

2. ✍ 리팩토링 할 내용 정리하기

(1) 실시간 저장 기능 수정 실시간 저장 기능을 만들 때는 ‘실시간 저장’에 초점을 두어 구현했으나, 기능 완성 후에는 언마운트를 기준으로 저장해도 무관할 것 같다는 생각이 들었다. 이 부분은 추후 실시간 저장에서 언마운트 시 저장하도록 수정할 예정. 그리고 저장을 로컬스토리지 말고 다른 방법으로 할 수 있는지 더 고민해봐야겠다.

(2) 투표하기에서 투표의 상태 관리 투표의 상태는 여러가지로 나뉜다. ** '진행 중', '결정완료'** 로 투표 결정 완료 여부를 따지고, 또 '투표 전', '투표완료', '투표 결과 보기' 로 투표를 3가지 상태로 나눌 수 있다. '투표 결과 보기' 상태는 결정 여부와 관계 없이 가질 수 있고, 각 투표마다 가지고 있다. 문제는 이 결과보기 상태 값을 백에서 각 투표마다 가지고 있는게 아니라 전체 투표 리스트에서 배열로 주고 있기 때문에 프론트에서의 처리 과정이 조금 번잡하게 되어있다. 현재는 배열에 담긴 id와 투표id를 비교해서 boolean값을 recoil에 지정해 주었더니 이 부분에서 버그가 나고 있다. 특히 지도에서도 결과보기 값이 필요해서 url에 쿼리스트링을 넣는 방식으로 할까 싶은데 이게 맞는지는 아직 확신이 들지 않는다.

(3) 여행지 후보 지도 아마 2번이 해결되면 3번도 자연스럽게 해결 될 것 같지만 현재의 가장 큰 문제다. 카카오맵과 swiper를 연결해서, 하단의 슬라이드가 움직이면 센터 좌표도 바뀌도록 로직을 짰는데 결과보기 상태를 추가하고 나니 슬라이드 정렬에 문제가 생겼다. 이미지에서는 보이지 않지만 슬라이드를 넘길때마다 슬라이드가 복제되어 중복으로 보이고 있다. 좀 이상한건 모바일에서는 정상적으로 보이고 있다는 것. 우선, 결과보기 상태부터 해결하고 이 부분도 새로 코드를 작성해 봐야 할 것 같다.

(4) react 성능 최적화 항상 바로바로 해야하는 걸 알지만 어쩌다보니 항상 후순위로 밀려나 있다. 이번에는 위의 1-3 문제를 해결한 다음에 성능 최적화까지 해 볼 생각이다.

(5) 타입 정리 시간이 촉박해질 수록 타입을 지저분하게 작성한 부분이 있다. 아마 이부분 때문에 버그가 발생한 것도 있는 것 같아 같이 수정해야 한다.

리팩토링 이전 간단한 후기

PM부터 디자이너, BE까지 총 16명이서 진행한 2달의 프로젝트였다. 부트캠프에서 안내한 대략적인 기간은 12월에 기획과 디자인, 12월 26일부터 개발이었지만 개발 기간은 한 주 가량 밀리고 마감 직전 주까지도 기획과 자잘한 디자인이 바뀌었으며, API 스키마도 마감 직전 주에 확정되어서 마감 전날까지 계속해서 버그 수정을 했었다.

사실 같은 기능을 담당한 BE분의 작업이 점점 늦어 졌었는데, 알고보니 해당 팀원이 취업에 성공해서 작업 시간이 부족했던 거였다. 이 내용을 모두가 마감 3,4일 전에 알게 되었고, 그로 인해 다른 BE 분들이 남은 작업을 나눠 진행하게 되어 시간이 더 촉박했다.

개발 기간이 점차 밀리고 프론트엔드가 중간에서 정신 없을 거란 건 어느정도 예상하긴 했지만 막상 그 상황에 놓이게 되니 조급해지는 건 어쩔 수가 없었던 것 같다. 넉넉할거라 생각했던 기간은 다 같이 밤을 새며 작업을 해도 턱없이 많이 부족했고, 버그들이 남겨진 채로 마무리 된 게 아쉬웠다. 모두가 쉬는 사람 없이 다 같이 잠도 안자고 노력했던 터라 더 아쉬웠던 것 같다. 현업에서도 기획, 디자인 등 계속해서 변경된다는 이야기는 많이 들었는데 다들 어떻게 잘 해나가시는 건지 정말 궁금해졌다.

그리고 이전에도 느꼈지만 이번 프로젝트를 통해 다양한 팀과 협업하면서 더 확실히 느낀게 있다. 코드를 작성 하다 막혔을 때 최대한 짧은 시간 안에 처리하는 게 개발에 있어서 가장 중요하다는 것. 리팩토링을 하면서 다음에는 시간 분배를 어떻게 할지 같이 고민해 봐야겠다.

+ 난 recoil이랑 react-query(tanstack-query)가 너무 좋은 것 같다. 사용 방법도 간단하고 작성된 코드도 깔끔했다. 다만 프로젝트 3개를 두 조합으로 했더니 react만 쓰는 걸 잊은 것 같아 걱정이다. 리팩토링이 끝나면 react만 썼을 때는 어떻게 작성이 되는지 거꾸로 바꿔볼 예정이다.

✍ 소개

React를 기반으로 개발된 숙박 예약 서비스입니다. FE 5명, BE 3명이 참여했으며 약 2주간 개발했습니다.

공개용 Github : https://github.com/Yanolja-MiniProject-10/Yanolja-clone-fe 배포 링크 : https://yanolja.vercel.app/

Test ID : test@yanolja.com
Test PW : 00000

전체 시연 영상

!youtube[xnGrdf6tPFQ]

Skills

React, JavaScript, TypeScript, Recoil, Axios, React-Query, Vite, Github, Vercel, Styled Components

🧑🏻‍💻 담당 개발 내용

담당 - 첫 메인 페이지

• 상세 내용
  • 이벤트 캐러셀
  • 카테고리
  • 모든 숙소 둘러보기
  • 최근 본 상품의 연관 상품
  • 지역 별 상품 추천
  • 예약 숙소 랭킹
  • 푸터, 메인 내비바, 메인 헤더, 공통 헤더

주요 내용 요약

1. 컴포넌트 재 사용
2. recoil을 이용하여 연관된 상품 추천 기능 구현
3. react-query를 통해 api 호출 함수 컴포넌트 별 조건부 재 사용
4. 디자인 - 스켈레톤 UI 도입으로 UX 측면 고도화

1. 재사용 컴포넌트

• Common Header - 페이지 별 제목과 필요한 아이콘을 보여줍니다.

  • 영상 !youtube[BZPleJXjfsA]

  • 예시 이미지

• AllAndRelatedSwiper - [모든 숙소 둘러보기], [최근 본 상품의 연관 상품]

  • 영상

    !youtube[rTmzz2n5jIU]

 - 예시 이미지

2. 상품 추천 기능 구현 - [최근 본 상품의 연관 상품]

• 고객이 클릭해서 본 숙소에서 정보를 recoil에 저장하고 불러와 메인에 보여줍니다.
• 로그인을 하지 않거나, 클릭한 상품이 없을 경우 보여주지 않습니다.

3. react-query를 통한 api 호출 함수의 컴포넌트 별 조건부 재 사용

enabled을 사용하면 비동기 함수인 useQuery를 동기적으로 사용 가능하다.

const useFetchCarts = () =>
  useQuery({
    queryKey: ["fetchCarts"],
    queryFn: () => fetchCarts(),
  });

//api 호출 함수를 더 만들지 않고 useQuery를 추가하여 enable 사용
// 동일한 쿼리키를 사용하여, mutate를 동일하게 적용받도록 함

const useFetchCartCount = (user: UserToken) =>
  useQuery({
    queryKey: ["fetchCarts"],
    queryFn: () => fetchCarts(),
    enabled: !!user.accessToken,  // accessToken 유무로 user 로그인 상태일 때 실행
  });

4. 디자인

• 스켈레톤 UI

• 반응형

🧑🏻‍💻 Github

• Project를 이용한 진행 상황 처리

• Actions를 활용하여 CI/CD 경험

에러 및 고민한 점

위에서 기재했던 react-query를 통한 api 호출 함수의 컴포넌트 별 조건부 재 사용 부분이 오래 고민했던 곳이다. api 호출을 비동기로 사용했는데, api 호출을 조건에 따라 동기적으로 사용이 필요했기 때문이다. 유저가 로그인 상태일 때만 함수를 실행해야 하는 조건이었는데 custom hook의 경우 useEffect나 조건문에 넣지 못해서, 처음에는 api호출 함수에서 조건을 넣어봤지만 번번히 실패했다.

그러다 react-query의 enabled를 알게 되고 손쉽게 조건부 처리를 할 수 있었다.

const useFetchCartCount = (user: UserToken) =>
  useQuery({
    queryKey: ["fetchCarts"],
    queryFn: () => fetchCarts(),
    enabled: !!user.accessToken,  // accessToken 유무로 user 로그인 상태일 때 실행
  });

해당 게시글은 부트캠프 과정 중 수료 점수에 반영되어, 제목과 해시태그를 포함한 지정된 양식으로 작성되었습니다.

todos 앱을 배우며 모르는 부분이 있어 질의응답으로 이해한 부분을 기재한다.

//타입과 initialState
interface NoteState {
  mainNotes: Note[];
  archiveNotes: Note[];
  trashNotes: Note[];
  editNote: null | Note;
}
const initialState: NoteState = {
  mainNotes: [...notes],
  archiveNotes: [],
  trashNotes: [],
  editNote: null,
};
enum noteType {
  archiveNotes = "archiveNotes",
  trashNotes = "trashNotes",
  mainNotes = "mainNotes",
}


// Slice
const noteListSlice = createSlice({
  name: "noteList",
  initialState,
  reducers: {
    //중략

     readNote: (state, { payload }) => {
       //1. payload
      const { type, id } = payload;

      const setRead = (notes: noteType) => {
        //2. state
        state[notes] = state[notes].map((note: Note) =>
          note.id === id ? { ...note, isRead: !note.isRead } : note
        );
      };
          // noteType은 enum이다
      if (type === "archive") {
        setRead(noteType.archiveNotes); //"archiveNotes"
      } else if (type === "trash") {
        setRead(noteType.trashNotes); //"trashNotes"
      } else {
        setRead(noteType.mainNotes); //"mainNotes"
      }
    },
  },
});

// 사용하는 곳
<DeleteBox
   onClick={() => dispatch(readNote({ type, id: note.id }))}
   className="readNote__close-btn"
        >

1. payload

type, id를 객체로 받으며 payload에 할당

2. state

notes가 버라이어티한 string값이기 때문에 state.mainNotes = state.mainNotes.map 처럼 state.notes로 사용할 수 없다.

예를 들어 설명한다. notes = “archiveNotes” 이며, state.notes - state.“archiveNotes” 형태는 되지 않는다. state[notes] - state[“archiveNotes”] 로 작성해야, 결국 state.archiveNotes과 같아진다.

*간단 정리 *

setRead(noteType.archiveNotes) => setRead(“archiveNotes”)

state[notes] = state[“archiveNotes”] = state.archiveNotes

https://www.acmicpc.net/problem/9663

강의에서 제시한 문제 해결 아이디어

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 계산
• 모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)를 사용할 수 있다.
• 하나의 순열을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다. -> 이때, M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같다. -원소를 중복하여 선택하지 않으므로, 방문처리(visited) 배열을 사용한다. -> 한 번 선택된 원소는 다음 재귀 함수에서 다시 선택되지 않는다.

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]); // 전체 map의 크기
let queens = []; // 현재 체스판에 놓인 퀸(queen)의 위치 정보들

function possible(x, y) {
  // (x, y) 위치에 퀸을 놓을 수 있는지 확인
  for (let [a, b] of queens) {
    // 현재까지 놓았던 모든 queen의 위치를 하나씩 확인하며
    if (a == x || b == y) return false; // 행이나 열이 같다면 X
    if (Math.abs(a - x) == Math.abs(b - y)) return false; // 대각선 위치한 경우 X
  }
  return true;
}

let cnt = 0;
function dfs(row) {
  if (row == n) cnt += 1; // queen을 N개 배치할 수 있는 경우 카운트
  for (let i = 0; i < n; i++) {
    // 현재 행(row)에 존재하는 열을 하나씩 확인하며
    if (!possible(row, i)) continue; // 현재 위치에 놓을 수 없다면 무시
    queens.push([row, i]); // 현재 위치에 퀸 놓기
    dfs(row + 1); // 재귀함수 호출
    queens.pop(); // 현재 위치에서 퀸 제거
  }
}
dfs(0);
console.log(cnt);

정답 예시

제출 답안과 동일

2. 알파벳

https://www.acmicpc.net/problem/1987

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let [r, c] = input[0].split(" ").map(Number);
let arr = []; // 순열을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= r; i++) arr.push(input[i]);

let dx = [-1, 1, 0, 0]; // 상하좌우 방향
let dy = [0, 0, -1, 1];

let visited = new Set(); // 방문한 적 있는 알파벳 집합
let maxDepth = 0; // 최대 깊이

function dfs(depth, x, y) {
  maxDepth = Math.max(maxDepth, depth); //최대 깊이 계산
  for (let i = 0; i < 4; i++) {
    let nx = x + dx[i];
    let ny = y + dy[i];
    if (nx < 0 || nx >= r || ny < 0 || ny >= c) continue; // 맵을 벗어나면 무시
    if (visited.has(arr[nx][ny])) continue;
    visited.add(arr[nx][ny]); // 방문 처리
    dfs(arr, depth + 1); // 재귀 함수 호출
    visited.delete(arr[nx][ny]); // 방문처리 해제
  }
}
visited.add(arr[0][0]); // 왼쪽 위에서 출발
dfc(1, 0, 0);
console.log(maxDepth);

3. 부등호

https://www.acmicpc.net/problem/2529

강의에서 제시한 문제 해결 아이디어

• 총 10개의 숫자 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 중에서 중복 없이 모든 순열을 선택 한다.
• 선택한 뒤에 K 개의 부등호에 대한 순서를 만족하는지 확인한다.
• K는 최대 9까지 입력될 수 있다.

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let k = Number(input[0]);
let arr = input[1].split(' ');
let visited = new Array(10).fill(false);
let result = [];
let current = "";
let first = "";

dfs(0);
console.log(current + "\n" + first) // 마지막에 남은 current 값은 [가장 큰 문자열]


function dfs(depth) {
  if (depth == k+1) { //각 순열에 대한 처리
   let check = true; // 부등식을 만족하는지 확인
    for (let i = 0; i < k; i++) {
      if (arr[i] =="<") {
        if(result[i] > result[i+1]) check = false; // 부등식을 만족하지 않음
      }
      else if (arr[i] == '>') {
        if(result[i] < result[i+1]) check = false; // 부등식을 만족하지 않음
      }
    }
    if (check) { // 부등식을 만족하는 경우에
      current = "";
      for (let x of result) current += x + "";
      if ( first == "") first = current; // 첫째 문자열은 [가장 작은 수]
    }
    return;
     }
     for (let i = 0; i < 10; i++;) { // 0부터 9까지의 숫자를 하나씩 고르는 순열(백트래킹)
   if (visited[i]) continue; // 이미 고른 숫자라면 무시하도록
    visited[i] = true; // 현재 선택한 숫자 방문 처리
    result.push(i);
    dfs(depth + 1); // 재귀 함수 호출
    visited[i] = false; //현재 선택한 숫자 방문 처리 취소
    result.pop();
  }
}

https://www.acmicpc.net/problem/10971

강의에서 제시한 문제 해결 아이디어

• 외판원 순회(traveling salesman problem. TSP) 문제이다.
• 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아와야 한다. -> 어떤 노드에서 출발해도 무관

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]);
let graph = []; // 전체 그래프(graph) 정보 입력
for (let i = 0; i <= n; i++) graph.push([0]);
for (let i = 1; i <= n; i++) {
  line = input[i].split(" ").map(Number);
  for (let j = 0; j < n; j++) graph[i].push(line[j]);
}
let visited = new Array(11).fill(false); // 방문처리 배열
let result = []; // 순열 정보 배열
let minValue = 1e9;

dfc(arr, 0);
console.log(minValue);

// 2부터 N까지의 수를 하나씩 골라 나열하는 모든 순열을 계산
function dfs(arr, depth) {
  if (depth == n - 1) {
    //현재 순열에 대한 처리
    let totalCost = 0; // 1번 노드에서 출발
    let cur = 1; // 1번 노드에서 출발

    for (let i = 0; i < n - 1; i++) {
      // 현재 순열에 따라서 노드 이동
      let nextNode = result[i]; // 다음 이동 노드까지의 비용 계산
      let cost = graph[cur][nextNode];
      if (cost == 0) return; // 이동 불가능하면 무시
      totalCost += cost; // 이동 가능 -> 비용 더하고 노드 이동
      cur = nextNode;
    }
    // 마지막 노드에서 1로 돌아오는 것이 필수
    let cost = graph[cur][1];
    if (cost == 0) return; // 이동 불가능하면 무시
    totalCost += cost; // 이동 가능 -> 비용 더하고 노드 이동
    minValue = Math.min(minValue, totalCost); // 경로의 최소 비용 저장
  }
  for (let i = 2; i <= n; i++) {
    if (visited[i]) continue;
    result.push(i); // 방문 처리
    visited[i] = true;
    dfs(depth + 1); // 재귀 함수 호출
    result.pop(); // 방문 처리 해제
    visited[i] = false;
  }
}

2. 조합 - 도영이가 만든 맛있는 음식

https://www.acmicpc.net/problem/2961

강의에서 제시한 문제 해결 아이디어

• 모든 길이에 대한 가능한 모든 조합을 구하는 것

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]);
let arr = [];
for (let i = 1; i <= n; i++) {
  let [x, y] = input[i].split(" ").map(Number);
  arr.push([x, y]);
}
let visited = new Array(n).fill(false); // 각 원소 인덱스별 방문 여부
let result = []; // 현재 순열에 포함된 원소
let answer = 1e9;

function dfs(depth, start) {
  if (depth >= 1) {
    // 현재 조합에 대하여 결과 계산
    let totalX = 1;
    let totalY = 0;
    for (let i of result) {
      // 인덱스를 하나씩 확인하며
      let [x, y] = arr[i];
      totalX *= x;
      totalY += y;
    }
    answer = Math.min(answer, Math.abs(totalX - totalY));
  }
  for (let i = start; i < n; i++) {
    // 모든 조합 계산
    if (visited[i]) continue;
    visited[i] = true; // 방문 처리
    result.push(i);
    dfs(depth + 1, i + 1); // 재귀 함수 호출
    visited[i] = false; //방문 처리 해제
    result.pop();
  }
}
dfs(0, 0);
console.log(answer);

3. 로또

https://www.acmicpc.net/problem/6603

강의에서 제시한 문제 해결 아이디어

• 모든 조합을 고려해서 모든 조합을 출력하는 정도로 이해해도 무관

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

for (let i =0; i < input.length; i++) {
  let data = input[i].split(" ").map(Number);
  if (data[0] == 0) break; // 테스트 케이스 종료 조건
  else {
    n = data[0];
    arr = data.slice(1);
    visited = new Array(n).fill(false); // 각 원소 인덱스별 방문 여부
    selected = []; // 현재 조합에 포함된 원소
    answer = "";
    dfs(arr, 0,0);
    console.log(answer);
      }
}

function dfs(result, depth) {
  if (depth == 6) { // 모든 조합을 확인하는 부분(로또는 6개의 자연수로 구성)
    let result= []; // 조합 결과 저장 테이블
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " "; // 계산된 조합을 실질적으로 처리하는 부분
    answer += "\n";
    return;
  }
  // start 지점부터 하나씩 원소 인덱스를 확인하며
  for (let i = start; i < arr.length; i++) {

    if (visited[i]) continue; // [중복x] 이미 처리 된 원소라면 무시
    selected.push(i); // 현재 원소 선택
    visited[i] = true; // 방문 처리
    dfs(arr, depth + 1, i + 1); // 조합이므로, 재귀 함수 호출 시 다음 인덱스 넣기
    selected.pop(); // 현재 원소 선택 취소
    visited[i] = false; //방문 처리 취소
  }
}

https://www.acmicpc.net/problem/15650

강의에서 제시한 문제 해결 아이디어

• 5개의 수 [1, 2, 3, 4, 5]에서 3개를 고르는 모든 조합을 고려해보자.

• 깊이가 3인 경우를 고려한다.

• 경우의 수 : 10개

• 모든 조합의 수를 고려하기 위해 재귀 함수(백트래킹)을 사용할 수 있다.

• 하나의 조합을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다. -> 이때, M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같다.

• 원소를 중복하여 선택하지 않으므로, 방문처리(visited) 배열을 사용한다. -> 한 번 선택된 원소는 다음 재귀 함수에서 다시 선택되지 않는다. [조합] 재귀 함수를 호출할 때마다 (자식 노드로 갈수록) 선택되는 값이 커지도록 하는 것이 핵심 -> 순열 코드와 다른 점은 start 변수가 사용된다는 점 뿐이다.

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let [n, m] = input[0].split(" ").map(Number);
let arr = []; // 조합을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i); //
let visited = new Array(n).fill(false); //각 원소 인덱스별 방문 여부(중복 확인용)
let selected = []; // 현재 조합에 포함된 원소

let answer = "";
function dfs(arr, depth, start) {
  if (depth == m) {
    //모든 조합을 확인하는 부분
    let result = []; // 조합 결과 저장 테이블
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " "; // 계산된 조합을 실질적으로 처리하는 부분
    answer += "\n";
    return;
  }
  for (let i = start; i < arr.length; i++) {
    // start 지점부터 하나씩 원소 인덱스를 확인하며
    if (visited[i]) continue; //[중복X] 이미 처리된 원소라면 무시
    selected.push(i); // 현재 원소 선택
    visited[i] = true; // 현재 원소 방문 처리
    dfs(arr, depth + 1, i + 1); // 조합이므로, 재귀 함수 호출 시 다음 인덱스 넣기
    selected.pop(); // 현재원소 선택 취소
    visited[i] = false; // 현재 원소 방문 처리 취소
  }
}
dfc(arr, 0, 0);
console.log(answer);

2. 중복 순열 - N과 M (3)

https://www.acmicpc.net/problem/15651

강의에서 제시한 문제 해결 아이디어

• 1부터 N까지 자연수 중에서 M개를 고른 모든 수열을 계산. [중복 수열] 이때, 같은 수를 여러번 골라도 된다.

• 모든 조합의 수를 고려하기 위해 재귀 함수(백트래킹)을 사용할 수 있다.

• 하나의 조합을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다. -> 이때, M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같다.

• 원소를 중복하여 선택하므로, 방문처리(visited) 배열을 사용하지 않는다. -> 한 번 방문한(방문 처리된) 원소도 중복해서 또 방문할 수 있다.

• 따라서 기본 순열 코드에서 단순히 visited 변수를 제거한다.

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let [n, m] = input[0].split(" ").map(Number);
let arr = []; // 순열을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i);
let selected = []; // 현재 순열에 포함된 원소

let answer = "";
function dfs(arr, depth) {
  if (depth == m) {
    //모든 순열을 확인하는 부분
    let result = []; // 순열 결과 저장 테이블
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " "; // 계산된 순열을 실질적으로 처리하는 부분
    answer += "\n";
    return;
  }
  for (let i = 0; i < arr.length; i++) {
    // 하나씩 원소 인덱스를 확인하며
    if (visited[i]) continue; //[중복X] 이미 처리된 원소라면 무시
    selected.push(i); // 현재 원소 선택
    dfs(arr, depth + 1); // 재귀 함수 호출
    selected.pop(); // 현재원소 선택 취소
  }
}
dfc(arr, 0);
console.log(answer);

정답 예시

제출답안과 동일

3. 중복 조합 - N과 M (4)

https://www.acmicpc.net/problem/15652

강의에서 제시한 문제 해결 아이디어

• 1부터 N까지 자연수 중에서 M개를 고른 모든 조합을 계산한다.

• 오름차순이라는 점 (순서가 하나만 있다는 점)에서 조합으로 이해할 수 있다. [중복 조합] 이때, 같은 수를 여러 번 골라도 된다.

• 모든 조합의 수를 고려하기 위해 재귀 함수(백트래킹)을 사용할 수 있다.

• 하나의 조합을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다. -> 이때, M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같다.

• 원소를 중복하여 선택하므로, 방문처리(visited) 배열을 사용하지 않는다. -> 한 번 방문한(방문 처리된) 원소도 중복해서 또 방문할 수 있다.

• 따라서 기본 순열 코드에서 단순히 visited 변수를 제거한다. [조합] 재귀 함수를 호출할 때마다(자식 노드로 갈수록) 선택되는 값이 커지도록 하는것이 핵심이다. -> 순열 코드와 달리 start 변수가 사용된다.

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let [n, m] = input[0].split(" ").map(Number);
let arr = []; // 조합을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i); //
let selected = []; // 현재 조합에 포함된 원소

let answer = "";
function dfs(arr, depth, start) {
  if (depth == m) {
    //모든 조합을 확인하는 부분
    let result = []; // 조합 결과 저장 테이블
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " "; // 계산된 조합을 실질적으로 처리하는 부분
    answer += "\n";
    return;
  }
  for (let i = start; i < arr.length; i++) {
    // start 지점부터 하나씩 원소 인덱스를 확인하며
    selected.push(i); // 현재 원소 선택
    dfs(arr, depth + 1, i); // 조합이므로, 재귀 함수 호출 시 다음 인덱스 넣기
    selected.pop(); // 현재원소 선택 취소
  }
}
dfc(arr, 0, 0);
console.log(answer);

정답 예시

제출답안과 동일

https://www.acmicpc.net/problem/15649

강의에서 제시한 문제 해결 아이디어

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 모든 수열을 계산
• 모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)를 사용할 수 있다.
• 하나의 순열을 트리(tree)에서 리프 노드까지의 경로로 생각할 수 있다. -> 이때, M개의 원소를 뽑는 순열을 고려하는 것이므로, 깊이(depth)는 M과 같다.
• 원소를 중복하여 선택하지 않으므로, 방문처리(visited) 배열을 사용한다. -> 한 번 선택된 원소는 다음 재귀 함수에서 다시 선택되지 않는다.

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let [n, m] = input[0].split(" ").map(Number);

let arr = [];

function possible(x, y) {
  for (let [a, b] of arr) {
    if (a == x || b == y) return false; // 행이나 열이 같다면 X
    if (Math.abs(a - x) == Math.abs(b - y)) return false; // 대각선 위치한 경우 X
  }
  return true;
}

function dfs(row) {
  for (let i = 1; i < n; i++) {
    if (!possible(row, i)) continue;
    arr.push([row, i]);
    dfs(row + 1);
  }
}
dfs(1);
console.log(arr);

-오답 !

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let [n, m] = input[0].split(" ").map(Number);
let arr = []; // 순열을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i); // [ 1, 2, 3, 4 ]
let visited = new Array(n).fill(false); // [ false, false, false, false ] 각 원소 인덱스별 방문 여부
let selected = []; // 현재 순열에 포함된 원소

let answer = "";
function dfs(arr, depth) {
  if (depth == m) {
    //모든 순열을 확인하는 부분
    let result = []; // 순열 결과 저장 테이블
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " "; // 계산된 순열을 실질적으로 처리하는 부분
    answer += "\n";
    return;
  }
  for (let i = 0; i < arr.length; i++) {
    // 하나씩 원소 인덱스를 확인하며
    if (visited[i]) continue; //[중복X] 이미 처리된 원소라면 무시
    selected.push(i); // 현재 원소 선택
    visited[i] = true; // 현재 원소 방문 처리
    dfs(arr, depth + 1); // 재귀 함수 호출
    selected.pop(); // 현재원소 선택 취소
    visited[i] = false; // 현재 원소 방문 처리 취소
  }
}
dfc(arr, 0);
console.log(answer);

2. 모든 순열

https://www.acmicpc.net/problem/10974

강의에서 제시한 문제 해결 아이디어

• N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전 순으로 출력
• N의 값은 최대 8이다. -> 이때 모든 순열을 출력하므로 최대 경우의 수는 8!개이다.

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]);
let arr = []; // 순열을 계산하고자 하는 원소가 담긴 배열
for (let i = 1; i <= n; i++) arr.push(i);
let visited = new Array(n).fill(false); // 각 원소 인덱스별 방문 여부
let selected = []; // 현재 순열에 포함된 원소

let answer = "";
function dfs(arr, depth) {
  if (depth == n) {
    //모든 순열을 확인하는 부분
    let result = []; // 순열 결과 저장 테이블
    for (let i of selected) result.push(arr[i]);
    for (let x of result) answer += x + " "; // 계산된 순열을 실질적으로 처리하는 부분
    answer += "\n";
    return;
  }
  for (let i = 0; i < arr.length; i++) {
    // 하나씩 원소 인덱스를 확인하며
    if (visited[i]) continue; //[중복X] 이미 처리된 원소라면 무시
    selected.push(i); // 현재 원소 선택
    visited[i] = true; // 현재 원소 방문 처리
    dfs(arr, depth + 1); // 재귀 함수 호출
    selected.pop(); // 현재원소 선택 취소
    visited[i] = false; // 현재 원소 방문 처리 취소
  }
}
dfc(arr, 0);
console.log(answer);

정답 예시

제출답안과 동일

3. 0 만들기

https://www.acmicpc.net/problem/7490

강의에서 제시한 문제 해결 아이디어

• 1부터 N까지의 수를 오름차순으로 쓴 수열 [1,2,3, ...N]이 있다고 할때
• 이때 각 수 사이에 사용할 수 있는 연산으로는 다음의 세가지 연산이 있다.

1. (-)
2. (+)
3. 숫자 이어붙이기 (공백)

• 결과적으로 N이 주어졌을때, 수식의 결과가 0이 되는 모든 수식을 찾아야 한다.
• 테스트 케이스 및 자연수 N의 최댓값은 9이다.
• 3개의 연산 중에서 연속적으로 N번 선택하는 중복 순열 문제로 이해할 수 있다.
• 따라서 가능한 전체 경우의 수는 3의 8제곱이다.

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let testCase = Number(input[0]);
let n = 0;
let arr = [];

for (let tc =1; tc <= testCase; tc++) { // 각 테스트 케이스 처리
n = Number(input[tc]); // 자연수(N) 입력 받기
arr = [];
for (let i = 1; i <= n; i++) arr.push(i) // 1부터 N까지의 수 삽입
dfs([],0);
console.log()
}

function dfs(result, depth) {
  if (depth == n-1) { //현재 순열 처리(중복 순열)
    let str = ''; // 현재 수식 문자열
    for (let i = 0; i < n-1; i++) str += arr[i] +result[i];
    str += arr[n-1] +'';
    current = eval(str.split(' ').join('')); // 공백을 제거한 뒤에 수식 계산
    if (current == 0) console.(str); // 수식의 결과가 0이 되는 경우 출력
    return;
  }
  for (let x of [' ', '+', '-']) { // +,-,혹은 이어붙이기( )
    result.push(x);
    dfs(result, depth + 1); // 재귀 함수 호출
    result.pop();
  }
}

1. 백트래킹 (BackTracking)

• 일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용
• 추후에 공부할 DFS와의 차이점
  1. DFS보다 백트래킹이 더 많이 출제
  2. DFS는 일반적으로 완전 탐색 목적, 재귀 함수를 이용해 구현
  3. 백트래킹도 재귀 함수를 이용하는 것이 일반적이지만, 단순히 완전 탐색하는 것이 아니라 조건에 따라서 유망한 노드로 이동

1) 그래프 표현 방식

2. N-Queen 문제

• 예를들어 N = 8이라고 할 때
• 64개의 위치에 8개의 퀸을 설치하는 모든 조합의 수 = Combination(64,8)
• 따라서 단순히 모든 경우의 수를 전부 고려한다면? -> 각 퀸이 서로 공격이 가능한지 검사하는 방식을 사용한다면 경우의 수가 매우 커질 수 있다.

1) 문제해결 아이디어

• 완전 탐색을 하더라도 유망한 경우에 대해서만 탐색을 진행한다면?
• 그러한 백트래킹 방식을 사용하여 훨씬 경우의 수를 줄일 수 있다.

2) 문제 이해하기

• N개의 퀸을 놓기 위해서는 각 행마다 1개씩 퀸을 놓아야 한다.
• 하나의 A가 이미 존재하는 상태에서, 다른 퀸 B를 놓으려면 어떻게 해야 할까?

3) 문제 해결 방법

• 백트래킹 진행 시 경우의 수를 최대한 줄이는 방법 방법 : 이전까지 놓았던 퀸들과 상충되지 않는 조건을 만족하는 위치에 대해서만 재귀 함수를 호출 1) 재귀 함수를 통해 모든 경우의 수를 다 찾은 뒤, 각 경우마다 가능한지 검사하는 방법 2) 유망한 경우에 대해서만 재귀 함수를 호출하는 방법 -> 위 경우에서는 2) 방법이 더 효율적

3. 백트래킹의 기본 형태

4. N-Queen 문제 해결 아이디어

• 가능한 모든 조합의 수를 구하는 것

• 매 재귀함수마다 실제로 N x N 모든 위치를 볼 필요가 없다. [ 핵심 ] 맨 처음 행(row)부터 차례대로 퀸을 놓는다고 생각하면 가짓수를 훨씬 줄일 수 있다.

• N-Queen 문제는 가능한 조합을 계산하는 것, 현재 행의 이전 행으로 돌아갈 필요가 없다.

• 백트래킹은 기본적으로 가능한 노드에 대하여 계속해서 재귀적으로 함수 호출

• 백트래킹은 모든 경우의 수를 탐색하기에 적합하다.

• N-Queen 문제를 해결하기 위해서는 특정 위치(노드)의 가능 여부를 판단할 필요가 있다.

• 가능한 노드 여부는 다음의 두가지를 확인

5. N-Queen 정답 코드 예시

let n = 8; // 전체 map의 크기
let queens = []; // 현재 체스판에 놓인 퀸(queen)의 위치 정보들

function possible(x, y) {
  // (x, y) 위치에 퀸을 놓을 수 있는지 확인
  for (let [a, b] of queens) {
    // 현재까지 놓았던 모든 queen의 위치를 하나씩 확인하며
    if (a == x || b == y) return false; // 행이나 열이 같다면 X
    if (Math.abs(a - x) == Math.abs(b - y)) return false; // 대각선 위치한 경우 X
  }
  return true;
}

let cnt = 0;
function dfs(row) {
  if (row == n) cnt += 1; // queen을 N개 배치할 수 있는 경우 카운트
  for (let i = 0; i < n; i++) {
    // 현재 행(row)에 존재하는 열을 하나씩 확인하며
    if (!possible(row, i)) continue; // 현재 위치에 놓을 수 없다면 무시
    queens.push([row, i]); // 현재 위치에 퀸 놓기
    dfs(row + 1); // 재귀함수 호출
    queens.pop(); // 현재 위치에서 퀸 제거
  }
}
dfs(0);
console.log(cnt);

https://www.acmicpc.net/problem/10816

강의에서 제시한 문제 해결 아이디어

• 이진 탐색을 위해 데이터를 오름차순 정렬
• lowerBound()와 upperBound() 이해
• countByRange()를 사용

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]); //가지고 있는 개수
let numberArray = input[1].split(" ").map(Number); // 카드에 적힌 숫자 배열
let m = Number(input[2]); //쿼리 수
let queryArray = input[3].split(" ").map(Number); // 갯수 구해야할 배열

numberArray.sort((a, b) => a - b);

result = "";
for (x of queryArray) {
  let cnt = countByRange(numberArray, x, x);
  result += cnt + " ";
}

console.log(result);

//함수들
function lowerBound(arr, target, start, end) {
  while (start < end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] >= target) end = mid;
    else start = mid + 1;
  }
  return end;
}
function upperBound(arr, target, start, end) {
  while (start < end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] > target) end = mid;
    else start = mid + 1;
  }
  return end;
}
function countByRange(arr, leftValue, rightValue) {
  let rightIndex = upperBound(arr, rightValue, 0, arr.length);
  let leftIndex = lowerBound(arr, leftValue, 0, arr.length);
  return rightIndex - leftIndex;
}

• 정답! 정답 예시와 다른 점은 for of를 사용한 것

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]);
let arr = input[1].split(" ").map(Number);
let m = Number(input[2]);
let query = input[3].split(" ").map(Number);

arr.sort((a, b) => a - b);

answer = "";
for (let i = 0; i < m; i++) {
  let cnt = countByRange(arr, query[i], query[i]);
  answer += cnt + " ";
}
console.log(answer);

//함수 생략

2. 병사 배치하기

https://www.acmicpc.net/problem/18353

강의에서 제시한 문제 해결 아이디어

• 요구사항 : 전투력이 높은 병사가 앞쪽에 오도록 내림차순 정렬
  1. 배치과정에서는 특정 위치의 병사를 열외시키는 방법 사용
  2. 남은 병사의 수가 최대가 되도록 하는 것이 목표

✨ 특정한 수열에서 "가장 긴 증가하는 부분 수열"을 찾는 문제

• Long Increasing Subsequence(LIS) 알고리즘
• 부분 수열 : 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열

• 아이디어 : 현재 원소가 가장 크다면 뒤에 삽입하고, 그렇지 않다면 최대한 왼쪽의 원소와 교체

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]); //병사 수
let arr = input[1].split(" ").map(Number); // 병사 별 전투력

let cnt = [];
for (let i = 0; i < n; i++) {
  let a = arr[i];
  let b = arr[i + 1];
  if (a < b) cnt.push(b);
}

console.log(cnt.length);

-오답 : 출력된 숫자는 동일하지만 강의에서 제시한 형식을 사용하지 않았다.

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]); //병사 수
let arr = input[1].split(" ").map(Number); // 병사 별 전투력

arr.reverse(); // 순서를 뒤집어 최장 증가 부분 수열(LIS)문제로 변환

let d = [0]; // LIS배열
// 이진 탐색을 활용한 LIS 알고리즘 수행
for (x of arr) {
  if (d[d.length - 1] < x) {
    //마지막 원소보다 현재 원소 x가 크다면 가장 뒤에 넣기
    d.push(x);
  } else {
    //  x 이하인 원소가 있다면 가능한 왼쪽에 있는 원소와 x를 교체
    let index = lowerBound(d, x, 0, d.length);
    d[index] = x;
  }
}
console.log(n - (d.length - 1));

3. K번째 수

https://www.acmicpc.net/problem/1300

강의에서 제시한 문제 해결 아이디어

• "현재 mid보다 작거나 같은 데이터의 수가 K개 이상이 되는 조건"을 만족하는 mid중에서 가장 작을 값을 구하기
• 파라메트릭 서치 문제로 볼 수 있음

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]);
let k = Number(input[1]);

let arr = [];
for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) arr.push(i * j);
}

let start = 1;
let end = n ** n;

let result = 0;
while (start <= end) {
  let mid = parseInt((start + end) / 2);
  let total = 0;
  for (x of arr)
    if (mid <= x) {
    }
}

-오답 : 미제출 - for문으로 arr부터 만들고 정렬하려 했는데 잘못된 방법인 걸 깨달았다. 시간초과.

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0]); // 배열의 크기
let k = Number(input[1]); // 인덱스 k

let start = 1; // 배열에 존재할 수있는 가장 작은 값
let end = 10 ** 10; // 배열에 존재할 수 있는 가장 큰 값

let result = 0;
while (start <= end) {
  //이진 탐색 수행(반복적)
  let mid = parseInt((start + end) / 2); //현재의 중간점
  let total = 0; // mid보다 작거나 같은 데이터의 개수
  for (let i = 1; i <= n; i++) {
    total += Math.min(parseInt(mid / i), n);
  }
  if (total >= k) {
    //mid보다 작거나 같은 데이터의 개수 >= k
    result = mid; // result에 기록
    end = mid - 1; //탐색범위 왼쪽으로 이동
  }
  // mid보다 작거나 같은 데이터의 개수 < k
  else start = mid + 1;
}
console.log(result);

https://www.acmicpc.net/problem/2512

강의에서 제시한 문제 해결 아이디어

• 문제 요구사항 : 적절한 상한 금액을 찾는 것이 문제의 목표
• 전체 국가 예산이 485이고, 4개의 지방 예산 요청이 120, 110, 140,150이라고 하자 -> 상한 금액이 127인 경우, 배정 금액의 합이 120 + 110 + 127 + 127 = 484 이다.

1. 배정된 총 예산이 조건을 만족 -> 상한금액을 증가(최대화가 목표)
2. 배정된 총 예산이 조건을 만족 X -> 상한 금액을 감소

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0].split(" ")[0]); //지방의 갯수
let arr = input[1].split(" ").map(Number); // 지방의 예산요청
let m = Number(input[2]); // 총 예산

// 이진 탐색을 위한 시작점(start)과 끝점(end) 설정
let start = 1;
let end = arr.reduce((a, b) => Math.max(a, b));

let result = 0;
// 이진 탐색 수행(반복문)
while (start <= end) {
  let mid = parseInt((start + end) / 2);
  let total = 0; // 배정된 예산의 총액 계산
  for (x of arr) {
    // 각 지방에서 요청한 예산을 하나씩 확인하며
    total += Math.min(mid, x); // 예산 배정
  }
  if (total <= m) {
    // 조건 만족 -> 상한액 증가
    result = mid;
    start = mid + 1;
  } else {
    // 조건 만족 X -> 상한액 감소
    end = mid - 1;
  }
}
console.log(result);

2. 나무 자르기

https://www.acmicpc.net/problem/2805

강의에서 제시한 문제 해결 아이디어

• 문제의 목표 : 적절한 높이(height) 값 찾기
• 높이를 15로 설정한 경우 총 7만큼의 나무를 얻을 수 있다

1. 절단기의 높이가 올라가는 경우 : 얻을 수 있는 나무의 양 감소
2. 절단기의 높이가 내려가는 경우 : 나무의 양 증가

제출 답안

x -오답 : 코드는 1번과 거의 유사했는데 1번에서 변형을 어떻게 해야할지 몰랐다.

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

// 나무의 수(n), 가져갈 나무 길이(m)
let [n, m] = input[0].split(" ").map(Number);
let arr = input[1].split(" ").map(Number); // 각 나무 높이

// 이진 탐색을 위한 시작점(start)과 끝점(end) 설정
let start = 0;
let end = arr.reduce((a, b) => Math.max(a, b));

let result = 0;
// 이진 탐색 수행(반복문)
while (start <= end) {
  let mid = parseInt((start + end) / 2);
  let total = 0; // mid로 잘랐을 때 얻을 수 있는 나무의 양 계산
  for (x of arr) if (x > mid) total += x - mid;
  if (total < m)
    end = mid - 1; // 나무의 양이 부족한 경우 더 많이 자르기 (높이 내리기)
  else {
    // 나무의 양이 충분한 경우 덜 자르기(높이 올리기)
    result = mid; // 최대한 덜 잘랐을 때가 정답이므로 result에 기록
    start = mid + 1;
  }
}
console.log(result);

3. 랜선 자르기

https://www.acmicpc.net/problem/1654

강의에서 제시한 문제 해결 아이디어

• 요구사항 : 랜선의 개수 N개 이상을 얻을 수 있는 길이의 최댓값

1. 길이를 키우면, 얻을 수 있는 랜선의 수 감소
2. 길이를 줄이면, 얻을 수 있는 랜선의 수 증가

제출 답안

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

// 가지고 있는 개수(k), 필요한 개수(n)
let [k, n] = input[0].split(" ").map(Number);
let arr = [];
for (let i = 1; i <= k; i++) arr.push(Number(input[i]));

let start = 1;
let end = arr.reduce((a, b) => Math.max(a, b));

let result = 0;
while (start <= end) {
  let mid = parseInt((start + end) / 2);
  let total = 0; // 총 잘린 갯수
  for (x of arr) if (x > mid) total += parseInt(x / mid); //자른 갯수 확인
  if (total < n) end = mid - 1; // 갯수 부족하면 mid 줄이기
  else {
    result = mid;
    start = mid + 1;
  }
}
console.log(result);

-오답 : 결과값은 200으로 나오지만 오답 for 문 이후 if (x > mid) 불필요

정답 예시

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

// 가지고 있는 개수(k), 필요한 개수(n)
let k = Number(input[0].split(" ")[0]);
let n = Number(input[0].split(" ")[1]);
let arr = [];
for (let i = 1; i <= k; i++) arr.push(Number(input[i]));

let start = 1;
let end = arr.reduce((a, b) => Math.max(a, b));

let result = 0;
while (start <= end) {
  let mid = parseInt((start + end) / 2);
  let total = 0;
  for (x of arr) total += parseInt(x / mid);
  if (total < n) end = mid - 1;
  else {
    result = mid;
    start = mid + 1;
  }
}
console.log(result);

1. 이진 탐색 조건

변경할(최적화 할) 값 x에 대하여 f(x)가 단조 증가 혹은 단조 감소

• 단조 증가 함수 : x ≤ y 이면 f(x) ≤ f(y)인 경우 일반적으로 조건(constraint)은 f(x)에 대하여 정의된다.

2. 파라메트릭 서치(Parametric Search)

• 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다. 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
• 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다. 파라메트릭 서치 문제의 목적 함수 예시 :

3. 예산 문제

https://www.acmicpc.net/problem/2512

강의에서 제시한 문제 해결 아이디어

• 문제 요구사항 : 적절한 상한 금액을 찾는 것이 문제의 목표
• 전체 국가 예산이 485이고, 4개의 지방 예산 요청이 120, 110, 140,150이라고 하자 -> 상한 금액이 127인 경우, 배정 금액의 합이 120 + 110 + 127 + 127 = 484 이다.

1. 배정된 총 예산이 조건을 만족 -> 상한금액을 증가(최대화가 목표)
2. 배정된 총 예산이 조건을 만족 X -> 상한 금액을 감소

정답 예시 (파라메트릭 서치의 전형적인 코드 예시)

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().split("\n");

let n = Number(input[0].split(" ")[0]); //지방의 갯수
let arr = input[1].split(" ").map(Number); // 지방의 예산요청
let m = Number(input[2]); // 총 예산

// 이진 탐색을 위한 시작점(start)과 끝점(end) 설정
let start = 1;
let end = arr.reduce((a, b) => Math.max(a, b));

let result = 0;
// 이진 탐색 수행(반복문)
while (start <= end) {
  let mid = parseInt((start + end) / 2);
  let total = 0; // 배정된 예산의 총액 계산
  for (x of arr) {
    // 각 지방에서 요청한 예산을 하나씩 확인하며
    total += Math.min(mid, x); // 예산 배정
  }
  if (total <= m) {
    // 조건 만족 -> 상한액 증가
    result = mid;
    start = mid + 1;
  } else {
    // 조건 만족 X -> 상한액 감소
    end = mid - 1;
  }
}
console.log(result);

1. 정렬된 배열에서 특정 원소의 개수 구하기

• 코딩 테스트에서는 정렬된 배열에서 값이 특정 범위에 해당하는 원소의 개수를 계산하는 것을 종종 요구
• 이러한 문제를 해결하기 위해 lowerBound()함수와 upperBound() 함수를 사용할 수 있다.

2. 하한선과 상한선 함수

• lowerBound(arr, x) : 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 왼쪽 인덱스를 반환
• upperBound(arr, x) : 정렬된 순서를 유지하면서 배열 arr에 x를 넣을 가장 오른쪽 인덱스를 반환

3. lowerBound() 코드 예시

// 정렬된 순서를 유지하면서 배열에 삽일 할 가장 왼쪽 인덱스를 반환
function lowerBound(arr, target, start, end) {
  while (start < end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] >= target) end = mid; //최대한 왼쪽으로 이동하기
    else start = mid + 1;
  }
  return end;
}

4. upperBound() 코드 예시

// 정렬된 순서를 유지하면서 배열에 삽일 할 가장 오른쪽 인덱스를 반환
function upperBound(arr, target, start, end) {
  while (start < end) {
    let mid = parseInt((start + end) / 2);
    if (arr[mid] > target) end = mid;
    else start = mid + 1; //최대한 오른쪽으로 이동하기
  }
  return end;
}

5. countByRange()

• 정렬된 배열에서 값이 특정 범위에 속하는 원소의 개수를 계산
• 앞서 정의한 lowerBound() 함수와 upperBound() 함수를 이용해 구현할 수 있다.

// 값이 [leftValue, rightValue]인 데이터의 개수를 반환하는 함수
function countByRange(arr, leftValue, rightValue) {
  // 유의 : lowerBound와 upperBound는 end의 변수의 값을 배열의 길이로 설정
  let rightIndex = upperBound(arr, rightValue, 0, arr.length);
  let leftIndex = lowerBound(arr, leftValue, 0, arr.length);
  return rightIndex - leftIndex;
}

// 배열 선언
let arr = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9];
//값이 4인 데이터 개수 출력
console.log(countByRange(arr, 4, 4));
// 값이 [-1, 3] 범위에 있는 데이터 개수 출력
console.log(countByRange(arr, -1, 3));

이진 탐색 알고리즘 (Binary Search Algorithm)

1. 동작 방식

• 시작점(left)와 끝점(end)을 기준으로 탐색 범위를 명시

2. 시간 복잡도

• 각 단계마다 탐색 범위를 2로 나누는 것으로 이해할 수 있다.
• 이상적인 경우 매 단계마다 범위가 반으로 감소, 로그(log) 복잡도를 가진다.

3. 대표적인 사용법

• 매우 넓은 범위(억 단위 이상)에서 최적의 해를 찾아야 하는 경우
• 데이터를 정렬한 뒤에 다수의 쿼리를 날려야 하는 경우

4. 코드 예시 (재귀 함수)

// 재귀함수 소스코드 구현
function binarySearch(arr, target, start, end) {
  if (start > end) return -1; //없음
  let mid = parseInt((start + end) / 2);
  // 찾은 경우 중간점 인덱스 반환
  if (arr[mid] == target) return mid;
  //중간 점 > 찾는 값  일 때 왼쪽 확인
  else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
  // 중간 점 < 찾는 값  일 때 오른쪽 확인
  else return binarySearch(arr, target, mid + 1, end);
}

//n(원소의 개수)와 target(찾는 값)
let n = 10;
let target = 7;
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

// 이진 탐색 수행 결과 출력
let result = binarySearch(arr, target, 0, n - 1); //결과는 찾은 값의 인덱스
if (result == -1) console.log("원소가 존재하지 않습니다.");
else console.log(`${result + 1}번째 원소입니다.`);

5. 코드 예시 (반복문)

// 반복문 소스코드 구현
function binarySearch(arr, target, start, end) {
  while (start <= end) {
    let mid = parseInt((start + end) / 2);
    // 찾은 경우 중간점 인덱스 반환
    if (arr[mid] == target) return mid;
    //중간 점 > 찾는 값  일 때 왼쪽 확인
    else if (arr[mid] > target) end = mid - 1;
    // 중간 점 < 찾는 값  일 때 오른쪽 확인
    else start = mid + 1;
  }
  return -1;
}

//n(원소의 개수)와 target(찾는 값)
let n = 10;
let target = 7;
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

// 이진 탐색 수행 결과 출력
let result = binarySearch(arr, target, 0, n - 1); //결과는 찾은 값의 인덱스
if (result == -1) console.log("원소가 존재하지 않습니다.");
else console.log(`${result + 1}번째 원소입니다.`);

useRef

• 렌더링에 필요하지 않은 값을 참조할 수 있는 React Hook
• 변수 관리, 특정 DOM을 선택 할 때 사용

1. 사용

1) 변수관리

• state를 사용 시 state가 변하면 컴포넌트가 다시 렌더링되지만, ref를 사용하면 렌더링 되지 않는다. (생명주기 동안 ref값은 유지)

  2) 특정 DOM 선택하기

• js에서는 getElementId등을 사용하지만 react에서는 ref사용

• 엘리먼트에 포커스를 설정하거나 스크롤바 위치를 가져오는 등에서 사용

2. useRef 사용 방법

• useRef로 Ref 객체 생성 후 특정 DOM에 ref값으로 설정 -> Ref의 .current 값이 특정 DOM을 가리킴

const Test2 = () => {
  //Ref 생성
  const inputRef = useRef(null);

  const handleClick = () => {
    inputRef.current.focus();
  };
  return (
    <div>
        // 특정DOM에 ref 값으로 설정
      <ChildComponent ref={inputRef} />
      <button onClick={handleClick}>클릭</button>
    </div>
  );
};

3. useRef로 Custom Hook 만들기

1) 만들 Hook 설명

• 모달창이 있을 때 외부를 클릭해서 모달창 닫기

2) useOnClickOutside Hook 생성

import { useEffect } from "react";

export default function useOnClickOutside(ref, handler) {
  useEffect(() => {
    const listener = event => {
      // 클릭 시 ref.current가 없거나, 모달창 안이면 그냥 return
      if (!ref.current || ref.current.contains(event.target)) {
        return;
      }
      // 그 외(모달창 외부)에는 hadler(=모달창닫기)실행
      handler(event);
    };

    document.addEventListener("mousedown", listener);
    document.addEventListener("touchstart", listener);

    //useEffect에서 return은 언마운트될때 호출
    return () => {
      document.removeEventListener("mousedown", listener);
      document.removeEventListener("touchstart", listener);
    };
  }, [ref, handler]);
}

3) Hook 사용

• 사용할 컴포넌트에서 적용하기

  const ref = useRef(null);
  

//hadler로 모달 닫는 콜백함수 useOnClickOutside(ref, () => { setIsModalOpen(false); });

return ( //중략

npm install styled-components@latest

import styled from "styled-components";

const Banner = () => {
  //생략
  return (
      <>
        <Container>
             <HomeContainer>
             </HomeContainer>
        </Container>
       <>
  ) 
};

const Container = styled.div`
display: flex;
justify-content: center;
align-item: center;
flex-direction: column;
width: 100%
height: 100vh;
`;

export default Banner;

  function realtime() {
    const fetchList = (categoryId: any, imgId: any) => {
      // 유저가 선택한 카테고리와 이미지를 doc,과 field 명으로 받음
      const userRef = doc(db, categoryId, imgId);
      //onSnapshot으로 데이터를 받아 set
      const unsub = onSnapshot(userRef, (doc: any) => {
        setCommentList(doc.data().comments);
      });
      return unsub;
    };
    return fetchList(categoryId, imgId);
  }

  useEffect((): any => {
    if (comment !== '') {
      uploadCommentList(imgId, categoryId, comment);
      realtime();
    }
    setComment('');
  }, [isChange, doc, onSnapshot]);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

//n개의 공, k개의 바구니
let [n, k] = input[0].split(' ').map(Number);

let sum = [];
for (let i = 1; i < k+1; i++) { //연속적으로 수를 더하고 배열에 넣기
  sum.push(i);
}

// 연속적인 합의 값 더하기
let newSum = [...sum].reduce((prev, curr) => prev + curr);

//공의 개수와 비교
newSum==n
? console.log(sum[sum.length - 1]-1)
: console.log(-1)

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let n = Number(input[0].split(' ')[0]);
let k = Number(input[0].split(' ')[1]);

let summary = 0; // 1부터 k까지의 합
for (let i = 1; i < k+1; i++) { 
  summary += i;
}
if (summary > n) { // 공의 개수 부족
  console.log(-1);
}
else { // 공의 개수 충분
  n -= summary;
  if(n % k == 0) console.log(k-1); //k개에 각각 1씩 더하기
  else console.log(k);
}

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

//문자열 개수
let t = Number(input[0]);
//문자열
let arr = [];
for(let i = 1; i <=n; i++) arr.push(input[i]);

//1. 회문인지 0
//2. 유사회문 1
//3. 둘다 아닌지 2

for (let text of arr) {
  // 문자열 비교
  for (let j = 1; j <parseInt(text.length/2); j++)
  if (text[j-1] == text[text.length-1-j]) console.log(0) //회문일 때 0
  else if (text[j-1] !== text[text.length-1-j]) {
    // 해당원소 제거 or 반대편 원소 제거
  }
}

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

function palindrome(x) {
  return x == x.split('').reverse().join('');
}

let testCases = Number(input[0]);
for (let tc = 1; tc <=testCases; tc++) { //문자열 입력받기
  let data = input[tc];
  if (palindrome(data)) console.log(0); // 회문인 경우
 else {
  let found = false;
  let n = data.length; // 문자열 길이
  for (let i = 0; i < parseInt(n / 2); i++) {
    if (data[i] != data[n - i - 1]) { //대칭 아닌 인덱스 찾은 경우
    //앞쪽의 해당 원소 제거 후 회문 검사
    if(palindrome(data.slice(0, i) + data.slice(i+1,n))) found = true; //해당원소 기준으로 앞뒤문자만 붙임
    //앞쪽의 해당 원소 제거 후 회문 검사
    if(palindrome(data.slice(0, n - i - 1) + data.slice(n - i, n))) found = true;
    break;
    }
  }
  if(found) console.log(1); //유사 회문
  else console.log(2); //둘다 아님
  }
}

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');


//x보다 작거나 같으면서 가장 가까운 2^i를 찾는 함수
function nearestSquare(x) {
  let i = 1;
  while (( 2 ** i) <= x) i += 1;
  return i - 1;
}


let length = Number(input[0].split(' ')[0]);
let width = Number(input[0].split(' ')[1]);
let height = Number(input[0].split(' ')[2]);
let cubes = Array(20).fill(0);

let n = Number(input[1]);
for(let i = 2; i <=n +1; i++) {
  let a = Number(input[i].split(' ')[0]);
  let b = Number(input[i].split(' ')[1]);
  cubes[a] = b;
}

let size = 19;
size = nearestSquare(length);
size = Math.min(size, nearestSquare(width));
size = Math.min(size, nearestSquare(height));

let res = 0;
let used = 0;

for (let i = size; i >= 0; i--) {
  used *= 8; // 채널, 너비, 높이가 2씩 줄었으므로 큐브의 개수는 8배 증가
  cur = (2 ** i); //현재의 정육면체 큐브의 길이
  //채워넣어야 할 큐브의 개수 계산
  let required = parseInt(length /cur)
    * parseInt(width /cur)
    * parseInt(height /cur)
    - used;

  let usage = Math.min(required, cubes[i]); // 이번 단계에서 넣을 수 있는 큐브의 개수
  res += usage;
  used += usage; 
}

if (used == length * width * height) console.log(res); //박스를 가득 채운 경우
else console.log(-1) // 박스를 가득 채우지 못한 경우

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let city = Number(input[0]);
let dArray = input[1].split(' ').map(Number); //거리
let pArray = input[2].split(' ').map(Number); //비용

let lowest = pArray[0]; //최저가

let total = pArray[0] * dArray[0]; //초기값 설정

for (let i = 1; i<dArray.length -1; i++) {
  if (lowest >= pArray[i]) { //최저가 비교
      lowest = pArray[i];
      for (let j = 1; j<dArray.length; j++) {
        //최저가를 거리에 곱해서 총 가격(total)에 더하기
        total += lowest * dArray[j]
      }
  }
}

console.log(total);

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

let n = Number(input[0]);
let dist = input[1].split(' ').map(Number);
let cost = input[2].split(' ').map(Number);

//주유비용(cost) 배열의 값을 비오름차순이 되도록 변환
// [5, 2, 4, 1] => [ 5, 2, 2, 1]
let minCost = cost[0];
for (let i = 0; i < n; i++) {
  minCost = Math.min(minCost, cost[i]);
  cost[i] = minCost;
}

//도로당 이동 비용의 합 계산
let answer = BigInt(0);
for (let i = 0; i < n-1; i++) {
  //JS에서 큰 정수 처리할때 BigInt 사용
  answer += BigInt(dist[i]) * BigInt(cost[i]);
}
console.log(String(answer)); // 뒤에 붙는 'n'제거

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

//회의의 수
let n = Number(input[0]);
//회의정보
let arr = [];
for(let i = 1; i <=n; i++) {
  let start = Number(input[i].split(' ')[0]);
  let end = Number(input[i].split(' ')[1]);
  arr.push([start, end]);
}

// 시작시간 오름차순 정렬
arr.sort((a,b) => a[0] - b[0]);

let cnt= 0;
let first = arr[0][0];
for (let i = 1; i<n; i++) {
  if(first = arr[i][0]){  // 시작시간이 같은 회의 수대로 count 시도
    first = arr[i][0];
    cnt += 1;
  }
}

console.log(cnt);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

//회의의 수
let n = Number(input[0]);
//회의정보
let arr = [];
for(let i = 1; i <=n; i++) arr.push(input[i].split(' ').map(Number));

// 1.종료시점, 시작시점을 우선순위로 오름차순 정렬
arr.sort(function(a,b) {
  if(a[1] != b[1]) return a[1] - b[1];
  else return  a[0] - b[0]; //종료시점 같으면 시작순으로 정렬
});
let cnt= 1, cur = 0;
for (let i = 1; i<n; i++) {
  if(arr[cur][1] <= arr[i][0]){  //현재 회의 종료 후 시작되는 경우 카운트
    cur = i;
    cnt += 1;
  }
}
console.log(cnt);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

//풍선 개수
let n = Number(input[0]);
//풍선 높이
let arr = input[1].split(' ').map(Number);

let cnt= 1;
let height = arr[0];
for (let i = 1; i<n; i++) {
  if((height - arr[i]) < 1) {
    height = arr[i];
    cnt += 1;
  }
  else height = arr[i];
}

console.log(cnt); 

const rl = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];
rl.on('line', function(line) {
  input.push(line);// 콘솔 입력창에서 줄바꿈 입력마다 호출
}).on('close', function() {
  let data = input[1].split(' ').map(Number); // 모든 풍선의 위치 정보
  let result = 0;
  let arrow = new Array(1000001).fill(0); // 각 높이에 화실이 몇 개 있는지
  for (let x of data) {
    if (arrow[x] > 0) { // 해당 높이에 화살이 있다면
        arrow[x] -= 1;
        arrow[x-1] += 1;
      } else { // 해당 높이에 화살이 없다면
        arrow[x-1] += 1;
        result += 1; // 화살 쏘기
      }
    }
    console.log(result);
    process.exit();
});

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

// 피보나치 계산
pibo = [];
pibo.push(0);
pibo.push(1);
while (pibo[pibo.length - 1] < 1e9) pibo.push(pibo[pibo.length - 2] + pibo[pibo.length - 1]);



//총 개수
let testCases = Number(input[0]);
//데이터
for(let tc = 1; tc <= testCases; tc++) {
  let n = Number(input[tc]);
  let result = [];
  let i = pibo.length -1 // 가장 큰 피보나치 수의 인덱스
  while (n>0) { // n이 0이 될때까지
    if (n >= pibo[i]) {// 가능한 큰 피보나치 수 부터 빼기
    n -= pibo[i];
    result.push(pibo[i]);
    }
    i--;
  }
   let answer = "";
for (let i = result.length - 1; i >= 0; i--) 
  answer += result[i] + " "; //오름차순 출력
console.log(answer); 
}

let fs = require('fs');
let input = fs.readFileSync('./dev/stdin').toString().split('\n');

let n = Number(input[0]);
let cnt = 0;
let flag = false;

while (n >= 0) {
  //n이 0이 되었거나, n로 나누어 떨어지는 값인 경우
  if ( n== 0 || n% 5 == 0) {
    cnt += parseInt(n/5);
    console.log(cnt);
    flag = true;
    break;
  }
  n -= 3;
  cnt += 1;
}
if (!flag) {
console.log(-1);
}

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

// 
let a = Number(input[0].split(' ')[0]);
let b = Number(input[0].split(' ')[1]);

let cnt = 0;

function count(b) {
  while (a = b) {
    if ( b% 2 == 0) {
      b /= 2;
      cnt++;
    } else {
    b = (b - 1)/10;
    cnt++;
    }
  }
  return a = b ? cnt : -1;
}

console.log(count(b));

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let [a, b] = input[0].split(' ').map(Number);
let flag = false;
let result = 1;

while (a <= b) {
  if (a == b) {  //  a와 b가 같아질 때 탈출
    flag = true;
    break;
  }
  if (b%2 == 0) b = parseInt(b / 2); // 2로 나누어 떨어지는 경우
  else if (b % 10 == 1) b = parseInt(b/10); // 그렇지 않고, 일의 자리수가 1인 경우
  else break; // 위의 경우가 모두 해당되지 않는 경우
  result++;
}

if (flag) console.log(result);
else console.log(-1);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

// 
let s = Number(input[0]);

// 누적 시작
let cur = 0;
//총합
let sum = 0;

while ( sum <= s ) {
  cur += 1;
  sum += cur;
}
console.log(cur);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let s = Number(input[0]);
let cur = 0;
let sum = 0;

while ( sum <= s ) {
  cur += 1;
  sum += cur;
}
console.log(cur-1);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let testCase = Number(input[0]); //테스트케이스 개수
let n = Number(input[1]); // 지원자수
let arr = [];
for(let i = 2; i <=n; i++) {
  let [x, y] =  input[i].split(' ').map(Number);
  arr.push([x,y]);
}

arr.sort((a,b) => a[0] - b[0]); // 서류심사 성적순

let select = arr[0][1]; //비교 기준
let cnt = 0;
// 면접시험 비교
for (let j=1; j<arr.length; j++) {
  if (select >arr[j][1]) {
  select = arr[j][1];
  cnt += 1;
  }
}

console.log(cnt);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let testCase = Number(input[0]); 
let line = 1;
for(let tc = 0; tc <testCase; tc++) {
  let n = Number(input[line]);
  let arr = [];
  for (let i = line + 1; i <=line +n; i++) {
    let data =  input[i].split(' ').map(Number);
    arr.push(data);
    }
arr.sort((x,y) => x[0] - y[0]);
let count = 0;
let minValue = 100001;
for (let [x,y] of arr) {
  if (y < minValue) {
    minValue = y;
    count += 1;
  }
}
console.log(count);
line += n + 1;
}

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split('\n');

//동전 n종류, 총 합 k
let [n, k] = input[0].split(' ').map(Number);

// 동전 종류 n개만큼 가져오기
let arr = []
for(let i = 1; i <=n; i++) {
  arr.push(Number(input[i]))
};

//내림차순 정렬
arr.sort((a,b) => b-a);

let coin = [];

//몫을 정수로 구해서 coin 배열에 넣어주고, 나머지를 다시 반환
for (let x = 0; x < arr.length; x++) {
  if (arr[x] < k) {
  coin.push(parseInt(k / arr[x]))
  return k %= arr[x]
  }
}

//coin 배열의 값 모두 더해서 출력
let answer = 0;
for (let i = 0; i < coin.length; i++ ) {
  answer += coin[i];
}

console.log(answer);

for (let x = 0; x < arr.length; x++) {
  if (arr[x] < k) {
    console.log(arr[x])
    }}

  if (arr[x] < k) {  
  console.log(parseInt(k / arr[x]))
  return k %= arr[x]
  }

let fs = require('fs');
let input = fs.readFileSync('./input.txt').toString().split('\n');

let n = Number(input[0].split(' ')[0]);
let k = Number(input[0].split(' ')[1]);

let arr = [];
for(let i = 1; i <=n; i++) arr.push(Number(input[i]));

let cnt = 0;
// 총개수 n개에서 n-1 = 뒤에서부터 시작, 내림차순이 된다
for (let i = n-1; i>=0; i--) { 
  cnt += parseInt(k/arr[i]); // 해당 동전 몇개 사용 (몫)
  k%= arr[i]; // 해당 동전으로 거슬러 준 뒤 남은 금액 (나머지)
}

console.log(cnt);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

// 사람 수
let n = input[0].split(' ').map(Number);
// 각 사람이 돈을 인출하는데 걸리는 시간
let arr = input[1].split(' ').map(Number);
//시간 적게 소요되는 사람 우선 정렬
arr.sort((a,b) => a-b);

let answer = 0;

for (let i = 0; i < n; i++) { 
  arr.reduce((acc, cur) => acc += cur) // 누적해서 누적값 리턴(으로 생각)
  answer += acc;  //Error - acc 밖으로 뺄 수 없음
}
console.log(answer);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');


let n = Number(input[0]);
let arr = input[1].split(' ').map(Number);

arr.sort((a,b) => a-b);

let answer = 0;
let summary = 0;

for (let i = 0; i < n; i++) { 
  summary += arr[i];
  answer += summary;
}
console.log(answer);

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let minus = input[0].split('-');

// 미완성 미제출

let fs = require('fs');
let input = fs.readFileSync('dev/stdin').toString().split('\n');

let groups = input[0].split('-'); // [ '55', '50+40' ]
let answer = 0;

for (let i = 0; i < groups.length; i++) {
  // 각 그룹 내부에서 덧셈 연산 적용
  let cur = groups[i].split('+').map(Number).reduce((a,b)=> a+b);
  if(i == 0) answer += cur // 첫번째 그룹은 항상 덧셈
  else answer -= cur; // 두번째 그룹부터 뺄셈
}
console.log(answer);