[Core] Next.js (App Router)

Next.js를 사용하는 주된 이유는 SSR을 구현하기 위함 입니다. 오피스너 웹 버전에서는 건물명을 검색했을 때 사용자들이 유입될 수 있어야 합니다. 이를 위해서는 SEO 최적화가 필요하므로 Next.js 사용이 보다 유리합니다.

• React 기반의 프레임워크로, 서버 사이드 렌더링(SSR)과 정적 사이트 생성(SSG)을 쉽게 처리할 수 있어서 검색 엔진 최적화(SEO)에 유리합니다.
• 초기 페이지 로딩에 대해서는 SSR, SSG 방식으로 동작시킬 수가 있고, 이후의 요청에 대해서는 기본적으로 CSR 방식으로 동작하기 때문에 SSR 방식의 장점인 SEO에 유리하면서도 CSR의 장점을 활용할 수 있습니다.
  
  

[Styling] TailwindCSS

TailwindCSS는 스타일링을 쉽게 하기 위한 CSS 프레임워크입니다.

• 유틸리티 기반 CSS 프레임워크로, 제공되는 CSS 클래스들을 이용해서 빠르게 웹 페이지의 스타일을 지정할 수 있습니다.
• 쉽게 말하자면, 디자인의 기본 재료들을 제공하는 도구라고 할 수 있습니다.
• 페이지의 레이아웃이나 텍스트, 색상, 여백 등을 세밀하게 조정해야할 때 사용합니다. 예를 들어, 버튼의 크기, 색깔, 배경색 등을 조정할 수 있습니다.
• 다만 클래스를 남용하면 코드가 복잡해 보일 수 있어서, 일관된 구조로 작성하는 것이 좋습니다.
  
  

[Styling] Radix UI

Radix UI는 Headless UI 라이브러리로, 쉽게 말하자면 디자인 없이 기능만 제공하는 UI 라이브러리입니다. 사용자가 원하는 스타일로 쉽게 커스터마이징 할 수 있습니다.

• Radix UI 공식 문서를 살펴보면, "Core building blocks for your design system”이라는 문구를 확인할 수 있습니다. 해석해보면, “나만의 디자인 시스템을 만들기 위한 핵심 빌딩 블록”이라는 의미겠네요.
• Radix UI는 기본적인 UI 구성 요소를 제공하면서도 스타일링과 디자인은 제공하지 않습니다. 즉, UI 요소의 구조와 동작은 제공하지만, 스타일링은 개발자가 직접 지정할 수 있습니다.
• 따라서 반응형에 의해 디자인이 달라지거나, 기능 변경이나 추가가 많이 발생한다면 Headless가 유지보수에 더 유리하겠네요.
• 웹 접근성을 보장하는 UI 라이브러리라서, 디자인 시스템을 별도로 사용하면서도 접근성을 보장할 수 있다는 장점이 있습니다.
  

왜 Headless UI 라이브러리가 필요할까?

• Material UI나 Bootstrap과 같은 UI 라이브러리들은 각자만의 스타일이 입혀져 있기 때문에 회사에서 설계한 디자인과 다른 경우들이 많습니다. 오피스너의 경우에도 오피스너만의 디자인이 설계되어 있죠.
• 이러한 UI 라이브러리의 테마를 커스터마이징해서 문제를 해결할 수 있지만, 완벽하게 원하는 디자인으로 만드는 작업이 다소 번거로울 수 있습니다.
• 그렇다고 개발자가 처음부터 다 만들기엔 웹 접근성을 준수하며 개발하기가 어렵습니다.
• 그래서 이런 니즈들로 인해, 접근성을 보장하면서 기능을 제공하는 Headless UI 라이브러리가 등장하게 됐습니다.
  
  

[Styling] shadcn/ui

기능(Radix UI)과 디자인(TailwindCSS)이 잘 결합된 코드 모음(컴포넌트)이라고 생각하면 됩니다.

• 다시 한번 말하자면, Radix UI에 TailwindCSS의 스타일링을 곁들여, 가공된 컴포넌트로 제공하는 UI 모음집(Component Collection)입니다.
• 라이브러리가 아니기 때문에, npm 패키지 형태가 아닌, 컴포넌트를 복사 붙여넣기 하는 제공 방식을 택하고 있습니다. (패키지 매니저 사용이 아닌 npx 명령어 사용)
• 왜 복붙 방식을 하느냐면, 커스터마이징 자유도를 높이기 위해서라고 생각하면 될 것 같습니다. 또한 의존성을 주입시키지 않음으로써 불필요한 번들 크기 증가를 막을 수 있습니다.
  
  

[State Management] React Query

서버 상태 관리에 사용되는 라이브러리로, 비동기 데이터(fetching)를 쉽게 관리 할 수 있도록 도와줍니다. 즉, 서버에서 가져오는 데이터를 효율적으로 관리하기 위해 사용합니다.

• 서버에서 데이터를 가져오고(API 요청 결과), 캐싱하고, 재요청(동기화)하는 작업들을 쉽게 처리할 수 있습니다.
• 데이터를 불필요하게 너무 자주 요청하지 않도록 설정하고, 캐싱이 필요한 시점에만 적절히 캐싱을 사용해 성능을 최적화하는 것이 중요합니다.
  
  

[State Management] Zustand

클라이언트 상태 관리를 위해 사용되는 가벼운 전역 상태 관리 라이브러리입니다.

• 테마(라이트/블랙 모드)나 로그인 상태, 사용자 정보와 같은 데이터를 여러 컴포넌트에서 공유해야 할 때 사용합니다.
• 상태 관리가 너무 복잡해지지 않도록 하는 것이 중요하고, 컴포넌트가 필요 이상으로 상태를 구독하지 않도록 신경써야합니다.

🔥 학습 방향

1. next-auth를 사용하여 로그인 기능 구현을 할 예정이므로 이에 대한 학습이 필요할 것 같습니다.
2. 로그인/회원가입 기능 구현 시 유효성 검사를 효율적으로 하기 위해 React Hook Form 도입을 고려해봐야 할 것 같습니다. React Hook Form과 Zod를 함께 사용하면 폼 제출 시 유효성 검사를 효율적으로 수행할 수 있을 것 같습니다.
3. React Query의 경우 캐싱 기능을 제공하는데, 무분별한 캐싱은 되려 성능 저하를 발생시키므로 React Query를 학습하며 캐싱 처리에 대해 생각해보면 좋을 것 같습니다.
4. Zustand를 사용할 때, 클라이언트 상태 관리가 필요한 정보가 뭘지 생각해보며 개발하면 좋을 것 같습니다.

1. Live Server

웹 개발을 하면서 HTML, CSS, JS 파일을 수정할 때마다 브라우저를 새로고침해야 하는 번거로움이 있습니다. Live Server는 이를 해결하기 위한 확장 기능으로, 파일을 저장할 때마다 자동으로 브라우저를 새로고침해줍니다.

2. Prettier

코드 포맷팅은 일관된 코드 스타일을 유지하고 가독성을 높이기 위해 중요합니다. Prettier는 다양한 프로그래밍 언어에 대해 일관된 코드 포맷팅을 제공하는 확장 기능입니다.

3. ESLint

ESLint는 자바스크립트 코드에서 일반적인 오류를 검사하고, 코드 스타일 가이드를 준수하는지 검사하는 확장 기능입니다. 코드의 품질을 높이고 유지 보수성을 높이기 위해 ESLint를 사용하는 것이 좋습니다.

4. GitLens

GitLens는 Git 저장소의 커밋 기록을 시각화하고, 각 커밋에 대한 정보를 제공하는 확장 기능입니다. 코드 변경 내역을 빠르게 확인할 수 있어, 협업하면서 코드를 관리할 때 유용합니다.

5. Material Icon Theme

VSCode는 파일의 확장자에 따라 아이콘을 제공합니다. 하지만 이 아이콘은 파일의 종류를 구분하기에는 충분하지 않을 때가 있습니다. Material Icon Theme은 다양한 아이콘을 제공하여 파일의 종류를 더 쉽게 구분할 수 있게 해줍니다.

6. Bracket Pair Colorizer

소스 코드에서 괄호의 쌍이 맞아야 하는 경우가 많습니다. 이때 Bracket Pair Colorizer는 괄호의 쌍을 쉽게 확인할 수 있도록 쌍을 색상으로 강조해주는 확장 기능입니다.

7. Remote Development

Remote Development는 VSCode를 사용하여 원격 서버나 도커 컨테이너, WSL 등의 환경에서 개발할 수 있게 해주는 확장 기능입니다. 로컬에서 개발하지 않아도 되므로 환경 설정 등의 번거로움을 줄여주며, 원격 개발 환경에서도 VSCode의 모든 기능을 사용할 수 있습니다.

8. Better Comments

주석은 코드의 이해를 돕기 위해 작성되지만, 일반적인 주석은 그저 글씨로 보여지기 때문에 가독성이 떨어지는 경우가 많습니다. Better Comments는 주석의 가독성을 높이기 위한 다양한 스타일을 제공하는 확장 기능입니다.

9. Auto Close Tag

HTML이나 XML 같은 마크업 언어에서 태그를 작성할 때, 시작 태그와 종료 태그를 일일히 작성하는 것은 번거로운 작업입니다. Auto Close Tag는 시작 태그를 작성할 때 자동으로 종료 태그를 추가해주는 확장 기능입니다.

10. Code Runner

특정 파일에서 코드를 실행하고 결과를 확인하는 것은 프로그래밍 공부를 할 때 유용합니다. Code Runner는 VSCode에서 다양한 언어로 작성된 코드를 바로 실행할 수 있도록 지원하는 확장 기능입니다.

11. Live Share

Live Share는 원격에서 실시간으로 코드를 공유하고, 페어 프로그래밍을 할 수 있도록 지원하는 확장 기능입니다. 같은 코드를 함께 작성하면서 피드백을 주고받아 개발 생산성을 높일 수 있습니다.

12. Code Spell Checker

코드를 작성할 때 철자 오류가 발생할 수 있습니다. Code Spell Checker는 영어 철자 검사를 지원하는 확장 기능으로, 코드를 작성하는 도중 오타를 찾아주고 수정할 수 있습니다.

13. IntelliSense for CSS, SCSS, Less

CSS, SCSS, Less 같은 스타일 시트 언어에서 클래스, ID, 속성 등을 자동 완성해주는 IntelliSense 기능을 제공하는 확장 기능입니다.

14. REST Client

REST API를 테스트하거나 디버깅할 때 유용한 REST Client는 VSCode에서 HTTP 요청을 보내고 응답을 받을 수 있는 확장 기능입니다.

15. Indent Rainbow

들여쓰기를 시각적으로 확인할 수 있도록 색상을 입혀주는 Indent Rainbow는 코드 가독성을 높이는데 도움을 주는 확장 기능입니다.

💡 React Query

• 서버 데이터 관리하기에 적합하다.
• 데이터 Fetching, 캐싱, 동기화, 서버 데이터 업데이트 등을 쉽게 만들 수 있다.
• Redux에 비해 보일러 플레이트가 적다.
• 캐싱 처리가 간단해진다.
• 다양한 옵션을 사용 가능하다. (Redux에서는 직접 로직을 작성해야 한다.)
• onSuccess/onError 핸들링 간편하게 처리 가능
• React Query로 서버 데이터를 관리한다면, 이외 클라이언트 데이터를 관리하기 위한 상태 관리 라이브러리를 추가 사용 필요
  

💡 Redux

• 클라이언트 데이터 관리하기에 적합하다.
• 서버 상태를 관리하기 위해서는 비동기 처리를 위한 추가 라이브러리 필요
• 서버 데이터를 관리하기 위한 로직이 과도하게 커지고, 보일러 플레이트가 비대해진다.
  

서버 데이터 관리로 React Query를 사용하고 클라이언트 측에서 전역 데이터 관리 필요

💡 클라이언트 전역 데이터 관리 : Recoil vs 다른 상태관리 방법

• React useState

  • 상태를 공유해 주는 부모 컴포넌트에서 prop drilling을 하는 방법은 불편하다.
  • 하나의 공통 prop이 변경될 때마다 re-rendering 해야 하므로 많은 양의 데이터는 처리할 수 없다.

• React useContext

  • 각 상태는 Context Provider가 필요한데, 상태가 1000개라면 1000개의 Provider를 선언해야 한다. (Wrapper 지옥…) → Recoil 은 Atom을 동적으로 생성할 수 있다.
  • 상태가 변경될 때마다 캐싱 없이 매번 re-rendering 한다.

• Redux

  • 전역 상태를 수정하기 위해서는 반드시 액션을 선언해서 수행해야 하므로 데이터의 흐름을 좀 더 쉽게 예측 가능하다.
  • 좋은 개발자 도구가 있어서 문제가 생긴 경우 빠르게 어느 시점에 무슨 컴포넌트가 어떤 데이터를 변경하는지 확인할 수 있다.
  • RTK(Redux Tool Kit)를 사용하면 Reducer를 통한 데이터 업데이트시 RTK가 Immer를 사용하여 불변성을 지켜준다.
  • 초기 구축, 유지 보수 과정에서 boilerplate 코드를 많이 작성해야 한다.
  • React concurrent renderer를 지원하지 않는다.

• Recoil이 해결하는 문제: 손쉬운 전역 상태관리

  • Recoil의 상태를 구독, 업데이트하는 API는 간단하고 안정적이다.
  • Recoil에서 하나의 전역 상태는 Atom이라고 부른다.
  • Atom은 어느 하나의 컴포넌트에 묶여있지 않고, 모든 컴포넌트에서 접근 가능한 하나의 그래프라고 이해하면 쉽다.

• Recoil의 손쉬운 전역상태 사용 방법

  • 아래의 아주 간단한 코드만으로 Recoil을 React에 적용하고 상태를 구독, 변경하는 것이 가능하다.
  • 이 단순함과 안정성이 Recoil의 최대 장점

// app.js: Recoil Root Store 선언
function App() {
  return (
    <RecoilRoot>
      <Child />
    </RecoilRoot>
  );
}

// store.js: Recoil Atom 선언
const globalState = atom({
  key: 'globalState',
  default: 'blah',
});

// Child.jsx: 자식 컴포넌트에서 atom 구독, 변경.
function Child() {
  const [globalState, setGlobalState] = useRecoilState(globalState);
  const onChange = (event) => {
    setGlobalState(event.target.value);
  };
  return (
    <div>
      <input value={text} onChange={onChange} />
      Output: {text}
    </div>
  );
}

✅ 결론 : React Query + Recoil

// JS
let a = 1;
let b = 2;

let c = a + b;

// TS
let a: number = 1;
let b: number = 2;

let c: number;
c = a + b;

💡 TS 장점 - type이 있음으로써 좋아지는 점?

1. 런타임 에러 vs 컴파일 에러

// JS
const plus = (a, b) => {
    let c = a + b; // 1.runtime err 발생
    return c;
};

let a = 1;
let b = 'aa';

console.log('a + b = ' + plus(a, b));

// TS
const plus = (a: number, b: number): number => {
    let c: number = a + b;
    return c;
};

let a: number = 1;
let b: number = 'aa'; // 2. compile err 발생

console.log('a + b = ' + plus(a, b));

type을 명시함으로써 컴파일 단에서 미리 선언될 수 없는 변수를 차단

2. IDE와의 결합성

• TS는 JS보다 IDE와의 결합성이 훨씬 좋다.
• TS는 ctrl + click으로 웬만한 class와 fuction을 쉽게 역추적 할 수 있다.
• 물론 JS도 IDE에서 해당 기능을 제공하지만 쉽게 역추적 되지 않는 경우가 많다.
• 그럴땐 find를 통해서 찾아야만 한다. 클릭 한번, 타자 한번이 쌓여서 시간을 잡아먹는다.

3. 가독성

• TS는 자료형을 명시함으로써 어떤형의 데이터가 들어가고 어떤 형의 data가 return 되는지 쉽게 알 수 있다.
• JS의 경우에는 따로 설명이 되어 있지 않거나 네이밍이 이상할 경우, 직접 들어가서 코드를 읽는 수 밖에 없다.
• 또한 JS의 input이나 return 값이 object일 경우는 코드를 읽기가 더 힘들어진다.
• 하지만 TS는 interface로 type을 새로 선언함으로써 어떤 데이터가 들어가고 어떤 데이터가 return 되는지 좀더 쉽게 파악이 가능하다. 즉, 가독성이 좋아진다.

💡 JS 장점 - 하지만 JS가 좋을 수도 있잖아?

1. 유연성 & 생산성

// JS
let a = 'string';
let b = 2;
a = 1;

let c = a + b;
console.log('a + b = ', c);

// TS
let a: string = 'string';
let b: number = 2;
a = 1;

let c: number = a + b;
console.log('a + b = ', c);

• 위 코드를 보면 알 수 있듯이 JS는 a라는 변수를 자료형을 바꿔가면 사용하는게 가능하다. TS는 불가능하다.
• 또한 number나 string이 기본 자료형이 아닌 object같이 복합 자료형일 경우엔 TS는 선언해줘야 할 게 정말 많다.
• 그래서 코드 작성을 유연하게 하지 못할 때가 정말 많다.
• JS라면 3줄이면 될 것을 TS는 10줄 또는 그 이상을 작성해야 할 때도 있다.
  

✅ 결론 - TypeScript를 쓰자

• 컴파일로 많은 에러를 사전에 예방할 수 있고 가독성이 좋다.
• 협업 시에 서로 빠르게 코드를 이해할 수 있다.
• JS의 장점인 유연성과 생산성은 TS의 any 자료형을 사용함으로써 어느정도 해결이 가능하다.
• any는 어떤 자료형이든 허용하기 때문에 경우에 따라 유연하게 사용할 수도 있고 제약적으로 사용할 수도 있다.

1654번: 랜선 자르기

문제 접근 🤔

• 이 문제를 주어진 랜선들을 같은 길이로 잘라 n 개 이상으로 만들 수 있는 길이의 최댓값을 구하는 문제다.
• 이 길이를 구하기 위해 길이의 범위를 설정하자.
• 자르는 길이는 자연수이고 랜선들의 최댓값보다 커질 수 없으므로 범위는 (1, max(lanList)) 이다.
• 탐색 범위의 중간값인 mid 를 기준으로 하여 범위를 반씩 좁혀나가며 탐색을 진행한다.
• mid 로 랜선들을 자른 개수의 총합이 n 이상이면 low의 위치를 mid 의 오른쪽으로 보내주고, 자른 길이 중 최댓값을 저장한다.
• 자른 개수의 총합이 n 미만이면 high 의 위치를 mid 의 왼쪽으로 보내준다.
• 이 과정을 high가 low 보다 작아지기 전까지 반복해주면 구하는 길이의 최댓값을 구할 수 있다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(84 ms)

# 백준 입력 시간 줄이기
import sys
input = sys.stdin.readline

# 풀이 코드
k, n = map(int, input().split())
lanList = [int(input()) for _ in range(k)]
maxLen = -sys.maxsize - 1
low, high = 1, max(lanList)

while low <= high:
    mid = (low + high) // 2

    cutCnt = 0
    for lan in lanList:
        cutCnt += lan // mid

    if n <= cutCnt:
        maxLen = max(maxLen, mid)
        low = mid + 1
    else:
        high = mid - 1

print(maxLen)

자바스크립트 코드(184 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, ...datas] = fs.readFileSync(filePath).toString().trim().split('\n');

const solution = ([k, n], lanList) => {
  let [low, high] = [1, Math.max(...lanList)];
  let maxLen = Number.MIN_SAFE_INTEGER;

  while (low <= high) {
    let mid = ~~((low + high) / 2);
    let cutCnt = lanList.reduce((sum, lan) => sum + ~~(lan / mid), 0);

    if (n <= cutCnt) {
      maxLen = Math.max(maxLen, mid);
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  console.log(maxLen);
};

solution(L.split(' ').map(Number), datas.map(Number));

2805번: 나무 자르기

문제 접근 🤔

• 주어진 나무들을 자르고 남은 나무들의 길이 합이 최소한 m 이상이 되도록 하는 자르는 길이의 최댓값을 찾는 문제다.
• 이분 탐색을 이용하면 길이를 찾는 시간 복잡도를 줄일 수 있다.
• 구하는 것은 나무를 자를 길이이므로 탐색을 진행할 범위는 (0, max(trees)) 이다.
• 범위의 중간값을 mid 라 하고 mid 보다 큰 나무가 존재하면 자르고 남은 길이를 합해준다.
• 이 길이의 합이 m 과 같다면 구하는 최댓값이 현재의 mid 값이므로 저장해주고 반복문을 종료한다.
• 크다면 나무를 자를 수는 있지만 최댓값인지 모르므로 현재까지 저장된 값과 현재의 mid 중 더 큰 값을 저장하고 범위의 시작 위치를 mid 의 오른쪽으로 옮겨준다.
• 작다면 범위의 끝을 mid 의 왼쪽으로 옮겨준다.
• 이 과정이 완료되면 문제의 조건을 만족하는 최댓값을 구할 수 있다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(480 ms)

n, m = map(int, input().split())
trees = list(map(int, input().split()))
low, high = 0, max(trees)
maxLen = 0

while low <= high:
    mid = (low + high) // 2

    cutLen = 0
    for tLen in trees:
        if mid < tLen:
            cutLen += tLen - mid

    if m == cutLen:
        maxLen = mid
        break
    elif m < cutLen:
        maxLen = max(mid, maxLen)
        low = mid + 1
    else:
        high = mid - 1

print(maxLen)

자바스크립트 코드(1028 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, datas] = fs.readFileSync(filePath).toString().trim().split('\n');

const solution = ([n, m], trees) => {
  let [low, high] = [0, Math.max(...trees)];
  let maxLen = Number.MIN_SAFE_INTEGER;

  while (low <= high) {
    let mid = ~~((low + high) / 2);
    let cutLen = trees.reduce((sum, tLen) => (mid < tLen ? sum + tLen - mid : sum), 0);

    if (m === cutLen) {
      maxLen = mid;
      break;
    } else if (m < cutLen) {
      maxLen = Math.max(mid, maxLen);
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  console.log(maxLen);
};

solution(L.split(' ').map(Number), datas.split(' ').map(Number));

2512번: 예산

문제 접근 🤔

• 전체 국가 예산의 한도 내에서 줄 수 있는 예산의 상한액을 구하는 문제.
• 이분 탐색을 하기 전에 예외의 경우를 살펴보자.
• 총 예산의 한도 값보다 예산 요청 리스트의 최솟값에 n을 곱한 값이 크거나 같을 때는, 이분 탐색을 진행할 필요 없이 상한액은 한도를 n으로 나눈 몫이다. ex) 예산 요청: 2, 2, 3 and 한도: 5 → 상한액: 1
• 이러한 경우를 제외하고서는 상한액은 예산 요청 리스트의 최솟값과 최댓값 사이에 있을 것이다.
• 효율적으로 찾기 위해 이분 탐색을 진행하며 상한액의 최댓값을 찾아보자.
• 범위의 중간값을 상한액으로 지정했을 때 요청 예산이 더 크다면 예산을 상한액만큼 지급하고, 같거나 작다면 요청 예산만큼 지급한다.
• 이 값들을 더한 예산의 총합과 예산의 한도를 비교하여 이분 탐색을 진행하면 된다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(64 ms)

n, budgets, limit = int(input()), list(map(int, input().split())), int(input())
low, high = min(budgets), max(budgets)
maxBudget = 0

if limit <= low * n:
    maxBudget = limit // n
else:
    while low <= high:
        mid = (low + high) // 2

        budSum = 0
        for bud in budgets:
            budSum += mid if mid < bud else bud

        if budSum <= limit:
            maxBudget = max(maxBudget, mid)
            low = mid + 1
        else:
            high = mid - 1

print(maxBudget)

자바스크립트 코드(176 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [N, datas, M] = fs.readFileSync(filePath).toString().trim().split('\n');

const solution = (n, budgets, limit) => {
  let [low, high] = [Math.min(...budgets), Math.max(...budgets)];
  let maxBudget = Number.MIN_SAFE_INTEGER;

  if (limit <= low * n) {
    maxBudget = Math.floor(limit / n);
  } else {
    while (low <= high) {
      let mid = Math.floor((low + high) / 2);
      let budSum = budgets.reduce((sum, bud) => (mid < bud ? sum + mid : sum + bud), 0);

      if (budSum <= limit) {
        maxBudget = Math.max(maxBudget, mid);
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  console.log(maxBudget);
};

solution(Number(N), datas.split(' ').map(Number), Number(M));

Search a 2D Matrix II - LeetCode

문제 접근 🤔

• 이진 탐색(이분 탐색)을 통해 매 행마다 target과 같은 값이 있는지 확인하고 존재한다면 True, 존재하지 않으면 False를 반환하면 되는 문제.
• 브루트포스를 이용해서 해결할 수도 있지만 오름차순으로 정렬되어 있는 행렬이기 때문에 빠른 처리를 위해서는 이분 탐색을 고려해보아야 한다.

• 주어진 행렬은 행, 열 모두 오름차순으로 정렬되어 있으므로 0번째 행부터 순서대로 target의 존재를 확인하면 된다.
• 현재 행의 범위 안에 타겟이 속한다면 타겟이 존재할 수도 있으므로 이분 탐색을 진행하면 된다.
• low, high 의 초기값을 각각 0(첫번째 인덱스), 열의 길이로 선언해준다.
• low가 high보다 커지지 않을 때까지 반복문을 돌며, low와 high의 중앙값인 mid를 통해 타겟의 존재 여부를 확인한다.
• matrix[i][mid]이 타겟과 같다면 True를 반환해준다.
• 타겟보다 작다면 탐색 범위를 (mid + 1, high)로, 크다면 탐색 범위를 (low, mid)로 좁혀준다.
• 이 과정을 통해 모든 행을 확인해보았을 때도 같은 값을 찾지 못했다면 False를 반환한다.
• 행의 개수를 M 열의 개수를 N 이라고 했을 때, 이분 탐색을 이용한 이 문제의 총 시간 복잡도는 O(M log N) 을 갖는다.
  
  

  놓쳤던 부분 😅

• 이진 탐색에서는 없음.
• 이진 탐색 전에 먼저 떠오른 풀이가 있어 제출 해보았는데, 파이썬에선 통과가 되었고 JS에서는 시간초과가 났다 🤯
• 혹시 JS에서 배열에 같은 원소가 있는지 확인하는 includes 함수에서 오래 걸리나? 해서
• 시간 복잡도가 O(N)인 includes 함수에서 O(1)의 시간 복잡도를 갖는 Set의 has 함수로 변경하여 확인해보았을 때도 여전히 시간 초과가 났다.
• 파이썬의 in 연산자도 list에서 O(N)의 시간복잡도를 갖는데, 왜 파이썬은 되고 JS는 안 되는거죠? (JS 이지매 당함)
• 심지어 시간 복잡도가 O(logN)인 이진 탐색 풀이보다도 조금 빠른 결과물이 나왔다?!
• 왜 이런 차이가 나는 것인지는 조금 더 찾아봐야 될 듯.
  
  

  코드 😁

파이썬 코드(142 ms)

# 이진 탐색 풀이 (시간: 142 ms)
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        row, col = len(matrix), len(matrix[0])

        for i in range(row):
            if matrix[i][0] <= target and matrix[i][-1] >= target:
                low, high = 0, col

                while (low < high):
                    mid = (low + high) // 2

                    if matrix[i][mid] == target:
                        return True
                    elif matrix[i][mid] < target:
                        low = mid + 1
                    else:
                        high = mid

        return False

# 행렬의 매 행마다 원하는 값이 있는지 확인하는 풀이 (시간: 137 ms)
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        for row in matrix:
            if target in row:
                return True
        return False

자바스크립트 코드(862 ms)

const searchMatrix = (matrix, target) => {
    let [row, col] = [matrix.length, matrix[0].length];

    for (let i = 0; i < row; i++) {
        let [low, high] = [0, col];

        while (low < high) {
            let mid = ~~((low + high) / 2);

            if (matrix[i][mid] === target) {
                return true;
            } else if (matrix[i][mid] < target) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
    }
    return false;
};

Two Sum II - Input Array Is Sorted - LeetCode

문제 접근 🤔

• 투포인터를 이용하여 탐색을 해보았다.

• 없음
  
  

  코드 😁

파이썬 코드(96 ms)

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        start, end = 0, len(numbers) - 1
        while numbers[start] + numbers[end] != target:
            if numbers[start] + numbers[end] > target:
                end -= 1
            else:
                start += 1
        return [start + 1, end + 1]

자바스크립트 코드(63 ms)

const twoSum = (numbers, target) => {
    let [start, end] = [0, numbers.length - 1];

    while (numbers[start] + numbers[end] !== target) {
        if (numbers[start] + numbers[end] > target) {
            end--;
        } else {
            start++;
        }
    }
    return [start + 1, end + 1];  
};

5939번: Race Results

문제 접근 🤔

• heapq 모듈을 이용하여 힙을 만들되, 원소로 (시간, 분, 초) 를 튜플 형태로 저장한다.
• 힙에서 저장된 값을 뽑아내면 원하는 조건에 맞는 순서대로 값을 출력할 수 있다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(56 ms)

import sys
import heapq
input = sys.stdin.readline
N = int(input())
heap = []

for _ in range(N):
    hours, minutes, seconds = map(int, input().split())
    heapq.heappush(heap, (hours, minutes, seconds))

for _ in range(N):
    print(' '.join(map(str, heapq.heappop(heap))))

14534번: String Permutation

문제 접근 🤔

• itertools.permutations 모듈을 이용하여 입력 받은 문자열로 만들 수 있는 순열을 생성한다.
• 순열로 만들어진 모든 값들을 조인하여 문자열로 변환해주고 출력한다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(40 ms)

from itertools import permutations

for i in range(1, int(input()) + 1):
    pList = list(permutations(list(input())))
    print(f'Case # {i}:')
    for val in pList:
        print(''.join(val))

Largest Number - LeetCode

문제 접근 🤔

• 전형적인 정렬 문제이나 하나의 키 값으로 정렬하는 문제가 아니었다. 어떤 키 값으로 정렬을 할지가 중요한 문제.
• 여기서 키 값은 비교할 두 원소를 문자열로 변환하여 더한 값이었다.
• 따라서 nums의 원소인 숫자들을 문자열로 변환하고 sorted 함수를 통해 이 리스트를 정렬하자.
• key 를 functools.cmp_to_key(compare) 로 설정하고 정렬의 기준을 정해줄 compare 함수를 선언한다.
• compare 함수는 a + b > b + a  가 True 라면 -1, False라면 1을 반환하는 함수이다.
• 1이 반환되면 두 원소의 위치가 서로 바뀌기 때문에 주어진 조건에 맞게 정렬이 된다.
• 리턴 값을 str(int())로 감싸주는 이유는 입력값이 [0, 0] 일 때 00 이 아닌 0을 반환하기 위한 처리이다.
  
  

  놓쳤던 부분 😅

• 효율적으로 작성하는 코드를 찾아보다가 functools 모듈의 cmp_to_key 함수를 알게 되었다.
• cmp_to_key 를 활용하면 자신만의 조건에 따라 sorting 가능하게 할 수 있다.

functools.cmp_to_key(func) 는 sorted()와 같은 정렬 함수의 key 매개변수에 함수(func)를 전달할 때 사용하는 함수이다. 단, func() 함수는 두 개의 인수를 입력하여 그 둘을 비교하고 기준에 따라 음수, 0, 양수를 반환하는 비교 함수이어야 한다.

• 양수를 반환하면 두 입력의 자리를 바꾼다는 의미이고, 음수를 반환하면 위치를 바꾸지 않는다는 의미이다.
• 속도도 빠른 편인 것 같아서 정렬 문제를 풀 때 알아두면 유용하게 활용할 수 있을 듯.
  
  

  코드 😁

파이썬 코드(37 ms)

from functools import cmp_to_key

class Solution:

    def compare(self, a, b):
        return -1 if a + b > b + a else 1

    def largestNumber(self, nums: List[int]) -> str:
        nums = sorted(list(map(str, nums)), key = cmp_to_key(self.compare))
        return str(int("".join(nums)))

Insertion Sort List - LeetCode

문제 접근 🤔

💡 삽입 정렬 (insertion sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

• 입력으로 주어진 연결 리스트를 오름차순으로 정렬하는 문제
• 정렬된 연결 리스트를 저장할 빈 연결 리스트를 선언한다. 이를 dummy 라 하자.
• 입력으로 주어진 연결 리스트를 순회하면서, 각 노드마다 dummy에 삽입할 위치를 찾는다.
• 순회가 끝나면, dummy 는 정렬된 연결 리스트가 된다.
  
  

  놓쳤던 부분 😅

• 처음에 반쪽짜리 정렬을 하게 되어서 찾아보니 빈 연결 리스트를 선언하여 추가해줘야 하는 문제였다. 🥹
  
  

  코드 😁

파이썬 코드(64 ms)

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        dummy = curr = ListNode()
        while head:
            while curr.next and curr.next.val < head.val:
                curr = curr.next
            curr.next, head.next, head = head, curr.next, head.next
            if head and curr.val > head.val:
                curr = dummy
        return dummy.next

11279번: 최대 힙

문제 접근 🤔

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.

힙에 원소를 추가할 때 (-num, num) 의 튜플 형대로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다.

이때 원소 값의 부호를 바꿨기 때문에, 최소 힙으로 구현되었던 heapq 모듈을 최대 힙 구현에 활용할 수 있다.

• 입력 값으로 자연수가 들어왔을 때마다 이 방식으로 heapq 를 최대 힙으로 구현한다.
• 0이 입력되었을 때, 현재 힙이 빈 상태라면 0, 아니라면 힙에 존재하는 최댓값을 출력해준다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(152 ms)

import sys
import heapq
input = sys.stdin.readline
heap = []

for _ in range(int(input())):
    num = int(input())
    if not num:
        print(heapq.heappop(heap)[1] if len(heap) else 0)
    else:
        heapq.heappush(heap, (-num, num))

1927번: 최소 힙

문제 접근 🤔

• 힙을 사용해서 리스트에 입력으로 들어오는 자연수를 저장하고 0이 들어왔을 때 힙의 최솟값을 출력하면 된다.
• 리스트가 빈 상태라면 0을 출력한다.
  
  

  놓쳤던 부분 😅

• 없음
• 맞는데 자꾸 시간초과래서 찾아보니까 백준 시간 초과 방지로 인해 input = sys.stdin.readline 이 부분을 추가해줘야 했음 ㅋㅋ 🤬
  
  

  코드 😁

파이썬 코드(128 ms)

import heapq
import sys

input = sys.stdin.readline
heap = []

for _ in range(int(input())):
    num = int(input())
    if not num:
        print(heapq.heappop(heap) if len(heap) else 0)
    else:
        heapq.heappush(heap, num)

Kth Largest Element in an Array - LeetCode

문제 접근 🤔

• 힙에서 최댓값부터 뽑아내기 위해 nums 의 인자들을 음수로 변환한 값을 가진 리스트를 선언한다.
• heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환한다.
• k번째로 큰 값을 출력해주면 된다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(485 ms)

import heapq

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        heap = [-n for n in nums]
        heapq.heapify(heap)

        for _ in range(k):
            findKth = -1 * heapq.heappop(heap)

        return findKth

The K Weakest Rows in a Matrix - LeetCode

문제 접근 🤔

• 이 문제는 각 행의 전사 수를 기준으로 가장 약한 행부터 강한 행까지 k 개를 찾아 반환하는 문제이다.
• heapq 에 값을 튜플 형태로 저장하면 정렬의 우선순위를 정할 수 있다.
  • 전사의 수가 더 적은 행이 약하다.
  • 전사의 수가 같다면 행렬에서 인덱스 값이 더 낮은 행이 약하다.
• 즉 값으로 (전사의 수, 인덱스) 를 저장해준다면 힙에는 전사의 수가 더 낮은 순으로 저장되고, 전사의 수가 같다면 인덱스가 낮은 순으로 저장된다.
• 전사는 1로 나타내므로 각 행마다 collections.Counter 함수를 사용하여 1의 개수를 추출하고, 힙에 이 값과 행의 인덱스 값을 저장한다.
• heapq.heappop(힙) 을 이용하여 약한 행의 정보를 k 번 꺼내어 행의 인덱스 값을 리스트에 담아주고 이 리스트를 최종 출력하면 된다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(97 ms)

from collections import Counter
import heapq

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        heap, answer = [], []
        for idx, row in enumerate(mat):
            heapq.heappush(heap, (Counter(row)[1], idx))

        while k:
            answer.append(heapq.heappop(heap)[1])
            k -= 1
        return answer

Maximum Product of Two Elements in an Array - LeetCode

문제 접근 🤔

• 리스트 nums 를 최대 힙으로 구현하고 최댓값을 차례로 두개를 꺼낸다.
• 이 두 값을 각각 1씩 빼서 곱한 값을 반환해주면 된다.
  
  

  놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(50 ms)

import heapq

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        maxHeap = []
        for n in nums:
            heapq.heappush(maxHeap, (-n, n))
        i = heapq.heappop(maxHeap)[1]
        j = heapq.heappop(maxHeap)[1]
        return (i - 1) * (j - 1)

1068번: 트리

문제 접근 🤔

• 삭제해야 하는 부모 트리의 인덱스와 입력된 트리 리스트를 입력 값으로 받는 DFS 함수를 선언한다.
• 전달 받은 인덱스의 리스트 값을 삭제한다는 의미로 해당 값을 None 으로 바꾼다.
• 리스트 전체를 탐색하며, 방금 삭제한 인덱스를 부모 노드로 가지는 노드를 찾아 dfs 함수를 재귀 호출한다.
• 재귀가 끝나면 삭제된 노드들은 전부 None 으로 갱신되어 있으므로, 값이 None 이 아니면서, 다른 노드의 부모 노드도 아닌 원소를 찾을 때마다 cnt를 1씩 늘린다.
  
  

  놓쳤던 부분 😅

• DFS / BFS 를 사용할 때에 가장 중요한 것은 탐색의 기준을 잡는 것이라고 생각한다.
• 이번에는 바로 떠오르지 않아서 다른 분의 답안을 참고 했는데, 삭제해야 하는 인덱스를 기준으로 하고 탐색을 돌리면 생각보다 단순한 문제였다.
• 다양한 문제들을 접하며 문제를 해결할 아이디어를 떠올리는 능력을 더 길러야겠다.
  
  

  코드 😁

파이썬 코드(40 ms)

n, parentList, k = int(input()), list(map(int, input().split())), int(input())
cnt = 0

def dfs(num, list):
    list[num] = None
    for i in range(len(list)):
        if num == list[i]:
            dfs(i, list)

dfs(k, parentList)

for i in range(len(parentList)):
    if parentList[i] != None and i not in parentList:
        cnt += 1
print(cnt)

자바스크립트 코드(132 ms)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input.txt';
const [L, data, K] = fs.readFileSync(filePath).toString().trim().split('\n');

const dfs = (cutNum, list) => {
  list[cutNum] = null;

  for (let i = 0; i < list.length; i++) {
    if (cutNum === list[i]) {
      dfs(i, list);
    }
  }
};

const solution = (parentList, k) => {
  let cnt = 0;
  dfs(k, parentList);

  for (let i = 0; i < parentList.length; i++) {
    if (parentList[i] != null && !parentList.includes(i)) {
      cnt++;
    }
  }
  console.log(cnt);
};

solution(data.split(' ').map(Number), Number(K));

Balanced Binary Tree - LeetCode

문제 접근 🤔

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

이진 트리에서 높이 균형이란, 각 서브 트리의 높이 차이가 1 이하인 상태를 말한다. 즉, 트리의 각 서브 트리에 대해 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이가 1 이하여야 한다.

• 주어진 이진 트리가 높이 균형이 맞는지 확인하는 문제
• DFS를 통해 트리의 가장 하단부터 트리를 타고 올라가면서 각 노드의 높이를 반환하자.
• 노드의 왼쪽 노드와 오른쪽 노드의 높이 차이가 1보다 크다면 높이 균형이 맞지 않는 이진 트리이므로 False를 저장하고 모든 노드의 높이 차이가 1 이하라면 True를 저장하여 이를 최종 반환해주면 된다.

놓쳤던 부분 😅

• 없음
  
  

  코드 😁

파이썬 코드(56 ms)

class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        self.isHeightBalanced = True

        def dfs(node, height = 0):
            if not node:
                return height
            height += 1
            left, right = dfs(node.left, height), dfs(node.right, height)
            if abs(left - right) > 1:
                self.isHeightBalanced = False
            return max(left, right)

        dfs(root)
        return self.isHeightBalanced

자바스크립트 코드(76 ms)

const isBalanced = (root) => {
  let isHeightBalanced = true;

  const dfs = (node, height = 0) => {
    if (!node) {
      return height;
    }
    height++;
    let [left, right] = [dfs(node.left, height), dfs(node.right, height)];
    if (Math.abs(left - right) > 1) {
      isHeightBalanced = false;
    }
    return Math.max(left, right);
  };
  dfs(root);
  return isHeightBalanced;
};