🙋‍♀️2024.11.20 ~ 2024.11.21

드디어 해커톤 날이 밝았다.

시간이 워낙 워낙 워낙 촉박한데, 기능이 많다 보니까 당일 새벽까지 개발을 하다가 잠이 들었다. 집에서 해커톤 장소인 📍송파 파크하비오 호텔 까지 거리가 있다보니 일찍 출발해서 매우매우 피곤한 상태였다.

그럼에도 기쁜 마음으로 도착했더니 호텔 웨딩홀? 같은 곳 한 층을 통으로 사용해서 진행되었다. 그동안은 실감이 안났는데 해커톤 장소에 가보니 생각보다 큰 대회구나..! 하는 생각이 들었다.

대회장 복도 홀에 이렇게 포토존이랑 본선 진출 팀의 기획안 설명들이 있었다.

포토존 앞에 네컷 사진기도 있었다....!!!😲

대회장 안에 들어가니 모든 팀 당 결혼식 테이블 하나에 앉아서 해커톤에 참가했었다. 대회 주최측에서 식사, 간식, 간단한 생필품을 제공하고 모두가 후드집업을 유니폼으로 제공받아서 입었다.

• 대회장이 더운데 후드집업이 기모라 안에 반팔 같은거 입고 가시는거 추천할게요.^^*

대회 개최식이 끝나고 오후부터 바로 각 팀당 2회의 멘토링이 진행되는데 여기서 그동안 맡아주신 멘토님을 다시 뵙게 되었다! 이제는 다음날 있을 발표를 위한 멘토링이 진행되었고, 어떻게 수정해야 더 좋을지 발표자료를 보면서 멘토링을 진행해주셨다.

멘토링에 오기 전까지 기획은 90% , 개발은 80% 정도 개발이 완료된 상태였는데 개발팀은 해커톤 시간동안 발표자료에 넣을 시연 영상 촬영을 위해 에러 리팩토링과 디자이너님이 요청하신 디자인 리팩토링을 진행했다.

발표를 빼면 금방 끝나고 여유롭게 해커톤 시간을 보낼 줄 알았는데 생각보다 수정 사항이 많아서 발표자님과 백엔드 개발자를 제외하고는 결국 잠은 못잤다ㅠㅠ 정말로 무박... 😫

그래도 중간에 사우나에서 따뜻하게 씻고 오고, 중간 중간 다과에 간식에 식사까지 꼼꼼히 챙겨주셔서 그나마 다행이었다.

해커톤 발표

광란의 밤을 보내고 다음날 오전 드디어 해커톤 발표가 시작되었다.

우리 팀은 지정과제 세번째로 발표하게 되었다. 기획 겸 우리팀 팀장을 맡아주신 기획분께서 발표를 맡아주셨는데 정말 콩깍지 다 빼도 너무 너무 너무 잘해주셔서 상을 탈 것만 같았다.

일찌감치 우리팀 발표가 끝나고 편안한 마음으로 다른 팀 발표를 듣고 있는데 발표 시간 제한 10분을 못 맞추신 팀도 있고 개발을 진행 안하고 구상만 한 것 같은 팀도 있었다.

다시 한 번 공모전은 기획이 중요하구나 생각이 들었다. 기능 구현을 위해서 노력을 많이 했는데 막상 발표로 보니까 정말 구현을 한 것인지 구분조차 어려워서 좀 아쉬웠다 ...

오랜 기다림 끝에 모든 팀의 발표가 끝나고 점심시간을 가지고 심사 결과 발표가 시작되었다. 우리팀 말고도 다른 팀들도 다들 잠을 못자고 밤을 샌 팀이 많다 보니까 다들 되게 피곤한 상태로 발표만 기다리고 있었다. 자유 과제 팀 발표가 끝나고 대망의 지정과제 차례....

심평원장상 , 장려상, 우수상까지 우리팀 이름이 불리지 않다가 드디어 TOP 3 팀 호명과 함께 모두 단상위로 올라갔다.

결과는...!

최우수상 !!!!🥹

사실 대상과 최우수상까지 호명이 되지 않아서 정말 우리팀이 대상을 받게 되는 것인가 팀원들 모두 두근두근하고 있었어서.. 살짝 아쉬웠지만

그래도 첫 해커톤에 최우수상이라니!!!! 장관상이라니~!!! 500만원이라니 ~ !!!!

너무 뿌듯했다. 🥹🥹🥹🥹 좋은 기획안 만들어주신 우리 팀원들, 함께 한 달간 새벽까지 함께 열심히 개발한 우리 개발 팀원들 너무너무 감사합니다!!

더해서 개발자로서 한 발을 내딛도록 도와준 구름톤 트레이닝의 구름에게도 감사하다. 구름톤에 참여한게 올해 초인데 고작 일 년만에 이만큼 성장한 것은 구름톤에서 진행한 커리큘럼을 잘 따라갔기 때문이 아닐까 싶다. 구름에서의 시간이 아니었으면 해커톤에 참여할 일 조차 없지 않았을까?ㅜㅠ

+++ ☁️구름톤 메이트 토니야 수고했어!!!!

🙋‍♀️2023.12.29 ~ 2024.07.11

[구름 x 인프런] 자바 스프링 & 리액트 풀스택 개발자 성장 과정 6회차를 수료하고 어영부영 시간만 보내던 어느날 구름톤 디스코드 알람을 받게 되었다.

☁️구름에서 만난 팀끼리 고용노동부에서 주최한 k-digital trainging 해커톤에 참여해서 수상하면 성장 격려금을 지급한다는 소식을 보게 되었다.

그 글을 보자마자 바아로 구름톤 백엔드 친구 토니에게 연락해서 참가를 접수하게 되었다. KDT 해커톤 페이지 에 접속해서 공모 요강을 살펴보니 무려 국무총리상, 장관상에 상금이 최하 100만원?? 스펙도 쌓고 상금도 받고 이건 놓칠 수 없는 기회다!! 라는 생각에 KDT 해커톤 페이지에서 팀원을 구했다.

KDT 페이지의 팀원 모집글을 통해 우리는 기획 2명, 디자이너 1명, 프론트엔드 개발자 1명의 팀에 합류해서 기획 2명, 기획 겸 디자이너 1명, 프론트 개발자 2명, 백엔드 개발자 1명의 황금 밸런스의 총 6명 팀을 구성하게 되었다. 다들 경력도 있으시고 이미 직장생활을 하다 오신 분들이어서 그런지 기획도 착착 디자인도 착착 개발도 착착 진행되었다.

🔥예선 진출

KDT 해커톤 수상을 위해서는 3번의 관문이 있었다. 먼저 1차 예선 통과, 2차 본선 통과, 마지막 무박 2일 해커톤!

예선과 본선까지는 개발 결과물이 아닌 우리 팀의 아이디어에 대한 기획안과 사업계획서, 관련 기술에 대한 설명을 적은 서류를 통해 평가가 이뤄졌다. 서면 평가이다 보니까 기획의 힘이 굉장히 중요했는데 정말 운이 좋게도 좋은 팀원분들을 만나서 체계적이고 구체적인 기획안으로 예선을 통과했다!!

총 50팀이 예선을 통과했고 우리팀이 그 중 하나에 속했다!

참가 부문은 두 가지로 나뉘었는데 주제가 정해진 지정 과제와, 기술성을 메인으로 원하는 서비스를 개발하는 자유 과제로 나눠었다.

우리 팀은 저출산. 고령 사회에 필요한 첨단. 디지털 개발이라는 지정 과제 부문에 참여해 저출산 사회에 대한 대책으로 난임 부부를 위한 플랫폼을 개발했다.

예선 통과 후, 약 한 달 반의 시간동안 대회에서 제공하는 멘토링과 함께 서비스를 구현할 시간이 주어졌다. 📅10/2 ~ 11/21 멘토링을 통해 기획안이 완성되고 디자인이 확정되는 시간까지 더하면 개발자가 서비스를 구현할 시간은 정말 딱 한 달 정도 밖에 없었다 ㅠ🥹ㅠ 시간이 촉박하다 보니 본선 진출 결과가 나오기 전부터 개발을 계속 진행했었다.

🔥본선 진출

우와아아앙!! 급하게 또 빠르게 개발을 진행하던 중 해커톤 본선 진출 연락이 왔다. 워낙 기획분들이 준비해주신 기획안이 탄탄해서 본선에 진출할 거 같은 예감이 오긴 했었지만 막상 문자를 받고 나니 더 의지가 불탔다.🔥🔥 좋은 기획안을 제대로 개발만 하면 정말로 수상할 것 같은 느낌?을 받고 더 열심히 해야겠다고 생각이 들었다.

사실 본선까지 오면서는 정말 기획이 중요한 해커톤이다. 라는 느낌을 강하게 받았어서 앞으로 이 해커톤에 참여할 생각이 있으시다면 KDT 기획자 과정을 수료한 분과 함께하거나, 참여 전에 기획을 정말 탄탄히 준비해야 할 것 같아요.....!

인공지능 개발자가 없었다보니 개발 기술적인 부분에서 요즘 트렌드인 인공지능이나 딥러닝을 사용하지 못해서 기술적인 경쟁력이 떨어진다는 멘토링 코치님의 조언이 계속 있었다. 최대한 부하테스트나 렌더링 최적화 등 여러 부분의 기술적인 강조를 하려 노력했지만 서면으로만 보이기에는 부족하다는 생각이 들어서 걱정을 했었는데, 기획이 탄탄해서 통과했던 것 같다.

이어서 2탄에서 무박 해커톤/ 본선 진출 후기를..

자바스크립트에서 코드를 작성할 때 코드 품질을 높이고 일관된 스타일을 유지하기 위해 사용되는 도구

• 둘을 함께 사용하면 코드 품질과 일관성을 높일 수 있으며,
• 프로젝트의 협업 과정에서 코드 리뷰를 보다 효율적으로 진행할 수 있다.

ESLint는 코드 품질 및 버그 검사에 중점을 두고, Prettier는 코드 스타일을 관리하는 데 중점을 둔다.

ESLint

ESLint는 보통 프로젝트의 초기 빌드 과정에서 사용되어, 개발자가 코드를 작성하는 동안 실시간으로 코드를 검사하여 오류를 찾아낸다. 또한, IDE나 코드 에디터에서 플러그인으로 사용되어 개발자에게 편의성을 제공한다.

• 자바스크립트 코드의 스타일을 일관된 형식으로 유지하도록 돕고,

  • 들여쓰기, 줄 바꿈, 세미콜론 사용 등 코드 스타일을 체크해 일관성 유지

• 코드를 분석해 잠재적인 오류나 버그를 찾아내는 정적 분석 도구

  • 잘못된 변수 사용, 사용되지 않는 변수, 잘못된 조건문등을 검출

• 프로젝트에 맞게 ESLint 규칙을 추가하거나 수정해 사용 가능

  • 개발 프로젝트 팀원끼리 자체적으로 정한 스타일을 강제할 수 있다.

    ESLint 세팅

1. 패키지 설치

• 프로젝트 상위 폴더에서 터미널을 열어서

  $ npm install eslint --save-dev
  // or
  $ yarn add -D eslint

• 타입스크립트를 사용하는 경우

  $ npm install --save-dev eslint typescript @typescript-eslint/parser @typescript-eslint/eslint-plugin

2. VS Code 확장 프로그램 설치

• 확장 프로그램에서 eslint 검색후 설치

3. .eslintrc.js 파일 설정

• 프로젝트 루트 경로의 .eslintrc.js 파일 설정

• .eslintrc.js, .eslintrc.json, .eslintrc 3가지 파일의 형태 모두 가능하다.

  • .eslintrc.js

    module.exports = {
    env: {
    browser: true,
    es2021: true,
    },
    extends: [
    'eslint:recommended',
    'plugin:@typescript-eslint/recommended',
    'plugin:react/recommended',
    'plugin:prettier/recommended',
    ],
    overrides: [
    {
      env: {
        node: true,
      },
      files: ['.eslintrc.{js,cjs}'],
      parserOptions: {
        sourceType: 'script',
      },
    },
    ],
    parser: '@typescript-eslint/parser',
    parserOptions: {
    ecmaVersion: 'latest',
    sourceType: 'module',
    },
    plugins: ['@typescript-eslint', 'react', 'prettier'],
    rules: {
    'react/react-in-jsx-scope': 'off',
    },
    };

    Prettier

    코드의 스타일을 일관되게 유지하고 관리하기 위해 사용

• 보통 Prettier는 코드 저장 시 자동으로 동작하여 코드 서식을 일관되게 유지한다.

• 빌드 프로세스에서도 Prettier를 실행하여 코드의 일관성을 유지하고, 코드 리뷰에서도 팀원들 간의 서식을 통일시키는 데 사용된다.

Prettier 세팅

1. 패키지 설치

   $ npm install -D prettier
   // or
   $ yarn add -D prettier

2. 확장 프로그램 설치
3. VS Code 설정 바꿔주기

• 저장할 때마다 prettier가 적용되게 하기
• VS Code 에서 cmd+shift+p 로 열고 settings 검색

settings.json 파일에 추가

  "editor.defaultFormatter": "esbenp.prettier-vscode",
  "editor.formatOnSave": true

• ctrl + , 으로 설정 창 열어서 Editor: Default Formatter 검색 맥은 cmd + ,
• prettier-code formatter 선택
  4. 프로젝트 루트 경로에.prettierrc 파일 생성해서 원하는 프리티어 설정

• .prettierrc

  {
  // 한 줄에 표시될 최대 문자 수
  "printWidth": 120,
  // 탭의 너비
  "tabWidth": 2,
  // 탭 대신 공백 문자를 사용할 것인지 여부
  "useTabs": false,
  // 세미콜론 사용 여부
  "semi": true,
  // 작은 따옴표 사용 여부
  "singleQuote": true,
  // 여러 줄의 배열 또는 객체 리터럴 마지막 요소 뒤에 쉼표 추가 여부
  "trailingComma": "all",
  // 객체 리터럴의 중괄호 사이에 공백 추가 여부
  "bracketSpacing": true,
  // 화살표 함수의 매개변수가 단일 매개변수인 경우 괄호 사용 여부
  "arrowParens": "avoid",
  // proseWrap 옵션은 Markdown과 같은 텍스트에서 줄 바꿈을 적용하는 방식을 설정
  "proseWrap": "never",
  // 파일의 끝에 있는 줄 종료 문자 설정
  "endOfLine": "lf"
  }
  
  

### ESLint와 Prettier 동시 세팅
> 주로 ESLint와 Prettier은 개발 과정에서 함께 사용된다. 하지만 Prettier와 ESLint를 같이 사용하게 되면 두 설정이 다 적용되어 충돌이 발생한다.

이러한 문제를 해결하기 위해서 ESLint 내부에서 Prettier를 이용할 수 있도록 설정을 변경해야 한다.

#### 세팅

추가 플러그인이 필요하다.

- eslint-config-prettier :
ESLint의 규칙 중 Prettier에서 이미 다루는 것과 중복되는 부분을 비활성화하여 충돌을 방지한다. 이를 설치하면 ESLint가 Prettier의 규칙을 무시하고 서로 충돌하지 않는다.
- eslint-plugin-prettier :
Prettier가 적용되는 부분을 ESLint 에러로 표시하여 개발자가 Prettier의 서식을 준수하도록 유도한다.

1. 패키지 설치

npm i -D prettier eslint-plugin-prettier eslint-config-prettier

2. `.eslintrc` 파일에 다음과 같이 추가
```json
{
  "extends": ["eslint:recommended", "plugin:prettier/recommended"]
}

{
  "plugins": ["prettier"],
  "rules": {
    "prettier/prettier": "error"
  }
}

• 타입스크립트 사용 시

패키지 설치

npm install eslint @typescript-eslint/parser @typescript-eslint/eslint-plugin eslint-plugin-react --D

• 프리티어 설치

  prettier eslint-config-prettier eslint-plugin-prettier -D

  .eslintrc 파일에 다음과 같이 추가

  {
  "parser": "@typescript-eslint/parser",
  "extends": [
    "plugin:@typescript-eslint/recommended",
    "plugin:prettier/recommended",
    "prettier/@typescript-eslint"
  ],
  "plugins": ["@typescript-eslint"],
  "rules": {
    "@typescript-eslint/explicit-module-boundary-types": "off",
    "prettier/prettier": "error"
  }
  }
  

- `.eslintrc.js`
```jsx
module.exports = {
  env: {
    browser: true, // 브라우저 환경에서 실행되는 코드에 대한 설정
    es2021: true, // ECMAScript 2021 기능을 사용할 수 있도록 설정
  },
  extends: [
    'eslint:recommended', // ESLint의 권장 설정 사용
    'plugin:@typescript-eslint/recommended', // TypeScript에 대한 ESLint 권장 설정 사용
    'plugin:react/recommended', // React에 대한 ESLint 권장 설정 사용
    'plugin:prettier/recommended', // Prettier와 함께 사용할 권장 설정 사용
  ],
  overrides: [
    {
      env: {
        node: true, // Node.js 환경에서 실행되는 코드에 대한 설정
      },
      files: ['.eslintrc.{js,cjs}'], // 해당 파일에만 적용되는 설정
      parserOptions: {
        sourceType: 'script', // 파일이 스크립트 형식인지를 지정
      },
    },
  ],
  parser: '@typescript-eslint/parser', // TypeScript 코드를 파싱하는 데 사용할 파서 지정
  parserOptions: {
    ecmaVersion: 'latest', // ECMAScript 최신 버전 사용
    sourceType: 'module', // 모듈 형식의 코드 사용
  },
  plugins: ['@typescript-eslint', 'react', 'prettier'], // 사용할 플러그인 목록
  rules: {
    'react/react-in-jsx-scope': 'off', // JSX 파일에서 React import 없이 JSX 사용을 허용
  },
};

• env: 프로젝트에서 사용하는 환경을 설정한다. 위의 예제에서는 브라우저와 ECMAScript 2021을 사용하도록 설정되어 있다.
• extends: 프로젝트에 적용할 ESLint 구성을 확장한다. 위의 예제에서는 ESLint의 기본 설정과 React 플러그인의 권장 설정을 확장하고 있다.
• parserOptions: ESLint가 코드를 파싱하는 방법을 설정, 위의 예제에서는 ECMAScript 버전 및 모듈 형식을 설정하고 있다.
• plugins: 사용할 ESLint 플러그인을 설정한다. 위의 예제에서는 React 플러그인을 사용하고 있다.
• rules: 프로젝트에서 사용할 규칙을 설정한다. 필요한 경우 추가적인 규칙을 적용

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

예제 입력 1

8

예제 출력 1

92

문제 요약 :

N X N 체스판에서 N개의 퀸을 서로 공격할 수 없게 위치시키는 경우의 수 찾기

🧀 N-Queens

N개의 Queen을 서로 상대방을 위협하지 않도록 NxN 판에 위치시키는 문제

• 서로 상대를 위협하지 않도록
  • 같은 행, 같은 열, 같은 대각선 상에 위치 시키지 않아야한다.
• 각 세대별로 1번 Queen 을 놓는 경우의 수 N개, 2번 Queen 을 놓는 경우의 수 N개, N번 Queen 을 놓는 경우의 수 N개로
• 총 N개의 자식들을 가지는 N개의 깊이의 상태공간트리를 가진다.
  • 모든 경우의 수는 N X N +1 개가 된다.
  • 불필요한 재귀호출을 수행하지 않도록 유망한 노드만 세는 게 합리적이다. → 백트래킹

깊이우선탐색 + 되추적 알고리즘을 사용하는게 적합하다.

풀이 방법

• 두 말을 같은 행, 같은 열, 같은 대각선에 둘 수 없다.
  • 열의 차이와 행의 차이가 같으면 대각선의 위치가 같은 셈이다.

if(col(i) == col(k)) //같은 열(행)에 위치시키는 경우 -> 유망하지 않다.

if(abs(col(i)-col(k)) == abs(i-k))//열의 차이와 행의 차이가 같다.
                                                            //대각선 위치가 같다 -> 유망하지 않다.

• 0,0( 0번 행, 0번 열) 부터 시작해서 한 행씩, 한 열씩 유망성을 검사한다.
  • 0번 행에서 0번 열의 위치가 유망하다면 다음 행으로 이어서 진행한다.
    • 자식 노드로 이동하듯이 다음 행으로 쭉쭉 진행(DFS)
  • 해당 노드가 유망하지 않다면 현재 행의 다음 열 (0,1)로 이동한다.
• N번 행에 다다를 때까지 진행
  • N번 행에 도착하면 경우의 수를 증가시킨다.

풀이

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int N;
vector<int> col;
int answer = 0;

bool promising(int row){
    for(int i = 0; i < row; i++)
    {
        if(col[i] == col[row] || abs(col[i] - col[row]) == abs(i - row)){
            return false;
        }
    }
    return true;      
}

void DFS(int row){
    if(row == N){
        answer++;
        return;
    }
    for(int column = 0; column < N; column++){
        col[row] = column;//0,0위치부터 퀸을 놓기 시작

        if(promising(row)){
            DFS(row + 1);//다음 행 진행
        }
        //유망하지 않다면 다음 열 진행
    }
}

int main(){
    cin >> N;
    col.resize(N);

    DFS(0);

    cout << answer <<endl;
    return 0;
}

주석 추가

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int N;
vector<int> col;
int answer = 0;

//유망성 여부를 확인하는 함수
bool promising(int row){
        //현재 행에서 
    for(int i = 0; i < row; i++)
    {
                //같은 열에 위치되거나 대각선에 퀸이 놓여있으면 false
        if(col[i] == col[row] || abs(col[i] - col[row]) == abs(i - row)){
            return false;
        }
    }
    //그렇지 않으면 유망하다
    return true;      
}

//DFS로 체스판 위에서 말을 이동시킬 함수
void DFS(int row){
        //N번째 행까지 말을 위치시켰으면 경우의 수를 증가시킨다.
    if(row == N){
        answer++;
        return;
    }
      //현재 행에서 열을 옮기면서 반복
    for(int column = 0; column < N; column++){
        col[row] = column;//0,0위치부터 퀸을 놓기 시작
        //현재 위치가 유망하다면
        if(promising(row)){
            DFS(row + 1);//다음 행 진행(깊이 우선 탐색)
        }
        //유망하지 않다면 현재 행의 다음 열 진행(가지치기)
    }
}

int main(){
    cin >> N;
    col.resize(N);//벡터 크기 설정

    DFS(0);//0번 행부터 시작

    cout << answer <<endl;
    return 0;
}

되추적 알고리즘

• 되추적 알고리즘은 상태공간트리에서 깊이 우선 탐색 (DFS)를 실시
• 유망하지 않은 노드들은 가지( pruning )쳐서 검색하지 않는다.
• 유망한 노드에 대해서만 그 노드의 자식 노드들을 검색한다.

🎯 상태공간트리( state space tree) root에서 leaf까지의 경로가 해답 후보가 되는 트리, 깊이 우선 검색으로 그 해답 후보 중 해답을 찾을 수 있다.

유망성과 되추적

정의 : promising ( 유망하다 )

• 전혀 해답이 나올 가능성이 없는 노드는 유망하지 않다. (non-promising)
• 해답이 나올 가능성이 있는 노드를 유망하다(promising) 고 한다.

정의 : 되추적이란?

• 어떤 노드의 유망성을 점검하고
• 유망하지 않다고 판정되면
• 그 노드의 부모(parent) 노드로 돌아가서 (되추적)
• 다음 후손 노드에 대한 검색을 계속 진행하는 과정

백트래킹 : 모든 노드 중 특정한 조건을 만족하는 해가 될 것 같은 노드만 살펴보는 것이다. 불필요한 부분을 쳐내고 최대한 올바른 해만 찾아보는 방식

진행 절차

1. 상태공간트리의 깊이우선 탐색 (Depth -first-Search) 실시
2. 각 노드가 유망한 지 점검( 해답이 나올 가능성이 있는가)
3. 만일 그 노드가 유망하지 않다면, 그 노드의 부모 노드로 돌아가 검색을 계속한다.

DFS와의 차이

DFS 깊이우선탐색은 가능한 모든 경로를 탐색한다.

백트래킹은 유망한 경로만 탐색한다.

• 불필요한 경로를 사전에 차단하지 않고 모든 경로를 탐색하기 때문에 경우의 수를 최적으로 줄이지 못한다.
• 반면에 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보기 때문에 가지치기(pruning) 에 따라 효율이 달라질 수 있다.

되추적 알고리즘 의사코드

void checknode (node v) {
    node u;
    if(v노드가 유망하다면){
        if( v노드에 해답이 있다면)
            해답 찾기;
        else
            for( v의 각 자식노드 u에 대해)
                checknode(u);
        }
}

Monte Carlo 기법

몬테 카를로 기법을 사용한 백트래킹 알고리즘의 수행 시간 추정

• 몬테 카를로 기법 : 무작위 변수를 이용해 기대값을 추정한다.
• 샘플 공간에서 샘플을 뽑아 평균을 내고 이를 반복해 기대값을 추정한다.

→ 열어야하는 노드의 갯수를 계산하지 않고 추정한다.

몬테 카를로 기법의 조건

1. 상태공간트리에서 같은 수준 (same level)에 있는 모든 노드에서 같은 유망함수를 사용해야한다.
2. 상태공간트리에서 같은 수준 (same level) 에 있는 모든 노드들은 같은 수의 자식노드를 가져야한다.

Monte Carlo 기법을 사용한 백트래킹 알고리즘의 수행시간 추정 방법

1. root 노드의 유망한 자식 노드의 개수를 M_0라고 한다.
2. 상태공간트리의 수준 1 (root노드의 자식세대) 에서 유망한 노드 하나를 무작위로 정하고, 그 노드의 유망한 자식 노드의 개수를 M_1라고 한다.
3. 위에서 정한 노드의 유망한 노드 하나를 다시 무작위로 정하고 , 그 노드의 유망한 자식 노드의 개수를 M_2라고 한다.
4. 더 이상 유망한 자식노드가 없을 때까지 이 과정 반복

M_i : 수준 i의 마디들에서 유망한 자식 마디의 평균 개수 추정치

T_i : 수준 i의 어떤 노드의 자식 노드의 총 개수

검사한 마디 총 개수의 추정치 :

1 + T_0 + M_0T_1+M_1T_2+M_2T_3….+M_i-1T_i

몬테 카를로 기법은 2번 이상 실행해 추정치를 구하고 여러 번 수행하면 좋은 추정치를 구할 확률이 높아진다. 하지만 그 확률을 보장할 수는 없다.

백트래킹 알고리즘 활용

• 0-1 knapsack 문제
• n-Queens problem 백준 9663번 N-Queen
• 부분 집합의 합 구하기
• 그래프 탐색

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

예제 입력 1

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

예제 출력 1

4
3

문제 요약:

서류 심사와 면접 심사 순위가 주어질때 두 점수 모두 남보다 떨어지지 않는 사람만 채용할 때 선발할 수 있는 신입사원의 수 구하기

(A점수나 B 점수가 꼴찌가 아닌 사람만 채용)

생각할 점

• 서류 심사와 면접 심사 순위를 벡터 pair로 입력받는다.
• 입력받은 서류 심사 순위를 기준으로 오름차순으로 정렬( 1→2등이니까)
• 서류 심사 1위는 무조건 채용된다. → 채용되는 인원은 1명부터 시작
• 채용하는 인원들을 pick에 저장해두고 인원 수 만큼 반복문으로 채용할 사람 찾기
  • 면접 심사 순위를 기준으로 현재 1등보다 순위가 낮으면 → 낮다(순위가 높다)
  • 채용하고 갱신

    주의할 점: 여러테스트 케이스를 한번에 출력하기 때문에 마지막에 개행문자로 줄바꾸기를 해야 통과가 된다...!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T,N;
    cin >> T;

    while(T--) 
    {
        cin >> N;

        vector<pair<int,int>> score;

        for(int i=0;i < N;i++) {
            int a,b;
            cin >> a >> b;
            score.push_back({a,b});
        }

        sort(score.begin(),score.end());

        int temp = 0;
        int pick = 1;

        for(int i=1;i < N;i++) {
            if(score[temp].second > score[i].second) {
                pick++;
                temp=i;
            }
        }
        cout << pick <<"\n";
    }
}

주석 추가

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
//테스트 케이스 T, 사람수 N
    int T,N;
    cin >> T;
    //테스트 케이스만큼 반복
    while(T--) 
    {
        cin >> N;
        //서류 심사 순위, 면접심사 순위
        vector<pair<int,int>> score;

        //순위 입력 받기
        for(int i=0;i < N;i++) {
            int a,b;
            cin >> a >> b;
            score.push_back({a,b});
        }
                //서류 심사 순위를 기준으로 오름차순 정렬
        sort(score.begin(),score.end());

                //현재 서류 심사 1위의 인덱스 = 0
        int temp = 0;
        //서류 심사 1위는 무조건 채용되므로 선발된 인원을 1로 초기화
        int pick = 1;

                //면접 심사 순위를 비교해서 선발할 인원 찾기
        for(int i=1;i < N;i++) {
                //면접 심사 순위가 더 작은(순위가 더 높은) 사람을 찾으면
            if(score[temp].second > score[i].second) {
                    //선발하고 인덱스 갱신
                pick++;
                temp=i;
            }
        }
        cout << pick <<"\n";
    }
}

Lv.1 체육복

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

입출력 예 설명

예제 #1

1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2

3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

문제 요약:

바로 앞이나 뒷번호 학생에게만 체육복을 빌려줄 수 있을 때 체육 수업을 들을 수 있는 최대의 학생 수 구하기

생각할 점

• 일단 모든 학생이 체육복을 하나씩 가지고 있다고 생각하고
• 도난 당한 학생들의 경우 체육복 수를 감소, 여벌이 있는 학생의 경우 체육복 수를 증가시킨다.
• 체육복 빌려주기
  • 체육복이 없는 학생일 때 이전 번호와 다음 번호 학생이 여벌 체육복이 있는경우 빌려준다.
  • 빌린 학생 i는 수를 증가시키고 빌려준 학생 i-1 이나 i+1은 감소
• 수업을 들을 수 있는 학생수를 센다.

#include <iostream>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> student(n, 1); // 모든 학생은 일단 체육복을 가지고 있다고 가정

    // 체육복 도난당한 학생들의 체육복 개수 감소
    for(int i : lost) {
        student[i - 1]--;
    }

    // 여벌의 체육복을 가져온 학생들의 체육복 개수 증가
    for(int i : reserve) {
        student[i - 1]++;
    }

    // 체육복 빌려주기
    for(int i = 0; i < n; i++) {
        if(student[i] == 0) { // 체육복이 없는 경우
            if(i > 0 && student[i - 1] == 2) { // 이전 번호 학생이 여벌의 체육복이 있는 경우
                student[i]++;
                student[i - 1]--;
            }
            else if(i < n - 1 && student[i + 1] == 2) { // 다음 번호 학생이 여벌의 체육복이 있는 경우
                student[i]++;
                student[i + 1]--;
            }
        }
    }

    // 수업을 들을 수 있는 학생 수 계산
    for(int i = 0; i < n; i++) {
        if(student[i] > 0) {
            answer++;
        }
    }

    return answer;
}

주석 추가

#include <iostream>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> student(n, 1); // 모든 학생은 일단 체육복을 가지고 있다고 가정

    // 체육복 도난당한 학생들의 체육복 개수 감소
    for(int i : lost) {
        student[i - 1]--;
    }

    // 여벌의 체육복을 가져온 학생들의 체육복 개수 증가
    for(int i : reserve) {
        student[i - 1]++;
    }

    // 체육복 빌려주기
    for(int i = 0; i < n; i++) {
        if(student[i] == 0) { // 체육복이 없는 경우
            if(i > 0 && student[i - 1] == 2) { // 이전 번호 학생이 여벌의 체육복이 있는 경우
                student[i]++;
                student[i - 1]--;
            }
            else if(i < n - 1 && student[i + 1] == 2) { // 다음 번호 학생이 여벌의 체육복이 있는 경우
                student[i]++;
                student[i + 1]--;
            }
        }
    }

    // 수업을 들을 수 있는 학생 수 계산
    for(int i = 0; i < n; i++) {
        if(student[i] > 0) {
            answer++;
        }
    }

    return answer;
}

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 2자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

문제 요약: 숫자 number에서 k개 만큼의 수를 제거하고 만들 수 있는 수 중 가장 큰 수 찾기

생각할 점:

• 크기를 비교하는 숫자들의 자릿수는 모두 같다.
  • 정답 문자열 answer의 길이는 number.size() - k
• 숫자 문자열의 첫 인덱스가 높은 숫자일 수록 크다
• 인덱스 순으로 큰 숫자인지를 비교
• 그리디 알고리즘!

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";

    int numSize = number.size() - k;
    int index = 0;

    for(int i=0; i < numSize; i++) {
        char maxNum = number[index];
        int maxIdx = index;
        for(int j = index; j <= k+i; j++) {
            if(maxNum < number[j]) {
                maxNum = number[j];
                maxIdx = j;
            }
        }
        index = maxIdx + 1;
        answer += maxNum;
    }

    return answer;
}

주석 추가 버전

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
 //정답 배열의 길이는 number.size() -k
    int numSize = number.size() - k;
 //탐색을 시작할 인덱스
    int index = 0;
    //인덱스 0번 부터 i + numsize 만큼 반복
    for(int i=0; i < numSize; i++) {
            //number에서 가장 큰 수의 값을 maxNum에 저장
        char maxNum = number[index];
            //가장 큰 수의 인덱스를 maxIdx에 저장
        int maxIdx = index;
            //정답이 될 수의 배열에서 가장 큰 수를 찾아서 갱신해주기
        for(int j = index; j <= k+i; j++) {
            if(maxNum < number[j]) {
                maxNum = number[j];
                maxIdx = j;
            }
        }

        index = maxIdx + 1;
        answer += maxNum;
    }

    return answer;
}

문제

평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

입력

첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1 ≤ S ≤ 1,000,000), 그리고 주문받은 파닭의 수 C(1 ≤ C ≤ 1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S ≤ C) 그 후, S 줄에 걸쳐 파의 길이 L(1 ≤ L ≤ 1,000,000,000)이 정수로 입력된다.

출력

승균이가 라면에 넣을 파의 양을 출력한다.

예제 입력 1

3 5
440
350
230

예제 출력 1

145

힌트

파닭 하나당 넣을 수 있는 최대 파의 길이는 175cm으로, 440cm 파에서 2개, 350cm 파에서 2개, 230cm 파에서 1개, 총 5개의 파닭을 만들 수 있고, 각각의 파에서 90cm + 0cm + 55cm = 145cm의 파가 남는다.

문제 요약

입력받은 길이가 다른 파들의 최대 파 길이를 찾아 C개의 파닭을 만들고 남은 파의 길이를 구하기

생각할 점

• C개의 파닭을 전부 만들 수 있는 파의 길이를 이진 탐색으로 찾고 그 때 각 파에서 얼만큼의 길이가 남는지를 구한다.
• 파닭 하나당 넣을 수 있는 최대 파의 길이를 이진탐색으로 찾고
• 전체 파 길이를 구해서 ( 최대파 길이 * 치킨 수 )를 빼준다.

#include <iostream>
#include <vector>
using namespace std;

int main(){

    long long S, C; 
    cin >> S >>C;
    vector<long long> L(S);
    for(int i = 0; i < S; i++){
      cin >> L[i];  
    } 

    long long min = 1;
    long long max = 1e9;
    long long total = 0;
    long long maxPa = 0;

    while(min <= max){
        long long mid = (min + max) / 2;
        long long sum = 0;
        for(int i=0; i < L.size(); i++){
            if(L[i] >= mid) 
                sum += L[i] / mid;
        }
        if(sum >= C){
            maxPa = mid;
            min = mid + 1;
        }
        else 
            max = mid - 1;
    }

    for(int i=0; i<L.size(); i++){
       total += L[i];
    } 

    cout<< total - maxPa * C << endl;
}

주석 버전

#include <iostream>
#include <vector>
using namespace std;

int main(){
    //S는 파의 수, C는 만들 파닭의 수
    long long S, C; 
    cin >> S >>C;
        //파들의 길이를 저장할 벡터 L
    vector<long long> L(S);
    for(int i = 0; i < S; i++){
      cin >> L[i];  
    } 
    //파의 최소 길이
    long long min = 1;
        //파의 최대 길이 (파 길이의 범위가 1~10의 9승임)
    long long max = 1e9;
        //전체 파길이
    long long total = 0;
        //파닭 하나 당 들어가는 최대 파의 길이
    long long maxPa = 0;

    while(min <= max){
                //C개의 파닭을 만들기 위해 탐색할 파 길이의 중간값
        long long mid = (min + max) / 2;
                //만들 수 있는 파닭의 수
        long long sum = 0;

                //파길이들을 mid로 나누면 최대 파길이가 mid일 때 만들 수 있는 
                //파닭의 수를 구할 수 있다.
        for(int i=0; i < L.size(); i++){
            if(L[i] >= mid) 
                sum += L[i] / mid;
        }
                //C개의 파닭을 만들 수 있으면 최대 파길이 maxPa가 mid이거나
                //mid 보다 크다.
        if(sum >= C){
            maxPa = mid;
            min = mid + 1;
        }
                //C개의 파닭을 만들 수 없으면 탐색 범위가 잘못된 경우다.
        else 
            max = mid - 1;
    }
    //전체 파길이의 합 total
    for(int i=0; i<L.size(); i++){
       total += L[i];
    } 
    //전체 파길이의 합 - 최대 파길이 * 파닭 수   
    cout<< total - maxPa * C << endl;
}

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

문제 요약 :

각 심사관마다 심사하는 시간이 times로 주어졌을 때 n명의 사람이 심사를 받는 총 시간 구하기

생각할 점:

이진 탐색을 사용

• 입국 심사 시간 벡터를 오름차순으로 정렬한다.
• 최소 시간, 제일 오래걸리는 시간으로 초기화해서 시간들을 이진 탐색
  • 심사대의 수 : times.size()
  • 가장 적게 걸리는 시간 → 사람수가 1이고 심사 시간이 1인 경우 → 1
  • 제일 오래걸리는 시간? → 가장 오래걸리는 검색대 * n명인 경우
  • times 벡터의 가장 마지막 심사대의 시간이 가장 오래걸리는 검색대이다.
• mid 시간 동안 통과할 수 있는 사람의 수를 passed에 저장해서
• passed(mid 시간동안 처리할 수 있는 사람수)가 n보다 작으면 조건을 만족하지 못하니까 최소의 범위를 늘려서 탐색범위를 이동

(mid 시간 안에 n명을 심사할 수 없다 → 시간을 늘려줘야함)

• passed가 n보다 크면 mid 가 답이 될 수 있으므로 answer에 넣어주고 최대의 범위를 더 좁혀서 최소값을 찾을 수 있는 탐색 범위로 이동

  (mid 시간 안에 n명 심사가 가능하다 → 답이 mid 이거나 mid보다 작은 시간이다)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    sort(times.begin(),times.end());

    long long min = 1;
    long long max = (long long) times[times.size()-1] * n;

    while(min <= max){
        long long mid = (min + max)/2;
        //mid 시간동안 통과한 사람의 수
        long long passed = 0;
        for(int i =0; i < times.size(); i++){
            //mid 시간을 심사한 시간들로 나눈 값을 더하면 통과한 사람 수
            passed += (mid / times[i]);
        }
        if(passed < n){
            min = mid+1;
        }
        else{
            answer = mid;
            max = mid-1;
        }
    }

    return answer;
}

코드 설명

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {

    long long answer = 0;

        //심사하는 시간들을 오름차순 정렬
    sort(times.begin(),times.end());

    //총 심사하는 데 가장 적게 걸리는 시간( 1명 * 심사대 소요 시간 1)
    long long min = 1;

        //가장 오래 걸리는 시간 ( 벡터의 가장 마지막 심사대의 시간 * 전체 인원)
        //전체 인원이 가장 오래 걸리는 심사대에서 심사를 받는 게 가장 오래걸린다.
    long long max = (long long) times[times.size()-1] * n;

    //이진 탐색
    while(min <= max){
                //mid = 이진 탐색을 위한 가장 중간 값(소요되는 가장 중간 시간)
        long long mid = (min + max)/2;

        //mid 시간동안 통과한 사람의 수
        long long passed = 0;

        for(int i =0; i < times.size(); i++){
            //mid 시간을 심사한 시간들로 나눈 값들을 더하면 통과한 사람 수
            passed += (mid / times[i]);
        }

                //mid 시간동안 통과한 사람의 수가 찾고 있는 n보다 작다면
                //탐색 범위가 잘못 된 경우-> mid 시간 동안 n명을 심사할 수 없다.
        if(passed < n){
                    // 탐색 시간을 늘려줘야함
            min = mid+1;
        }
                //n명 이상이 심사 받은 경우 mid 시간 안에 n명의 심사가 가능하다.
                //즉 답이 mid이거나 mid 보다 적은 값이다.
        else{
            answer = mid;
            max = mid-1;
        }
    }

    return answer;
}

같은 문제

백준에서 찾은 동일한 문제 백준 3079번: 입국심사

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {
    int N;
    long long M;
    long long answer = 0;
    vector<int> T;

    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        int x;
        cin >> x;
        T.push_back(x);
    }

    sort(T.begin(), T.end());

    long long min = 1;
    long long max = T[N-1]* M;

    while(min <= max) {
        long long mid = (min + max) / 2;
        long long passed = 0;
        for(int i = 0; i < N; i++) {
            passed += (mid / T[i]);
                //오버플로우 방지를 위해서 break 문 필요
            if(passed >= M)
                break;
        }

        if(passed < M){
            min = mid+1;
        }
        else{
            answer = mid;
            max = mid-1;
        }
    }

    cout << answer << endl;
    return 0;
}

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1

5 3
1
2
8
4
9

예제 출력 1

3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

문제 요약:

입력받은 집의 수 만큼 집의 좌표를 입력받아 C개의 공유기를 설치할 때 C개의 공유기를 적절히 설치해서 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

🤔 생각할 점 :

• C개의 공유기를 모두 설치해야한다.
• 집이 꼭 바로 옆에 붙어 있지 않아도 된다.
• 집 좌표가 순서대로 들어오지 않음→ 오름차순 정렬
• 찾아야 하는 것 : 집들 사이의 거리

풀이 방법 :

1. N : 집의 수 , C : 공유기 수 , house : 집 좌표 벡터

2. 집 좌표를 입력받아서 오름 차순 정렬

3. 집들 사이 거리를 기준으로 이진 탐색

   start는 집들 사이의 최소 거리 1로 초기화하고 , end는 집들 사이의 최대 거리(끝집 - 첫집의 거리)로 초기화한다.

4. 중간값을 기준으로 공유기를 설치할 수 있는지 확인, 설치 가능하면

   • start = mid + 1 → 탐색범위를 중간을 기준으로 오른쪽으로 이동, 최적의 거리를 업데이트 해준다.
   • 설치할 수 없다면 end = mid - 1 → 탐색범위를 중간을 기준으로 왼쪽으로 좁힌다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, C;
int result = 0;
vector<int> house;

int binarySearch() {
    int start = 1;
    int end = house[N - 1]-house[0];
    int result = 0;

    while (start <= end) {
        int mid = (start + end) / 2;
        int count = 1;
        int temp = 0;

        for (int i = 1; i < N; i++) {
            if ((house[i] - house[temp]) >= mid) {
                temp = i;
                count++;
            }
        }
        if (count >= C) {
            result = mid;
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return result;
}

int main() {
    cin >> N >> C;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        house.push_back(x);
    }

    sort(house.begin(), house.end());

    result = binarySearch();
    cout << result << endl;
    return 0;
}

🌟메인 함수

int main() {
    cin >> N >> C;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        house.push_back(x);
    }
    // 1. 좌표 정렬
    sort(house.begin(), house.end());

    // 2. 집들 사이 거리에 대한 이진 탐색
    result = binarySearch();
    cout << result << endl;
    return 0;
}

이진 탐색 함수

int binarySearch() {
//3. 초기화
//start-> 최소 거리인 1, end -> 집들 사이 최대 거리(맨 끝집 - 맨 첫집)
    int start = 1;
    int end = house[N - 1]-house[0];
    int result = 0;
//4. 탐색
    while (start <= end) {
        int mid = (start + end) / 2;//중간값
                //count = 중간값을 기준으로 한 구간에 설치할 수 있는 공유기 개수
        int count = 1;
                //temp = 가장 최근에 공유기를 설치한 집 인덱스
        int temp = 0;
                //한 구간에 대해 설치할 수 있는 공유기의 수를 센다.
        for (int i = 1; i < N; i++) {
            if ((house[i] - house[temp]) >= mid) {
                temp = i;
                count++;
            }
        }
                //count가 주어진 공유기의 개수 C보다 크거나 같은 경우 탐색 범위를 오른쪽으로 좁힌다.
        if (count >= C) {
            result = mid;
            start = mid + 1;
        } 
                //그렇지 않은 경우에는 탐색 범위를 왼쪽으로 좁힌다.
                else {
            end = mid - 1;
        }
    }
    return result;
}

문제 설명

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.
2. words에 있는 단어로만 변환할 수 있습니다.

예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

입출력 예 설명

예제 #1

문제에 나온 예와 같습니다.

"hit" -> "hot" -> "dot" -> "dog" -> "cog"

예제 #2

target인 "cog"는 words 안에 없기 때문에 변환할 수 없습니다.

문제 요약:

begin 문자열을 한 문자씩 바꿔서 words 안의 문자열로 변화시키는 데 target문자열이 되도록 하려면 몇 단계를 거쳐야 하는지 찾기

생각할 점:

• 한 단계에 한 문자만 바뀐다.
• words 배열 안에 없는 단어로는 변환할 수 없다.

몇 단계 ? → begin 노드부터 target 노드까지 도달하는데 몇 개의 엣지가 필요한가

풀이 방법:

Q. words 문자열 벡터에서 한 글자만 다른 단어를 어떻게 찾을건가

• words 벡터에 대해 begin과 1글자만 다르면 변환 가능

Q. begin 문자열에서 target 문자열까지 가는 경로 찾기

• BFS 사용 ( 현재 문자열을 큐에 넣어서 이미 방문했는지 + 변환가능한 단어인지 검사)
  • 인접여부 대신 변환 가능 여부(다음 순서로 올 수 있는가)

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<bool> visited(51, false);

// 현재 문자와 다음 문자가 변환 가능한지 체크하는 함수
bool changeable(string before, string after) {
    int diff = 0;
    for (int i = 0; i < before.size(); i++) {
        if (before[i] != after[i]) 
                    diff++;
    }
    return diff == 1;
}

// BFS 함수
int BFS(const string& begin, const string& target, vector<string>& words) {
    queue<pair<string, int>> q;
    q.push({begin, 0});

    while (!q.empty()) {
        string node = q.front().first;
        int index = q.front().second;
        q.pop();

        if (node == target) 
            return index; 

        for (int j = 0; j < words.size(); j++) {
            if (!visited[j] && changeable(node, words[j])) {
                q.push({words[j], index + 1});
                visited[j] = true;
            }
        }
    }
    return 0; //도달하지 못하면 0반환
}

int solution(string begin, string target, vector<string> words) {
    return BFS(begin, target, words);
}

큐 페어가 아닌 문자열 큐로 생성해서 한 단계 탐색이 끝나면 Index를 증가시키는 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<bool> visited(51, false);

// 현재 문자와 다음 문자가 변환 가능한지 체크하는 함수
bool changeable(string before, string after) {
    int diff = 0;
    for (int i = 0; i < before.size(); i++) {
        if (before[i] != after[i]) 
                    diff++;
    }
    return diff == 1;
}
// BFS 함수
int BFS(const string& begin, const string& target, vector<string>& words) {
    queue<string> q;
    q.push(begin);
    int index = 0;

    while (!q.empty()) {
        for (int i = 0; i < q.size(); i++) { // 현재 단계의 단어들에 대해 탐색
            string node = q.front();
            q.pop();

            if (node == target) 
                return index; 

            for (int j = 0; j < words.size(); j++) {
                if (!visited[j] && changeable(node, words[j])) {
                    q.push(words[j]);
                    visited[j] = true;
                }
            }
        }
        index++; // 한 단계의 탐색이 끝났으므로 index를 증가시킴
    }
    return 0; 
}

int solution(string begin, string target, vector<string> words) {
    return BFS(begin, target, words);
}

🌟 chageable

현재 문자열(노드) 이 다음 문자열로 변환될 수 있는지 확인하는 함수

• 한 문자만 다르고 전부 같아야한다.→ 다른 문자의 수를 diff 변수로 세서 다른 문자가 하나이면 true

//before : 현재 문자열, after: 다음 문자열
bool changeable(string before, string after) {
    int diff = 0;
    for (int i = 0; i < before.size(); i++) {
            //문자 하나씩 비교해서 다르면 다른 문자 수 세기
        if (before[i] != after[i]) 
                    diff++;
    }//1개면 변환 가능 -> true
    return diff == 1;
}

🌟BFS

int BFS(const string& begin, const string& target, vector<string>& words) {
//검색할 문자열들을 담을 큐 q
    queue<string> q;
//첫번째 문자 begin을 큐에 추가
    q.push(begin);
    int index = 0;

    while (!q.empty()) {
//큐에 있는 문자열들을 큐에 맨 앞에 있는 문자열을 빼서 BFS 검사
        for (int i = 0; i < q.size(); i++) { // 현재 단계의 단어들에 대해 탐색
            //현재 검사중인 문자열 => node : 큐의 맨 앞에 있는 문자열
            string node = q.front();
            q.pop();
            //현재 검사중인 문자열이 찾을 문자열이면 index(단계)를 반환
            if (node == target) 
                return index; 
            for (int j = 0; j < words.size(); j++) {
                                //방문하지 않았고, 다음 문자열로 변환이 가능하다면 
                if (!visited[j] && changeable(node, words[j])) {
                                        //큐에 추가해주고 방문 처리
                    q.push(words[j]);
                    visited[j] = true;
                }
            }
        }
        index++; // 큐의 한 요소에 대한 탐색( 한 단계)가 끝나고 인덱스 증가
    }
    return 0; //타겟에 도달하지 못하면 0 반환
}

DFS로 풀이

#include <string>
#include <vector>

using namespace std;

vector<bool> visited(51,false);

bool changeable(string before, string after) {
    int diff = 0;
    for(int i = 0; i < before.size(); i++) {
        if(before[i] != after[i])
            diff++;
    }
    return diff == 1;
}

// DFS 함수
int DFS(const string& current, const string& target, vector<string>& words, int depth) {
//타겟 단어를 찾으면 단계(타겟을 찾으러 내려간 깊이) 반환
    if (current == target) 
        return depth;

    int minDepth = 0; // 최소 깊이 초기화(루트)
    for (int i = 0; i < words.size(); i++) {
            //아직 방문하지 않았고 현재 단어에서 변환 가능한 단어이면
        if (!visited[i] && changeable(current, words[i])) 
        {
                    //방문 처리
            visited[i] = true;
                    //해당 노드를 기준으로 다음 노드 방문을 위해 DFS 재귀
                    //단계 증가
            int result = DFS(words[i], target, words, depth + 1);
                    //최소 깊이 갱신해주기!(루트에서 다음 자식이동...등)
            if (result != 0) 
            {
                if (minDepth == 0 || result < minDepth)
                    minDepth = result;
            }
                    //이 길이 더이상 답이 없으면 방문처리 취소( 백트래킹)
            visited[i] = false; // 백트래킹
        }
    }
    return minDepth;
}

int solution(string begin, string target, vector<string> words) {
    int answer = DFS(begin, target, words, 0);
    return answer;
}

1260번 DFS와 BFS 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

예제 입력 1

4 5 1
1 2
1 3
1 4
2 4
3 4

예제 출력 1

1 2 4 3
1 2 3 4

예제

DFS : 한 경로로 계속 이어지는 경로를 먼저 찾아야함

• 1번 노드에서 시작해서 이어진 다음노드 2번 방문
• 2번에서 이어지는 노드 4번 방문
• 4번에서 이어지는 노드 3번 방문

BFS : 시작 노드로부터 다른 노드로 이어지는 모든 경로를 먼저 찾아야함

• 1번 노드에서 시작해서 연결된 노드 2번 방문
• 1번 노드에서 연결된 3번 , 4번 방문

문제 요약:

입력받은 노드와 간선의 정보를 토대로 그래프에 DFS와 BFS를 수행한 결과를 출력

🤔 생각할 점:

• 입력으로 주어지는 간선은 양방향
• 방문한 노드는 방문처리하기
• DFS 는 재귀나 스택 , BFS 는 큐로 구현

풀이 방법:

• N : 노드의 갯수 , M : 간선의 갯수 , V : 탐색을 시작할 노드(루트 노드)
• 간선의 수만큼 연결된 노드들의 관계를 이차 배열에 입력받아 연결된 노드들은 1로 저장(인접 행렬 생성)
  • 양방향 그래프이므로 (u,v) , (v,u)를 전부 저장
• 입력된 관계들을 토대로 DFS, BFS를 실행

#include <iostream>
#include <queue>
using namespace std;

int arr[1001][1001]; //노드간의 관계
int visited_dfs[1001];   //방문 처리
int visited_bfs[1001];
int N, M, V;

// DFS - 재귀 사용
void DFS(int node)
{
    visited_dfs[node] = 1;   //방문 처리
    cout << node << " "; //방문한 노드 출력

    for (int i = 1; i <= N; i++)
    {
        if (arr[node][i] == 1 && visited_dfs[i] == 0)
        {
            DFS(i); //해당 노드를 스택에 넣는 셈
        }
        if (i == N)
            return;
    }
}

// BFS - 큐 사용 
void BFS(int node)
{
    queue<int> q; //큐 생성
    q.push(node);    //시작노드 큐에 넣음

    while (!q.empty())
    {
        int next = q.front(); //큐 맨 앞에 값을 방문
        visited_bfs[next] = 1;    //방문기록
        cout << next << " ";  //방문한 노드 출력
        q.pop();              //큐에서 뺌

        //방문했던 노드와 가까운 노드 큐에 넣어줌
        for (int i = 1; i <= N; i++)
        {
            if (arr[next][i] == 1 && visited_bfs[i] == 0)
            {
                q.push(i);         //큐에 넣어줌
                visited_bfs[i] = 1; // 노드 방문 기록
            }
        }
    }

}

int main()
{
    int u, v;
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        arr[u][v] = 1;
        arr[v][u] = 1; 
    }                  

    DFS(V); // DFS 수행
    cout << "\n";                        
    BFS(V); // BFS 수행
}

🌟메인 함수

int arr[1001][1001]; //노드간의 관계
int visited_dfs[1001];//dfs 방문 처리 배열
int visited_bfs[1001];//bfs 방문 처리 배열
int N, M, V; 
int main()
{
    int u, v;
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        arr[u][v] = 1;
        arr[v][u] = 1; 
    }                  

    DFS(V); // DFS 수행
    cout << "\n";                        
    BFS(V); // BFS 수행
}

• 초기화
  • N : 노드의 갯수 , M : 간선의 갯수 , V : 탐색을 시작할 노드(루트 노드) 입력
    • 다른 함수에서도 사용할 변수들이므로 전역 변수로 선언
  • 양방향 그래프이므로 (u,v) , (v,u) 모두 연결 ( 1로 ) 노드들의 관계 입력
• DFS, BFS수행 ( 두 출력 사이에 줄 바꿈 개행 출력)

🌟 DFS

void DFS(int node)
{
    visited_dfs[node] = 1;   //방문 처리
    cout << node << " "; //방문한 노드 출력

    for (int i = 1; i <= N; i++)
    {
        if (arr[node][i] == 1 && visited_dfs[i] == 0)
        {
            DFS(i); //해당 노드를 스택에 넣는 셈
        }
        if (i == N)
            return;
    }
}

• DFS의 매개변수로 들어오는 V (시작 노드)를 방문 여부를 저장하는 배열 visited_dfs에 1로 방문처리를 하고 방문한 노드는 출력해준다.

• arr[node][i] == 1 && visited_dfs[i] == 0

  현재 노드와 연결관계이고 방문한적 없는 노드에 대해 DFS 함수를 재귀 실행 (방문처리, 출력, 연결된 노드)

  • DFS는 현재 연결된 노드에서 연결관계가 있는 다른 노드들로 계속 이어서 연결하기 때문

🌟BFS

void BFS(int node)
{
    queue<int> q; //큐 생성
    q.push(node);    //시작노드 큐에 넣음

    while (!q.empty())
    {
        int next = q.front(); //큐 맨 앞에 값을 방문
        visited_bfs[next] = 1;    //방문기록
        cout << next << " ";  //방문한 노드 출력
        q.pop();              //큐에서 뺌

        //방문했던 노드와 가까운 노드 큐에 넣어줌
        for (int i = 1; i <= N; i++)
        {
            if (arr[next][i] == 1 && visited_bfs[i] == 0)
            {
                q.push(i);         //큐에 넣어줌
                visited_bfs[i] = 1; // 노드 방문 기록
            }
        }
    }
}

• 큐를 사용해 BFS 구현, 매개변수인 시작노드 V를 node라는 변수로 큐에 넣고
• 큐에 노드가 들어와서 비어있지 않으면 큐의 맨 앞의 값을 방문처리, 출력 후 큐에서 뺀다
• arr[node][i] == 1 && visited_dfs[i] == 0 : 해당 노드와 연결관계이고 방문하지 않은 노드를
• 큐에 넣고 방문 기록 해준다. 그럼 큐가 또 비지 않게 되니 반복문을 수행한다.

DFS(Depth-First-Search) : 깊이 우선 탐색

현재 탐색중인 경로를 끝까지 탐색하고 다음 경로로 넘어간다.

1. root 노드부터 먼저 검색
2. root노드의 자식 중 가장 왼쪽 노드 부터 탐색
3. 왼쪽 노드의 자식 중 왼쪽….을 탐색하고 다시 부모 노드로 돌아가서 오른쪽 자식 노드 탐색
4. 위 과정을 반복

→ 깊이 우선 탐색은 한 부모노드의 자식을 모두 한번에 검사하는게 아니라 한 가지를 타고 내려가서 가장 멀리있는 노드에 도달하고 나서 다음 다시 부모노드로 돌아와 다른 자식을 탐색한다.

🌟 주로 백트래킹 알고리즘에 사용

🎯EX

root 노드 1 부터 출발해서 다시 1로 돌아오는 경로 찾기

1. root 노드 1에서 인접한 자식 찾기(방문처리 +스택에 추가)

2. 5 노드를 스택에 추가하고 이어서 6번 노드 방문

3. 6번 노드를 스택에 추가하고 다음 경로가 없기 때문에 6번을 스택에서 제거

4. 다시 5번 노드로 되추적해서 연결된 다른 노드 7번 방문

   7번 노드에 연결된 다음 경로가 없기 때문에 7번은 스택에서 제거

   5번에 연결된 다른 노드가 없기 때문에 다시 루트노드로 되추적

5. 1번 노드에 연결된 다른 노드 2번으로 이동, 스택에 추가

6. 2번에 연결된 노드….를 반복

최종 경로 : 1→2→3→4→1

구현

• 주로 재귀 함수나 스택(stack)을 사용해 구현

  • 탐색 시작 노드를 스택에 삽입하고 방문처리

  • 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리

    방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.

  • 2번의 과정을 수행할 수 없을 때까지 반복

• 이미 방문한 노드에 대해서는 방문 처리를 해야한다. 그렇지 않으면 무한루프에 빠지게 된다.

• 탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)를 사용.

  • 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 추가된 노드의 부모노드로 돌아와서(백트래킹-backtracking), 다른 자식 노드 탐색

의사 코드

void depth_first_tree_search (node v) {
    node u;
    visit v;
    for (each child u of v)//방문중인 노드의 자식 u에 대해
        depth_first_tree_search(u);//depth-fisrt-seach 적용
}

C++ 구현

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// 그래프의 정점을 표현하는 구조체
struct Node {
    int data;
    vector<Node*> children;
    bool visited; // 방문 여부를 나타내는 변수

    // 생성자
    Node(int d) : data(d), visited(false) {}
};

// 깊이 우선 탐색 함수
void depth_first_search(Node* start) {
    stack<Node*> s;
    s.push(start);

    while (!s.empty()) {
        Node* current = s.top();
        s.pop();

        // 현재 노드를 방문
        if (!current->visited) {
            cout << "Visiting node: " << current->data << endl;
            current->visited = true;

            // 현재 노드의 자식들을 스택에 넣기
            for (Node* child : current->children) {
                s.push(child);
            }
        }
    }
}

int main() {
    // 그래프 생성
    Node* node1 = new Node(1);
    Node* node2 = new Node(2);
    Node* node3 = new Node(3);
    Node* node4 = new Node(4);
    Node* node5 = new Node(5);

    // 그래프의 간선 설정
    node1->children.push_back(node2);
    node1->children.push_back(node3);
    node2->children.push_back(node4);
    node2->children.push_back(node5);

    // 깊이 우선 탐색 실행
    depth_first_search(node1);

    return 0;
}

BFS(Breath-First-Search) : 너비 우선 탐색

같은 자식 레벨은 다 탐색하고 다음 레벨의 자식으로 넘어간다.

1. root 노드부터 먼저 검색
2. level 1의 모든 노드 검색(왼쪽 노드부터 오른쪽 노드로)
3. level 2…leaf마디 까지 모든 노드 검색

사용 : 그래프(최단 거리 구하기), 트리(트리를 레벨별로 탐색) 자료구조 탐색에 사용

🎯EX

1. 루트노드 1을 큐에 넣는다.
2. 1을 큐에서 꺼내고 인접 노드 2,3을 모두 큐에 넣는다.( 1 방문 처리)
3. 2를 큐에서 꺼내고 인접노드 4,5를 모두 큐에 넣는다.( 1 방문 처리)
4. 3을 큐에서 꺼내고 인접노드 6,7을 모두 큐에 넣는다.
5. 4를 큐에서 꺼내고 인접노드 8,9를 모두 큐에 넣는다.t
6. 5를 큐에서 꺼내고 인접노드 10을 큐에 넣는다.
7. 큐에 있는 노드들에 대해 같은 과정을 반복하고 큐가 비면 반복 종료

🌟 노드를 방문 하는 순서 : 1→2→3→…→10

구현

• 재귀 알고리즘을 구현하기는 어렵기 때문에 Queue를 사용해 구현
  • 시작 정점을 큐에 넣는다.( 큐에 들어간 노드는 방문 처리)
  • 큐에서 정점을 하나씩 꺼내면서 해당 정점에 인접한 정점들을 모두 큐에 넣는다.
  • 큐에서 다음으로 꺼낼 정점을 선택, 이 과정을 큐가 빌 때까지 반복(탐색 안한 노드가 없을 때까지)
• 이미 방문한 노드에 대해서는 방문 처리를 해야한다. 그렇지 않으면 무한루프에 빠지게 된다.

🧀 BFS에서 재귀 알고리즘을 구현하기 어려운 이유

• 너비우선 탐색은 level 별로 순차적으로 탐색을 진행하기 때문에 재귀적으로 호출될 때마다 해당 레벨을 추적하고 제어하기 어렵다.
• 재귀 호출은 함수 호출에 따른 오버헤드가 발생할 수 있다. queue를 사용한 반복적인 방식(iterative approach)에서는 이러한 오버헤드가 없으므로 더 효율적이다.

의사 코드

void breadth_first_search(tree T) {
    queue_of_node Q;
    node u, v;
    initialize(Q); // 큐 Q가 비도록 초기화
    v = root of T;//루트 노드 v
    visit v;//v 방문
    enqueue(Q,v);//v를 큐에 추가
    while(!empty(Q)) {//큐에 들어온 노드가 있다면
        dequeue(Q,v);//해당 노드를 큐에서 제거하고
        for(each child u of v) {//v의 자식들 u에 대해
            visit u;//u 방문
            enqueue(Q,u);//큐에 추가
        }
    }
}

C++ 구현

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// 그래프의 정점을 표현하는 구조체
struct Node {
    int data;
    vector<Node*> neighbors;
    bool visited; // 방문 여부를 나타내는 변수
};

// 너비우선 탐색 함수
void breadth_first_search(Node* start) {
    queue<Node*> q;

    // 시작 정점을 큐에 넣고 방문 처리
    q.push(start);
    start->visited = true;

    while (!q.empty()) {
        // 큐에서 정점을 하나씩 꺼냄
        Node* current = q.front();
        q.pop();

        // 현재 정점 방문
        cout << "Visiting node: " << current->data << endl;

        // 현재 정점의 모든 인접한 정점들에 대해
        for (Node* neighbor : current->neighbors) {
            // 인접한 정점이 방문되지 않았다면 큐에 넣고 방문 처리
            if (!neighbor->visited) {
                q.push(neighbor);
                neighbor->visited = true;
            }
        }
    }
}

int main() {
    // 그래프 생성
    Node* node1 = new Node{1, {}, false};
    Node* node2 = new Node{2, {}, false};
    Node* node3 = new Node{3, {}, false};
    Node* node4 = new Node{4, {}, false};

    // 그래프의 간선 설정
    node1->neighbors.push_back(node2);
    node1->neighbors.push_back(node3);
    node2->neighbors.push_back(node4);
    node3->neighbors.push_back(node4);

    // 너비우선 탐색 실행
    breadth_first_search(node1);

    return 0;
}

테이블 (table) :
데이터를 구조화해 저장하는 자료구조로 key-value 쌍으로 데이터를 입력 받아 키를 입력해 해당 쌍의 데이터를 찾아온다.

해시 테이블:

• 큰 테이블 하나를 키로 생각해서 key-value 쌍으로 데이터를 입력받는다.
• 해시 함수를 이용해 데이터를 고유한 해시값으로 인덱싱해서 전체 데이터 보다 작은 크기의 배열을 형성한다.

→ 충돌이 없다면 데이터를 한 번에 찾을 수 있어 효율적인 탐색( 빠른 탐색 ) 을 위한 자료구조이다.

시간복잡도:

• 해시 테이블의 평균 시간 복잡도는 O(1) 이다. 즉, 해시 테이블에서 데이터를 검색하거나 삽입하는 데 걸리는 평균 시간은 상수 시간에 해당한다.

해시 테이블은 빠른 검색 속도를 제공하며, 삽입과 삭제 연산도 상수 시간에 가깝게 수행될 수 있어 많은 데이터를 효율적으로 처리할 때 유용하다. 그러나 해시 함수의 선택과 충돌 해결 방법의 올바른 구현이 중요하며, 최악의 경우 충돌이 많이 발생할 경우 성능이 저하될 수 있다.

Direct-address Table

직접 주소화 테이블

배열을 사용해 각 키에 대한 인덱스를 사용하여 키-값 쌍을 저장하는 자료구조, key 값으로 k를 갖는 원소는 인덱스 k에 저장

키의 범위가 작고 연속적인 경우에 유용하며, 키를 직접 인덱스로 사용하여 배열에 접근하여 값을 저장하거나 검색할 수 있다.

공간 복잡도:

직접 주소화 테이블은 저장할 수 있는 키의 범위가 제한되어 있어 공간 복잡도가 상대적으로 높을 수 있다. 예를 들어, 키의 범위가 0부터 m까지이면 배열의 크기는 m+1이 된다.

→ 즉 불필요한 공간의 낭비가 발생

시간 복잡도:

직접 주소화 테이블은 키를 배열의 인덱스로 사용하여 바로 해당 위치에 접근하여 값을 저장하거나 검색할 수 있다. 따라서 데이터를 검색하거나 삽입하는 데 걸리는 시간 복잡도는 O(1) 즉, 상수 시간에 해당한다.

문제:

• 불필요한 공간 낭비
• key에 다양한 자료형을 담을 수 없다.(key가 즉 index니까)
• 서로 다른 키들이 같은 인덱스를 가리키는 경우 충돌 발생

Hash Table

해시 함수 h를 이용해 (key, value) 를 index : h(k) 에 저장

키 k 값을 가지는 원소가 위치 h(k)에 해시된다. h(k)는 키 k의 해시값이다.

• 키는 무조건 존재하며 중복된 키가 있어서는 안된다.
• 해시 테이블을 구성하는 key, value 데이터 각각의 저장 공간을 slot 또는 bucket 이라 한다.

Collision

collision ( 충돌 ):

서로 다른 키의 해시값이 같은 상황, 중복되는 key는 없지만 해시 값이 중복되어 같은 데이터를 가리키는 상황

해결

• 개방주소법(open addressing)
• 개별 체이닝(seperate chaining)

개방 주소법

인덱스 위치가 충돌한다면 정한 규칙에 따라 빈 슬롯을 찾을 때까지 검사

추가적인 메모리 공간이 필요 없고 테이블이 가득 차면 삽입이 어렵다.

- 선형 탐사 (linear prob)

인덱스 위치가 충돌한다면 빈 slot을 찾을 때까지 내려간다. 배열의 끝에 도달하면 다시 처음으로 돌아가서 빈 slot을 탐색 (wrapping around : 배열을 원형으로 생각해 탐색)

- 이차 탐사(Quadratic Probing):

충돌이 발생했을 때 현재 위치에서부터 일정한 간격을 이용하여 다음 위치를 찾는 방법

• 일반적으로는 이차식의 형태로 간격을 결정한다. 예를 들어, 다음 위치를 찾을 때는 현재 위치에서 1, 4, 9, 16, ... 만큼 이동하는 방식

• 이차 탐사는 선형 탐사와 달리 일정한 간격이 아니라 제곱 수의 간격을 이용하기 때문에 클러스터링(Clustering) 현상을 줄일 수 있다. 하지만 이차 탐사 역시 일정한 패턴을 가지고 이동하기 때문에 빈 슬롯을 찾는 데 어려움이 있을 수 있다.

- 이중 해싱(Double Hashing):

두 개의 해시 함수를 사용하여 충돌을 해결하는 방법

충돌이 발생했을 때 두 번째 해시 함수를 사용하여 다음 위치를 결정한다. 이때 두 번째 해시 함수는 키와 상관없이 일정한 범위 내에서 값을 반환해야 한다.

• 이중 해싱은 충돌된 위치에서부터 일정한 간격이 아닌 다른 위치로 이동하기 때문에 클러스터링 문제를 해결할 수 있다.
• 또한, 두 번째 해시 함수가 독립적으로 정의되기 때문에 일정한 패턴이 나타나지 않아 빈 슬롯을 더 쉽게 찾을 수 있다.

→ 하나의 해시함수는 최초의 해시값을 얻을 때 사용, 또 하나는 해시 충돌이 발생할 때 탐사 이동폭을 얻기 위해 사용

개별 체이닝

해시 테이블에서 충돌 발생 시 각 해시에 해당하는 slot에 linked list를 추가해 데이터를 저장, 추가적인 메모리 공간 사용

해시 테이블의 크기가 고정되어 있을 때에도 효율적으로 동작하며, 연결 리스트의 구현 방법에 따라 메모리 소비를 최적화할 수 있다.

충돌된 데이터들은 연결 리스트의 형태로 슬롯에 저장되고, 이를 통해 동일한 해시 값에 대한 다수의 데이터를 하나의 슬롯에 저장할 수 있다.

• 검색 : 데이터를 검색할 때는 해당 키의 해시 값을 계산하여 해당 슬롯의 연결 리스트를 탐색한다. 기본 시간복잡도는 O(1)이지만 최악의 경우 O(n)의 시간 복잡도를 갖는다.
• 삽입: 데이터를 삽입할 때도 마찬가지로 해당 슬롯의 연결 리스트에 노드를 추가해 (key, value) 데이터 쌍을 저장한다. 시간복잡도는 O(1)이다.
• 삭제: 삭제를 위해선 검색이 필요하기 때문에 검색과 같은 시간복잡도를 갖는다.

장점

• 공간 활용:

  개별 체이닝은 해시 테이블의 슬롯에 연결 리스트를 저장하기 때문에 슬롯이 가득 차도 추가적인 데이터를 저장할 수 있다.

• 평균적으로 개별 체이닝은 충돌을 효율적으로 해결할 수 있다. 검색 및 삽입 연산의 시간 복잡도는 O(1 + α)입니다. 여기서 α는 충돌된 데이터의 평균 개수를 의미

🎯 개별 체이닝은 기본적으로 linked list를 이용해 데이터를 저장하지만 충돌이 많이 발생해 연결 리스트의 길이가 길어지면 BST 자료구조로 데이터를 저장하기도 한다.

→ BST를 사용해 worst case의 시간복잡도를 O(n) → O(logn)으로 낮출 수 있다.

🧀 worst case의 시간 복잡도 O(n)

n개의 모든 키가 동일한 해시값을 가져 길이 n의 연결리스트가 생성되는 경우

특정 키를 찾기 위해서는 길이 n의 연결리스트를 검색하는 O(n)의 시간복잡도와 동일하게 된다.

이진 탐색 트리

• 특정 노드를 기준으로 왼쪽 서브트리에는 해당 노드보다 작은 값으로 이루어져 있고 오른쪽 서브트리는 해당 노드보다 큰 값으로 이루어져 있는 이진 트리(Binary Tree) 이다.

조건:

• 특정 노드 기준 왼쪽은 해당 노드보다 작은 값으로 이루어진다.
• 특정 노드 기준 오른쪽은 해당 노드보다 큰 값으로 이루어진다.

이진 트리(Binary Tree)

각 노드가 최대 2개의 자식을 가지는 트리 구조, 이진 트리에서 각 노드는 0~2개의 자식을 가질 수 있다.

이진 트리의 조건

• 각 노드가 0~2개의 자식 노드를 가진다.

  → 노드가 없는 빈 트리는 단순히 루트가 없는 상태로 정의되며, 이진 트리의 특성을 만족한다.

• 각 노드의 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분되고 두 자식이 이진 트리 이면 이진트리로 간주한다.

시간 복잡도

BST의 주요 연산은 삽입(Insertion), 삭제(Deletion), 검색(Search)으로

1. 삽입(Insertion):
   • BST에 새로운 값을 삽입하는 과정은 트리의 적절한 위치를 찾아서 삽입하는 것이다.
   • BST의 삽입은 새로운 값이 루트 노드에서 시작해 루트노드보다 크다면 오른쪽, 작다면 왼쪽으로 이동해 그 위치의 자식들과의 비교를 반복해 자리를 찾는다.
   • 리프 노드에 추가되는 과정으로 값이 삽입될 때마다 트리의 구조를 유지해야 한다.

→ 따라서 삽입 연산은 트리의 높이에 비례하여 시간이 소요된다. 모든 자식이 0~2개의 자식을 가지기 때문에 트리가 균형적으로 생성된 경우는 평균적으로 O(log n)의 시간 복잡도를 가진다.

• 최악의 경우는 트리가 편향되어 있는 경우이며, 이 때의 시간 복잡도는 O(n)이다. (n은 트리의 노드 수)

2. 삭제(Deletion):
   • BST에서 노드를 삭제하는 과정은 삭제할 노드의 자식 노드의 개수에 따라 경우를 나누어 처리해야 한다.
     1. 자식이 없을 때 : 해당 노드만 삭제
     2. 자식이 하나 있을 때 : 해당 노드를 삭제하고 자식을 원래 해당 노드 자리로 이동
     3. 자식이 두 개 있을 때 :
        • 왼쪽 subtree의 가장 큰 노드( 가장 오른쪽 노드) 나
        • 오른쪽 subtree의 가장 작은 노드( 가장 왼쪽 노드) 로 해당 노드를 삭제한 자리 대체
   • 삭제 연산 역시 트리의 구조를 변경하므로, 삭제 후에도 BST의 조건을 유지해야 한다.

→ 트리가 균형적으로 생성되어 있는 경우에는 평균적으로 O(log n)의 시간 복잡도를 가진다.

• 최악의 경우는 트리가 편향되어 있는 경우이며, 이 때의 시간 복잡도는 O(n)이다. (n은 트리의 노드 수)
  3. 검색(Search):
  • BST에서 특정 값을 검색하는 연산은 트리를 탐색하는 과정으로 BST의 특성에 따라 값을 찾기 위해서는 트리를 순회하며 비교를 해야 한다.
• BST의 검색 연산은 트리의 높이에 비례하여 시간이 소요된다. 트리가 균형적으로 생성되어 있는 경우에는 평균적으로 O(log n)의 시간 복잡도를 가진다.
• 최악의 경우는 트리가 편향되어 있는 경우이며, 이 때의 시간 복잡도는 O(n)이다. (n은 트리의 노드 수)

따라서 BST의 시간 복잡도는 주로 트리의 높이에 의해 결정되며, 트리의 균형을 유지함으로써 평균적으로 O(log n)의 시간 복잡도를 가진다. 하지만 트리의 편향이 심할 경우 최악의 경우에는 O(n)의 시간 복잡도를 가진다.

🧀 BST의 높이가 logn인 이유

BST의 높이가 O(log n)이 되는 이유는 각 노드에서의 분기가 이진으로 이루어지기 때문이다.

BST에서는 각 노드의 왼쪽 자식은 현재 노드보다 작은 값이고, 오른쪽 자식은 현재 노드보다 큰 값이 된다. 이진 탐색 트리의 특성 상, 어떤 노드를 탐색하려 할 때마다 탐색 대상이 현재 노드의 왼쪽 서브트리 또는 오른쪽 서브트리 중 하나로 줄어들게 된다.

따라서 BST의 높이는 탐색할 노드를 선택할 때마다 대략적으로 높이가 절반씩 줄어들게 되어 O(log n)의 시간복잡도를 가진다.

🧀 BST의 worst case

BST의 worst case는 트리의 균형이 깨져 한쪽으로 치우친 상태로 트리 구조가 아닌 linked list 와 유사한 구조를 이룬다.해결을 위해서는 자가 균형 이진 탐색 트리 알고리즘으로 이진 트리의 균형이 잘 맞도록 유지해 높이를 가능한 낮게 유지한다.

EX : AVL트리, Red-black 트리

레드블랙 트리(BST 트리의 일종)

1. 모든 노드는 블랙이나 레드이다.

2. root와 leave(NIL)노드는 블랙이다.

3. 노드가 레드라면 부모 노드는 블랙이다.(연속해서 2대가 레드일 수 없다.)

4. 임의의 노드 x로 부터 모든 가능한 leave까지 거리는 항상 같다.

   → 리프 노드에서 루트 노드까지 가는 경로에서 만나는 블랙 노드의 갯수는 같다. (자기 자신은 제외하고 계산)

레드블랙 트리의 시간복잡도 : O(logn)

구현(C++)

1202번 보석도둑 세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

문제 요약:

가방에 담을 수 있는 최대 무게를 넘기지 않고 보석을 담아서 보석 가격의 합의 최대 구하기

생각할 점:

• 가방에는 한 개의 보석만 넣을 수 있다.

• 보석 가격 합의 최대가 되려면?

  • 보석을 무게 기준 오름차순, 가방 제한 무게 벡터도 오름차순

  • 최대 무게가 작은 가방부터 하나씩 반복하면서

  • 가방에 들어갈 수 있는 보석들의 가치를 저장한 벡터 bag에 무게가 가방의 용량을 넘지 않는 보석들의 인덱스 저장

  • bag에 들어갈 수 있는 보석이 있다면 보석들의 가치를 기준으로 내림차순 정렬해서 가장 가치가 큰 것만 최대 가격을 반환할 답 answer에 추가하고 맨 앞의 가장 가격이 높은 보석 인덱스를 지워준다.

  • 그 다음 가방 반복

처음에는 우선순위 큐를 사용한다는 생각을 못해서 bag 벡터에 매번 가격 순으로 내림차순 정렬을 해서 가장 가격이 높은 보석을 찾는 방법을 사용했다. 하지만 우선순위 큐를 사용한다면 큐에 데이터를 넣을 때마다 알아서 내림차순 정렬로 가장 가격이 높은 순으로 정렬이 되기 때문에 시간 복잡도 측면에서 훨씬 개선할 수 있다. 우선순위 큐-C++

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;

    vector<pair<int,int>> jewel(N);
    for (int i = 0; i < N; i++) {
        //무게, 가치
        cin >> jewel[i].first >> jewel[i].second;
    }

    vector<int> capacity(K);
    for(int i = 0; i < K; i++){
        cin >> capacity[i];
    }

    sort(jewel.begin(), jewel.end());
    sort(capacity.begin(),capacity.end());

    long long answer = 0;
    int index= 0;
    priority_queue<int> bag;

    for (int i = 0; i < K; i++) {
        while (index < N && jewel[index].first <= capacity[i]) {
            bag.push(jewel[index].second);
            index++;
        }

         if(!bag.empty()){
            answer += bag.top();
            bag.pop();

        }

    }

    cout << answer << endl;
}

풀이

🌟 초기화

• 보석의 수 N, 가방의 수 K로 입력받아
• 보석의 수 만큼 보석의 무게와 가격을 쌍으로 입력받는 벡터 jewel
• 가방의 최대 무게를 입력받아 저장하는 벡터 capacity 를 생성한다.

int N, K;
    cin >> N >> K;

    vector<pair<int,int>> jewel(N);
    for (int i = 0; i < N; i++) {
        //무게, 가치
        cin >> jewel[i].first >> jewel[i].second;
    }

    vector<int> capacity(K);
    for(int i = 0; i < K; i++){
        cin >> capacity[i];
    }

🌟 정렬

• 보석들의 무게를 기준으로 오름차순 정렬하고
• 가방의 최대 무게를 기준으로 오름차순 정렬한다.

sort(jewel.begin(), jewel.end());
sort(capacity.begin(),capacity.end());

🌟 로직

• 가방에 들어갈 수 있는 보석들의 가격을 저장할 우선순위 큐 bag 생성
• 가방 하나마다 들어갈 수 있는 보석의 무게를 조건문으로 비교해 해당하는 인덱스의 보석의 가격을 bag 큐에 추가한다.
• 한 가방에 들어갈 수 있는 보석을 모두 찾아 가방이 비어있지 않다면 우선순위 큐의 가장 top의 값( 가장 가격이 높은 보석) 을 answer에 더해주고 큐에서 해당값을 삭제한다.

long long answer = 0;
    int index= 0;
    priority_queue<int> bag;

    for (int i = 0; i < K; i++) {
        while (index < N && jewel[index].first <= capacity[i]) {
            bag.push(jewel[index].second);
            index++;
        }

         if(!bag.empty()){
            answer += bag.top();
            bag.pop();

        }

    }

우선순위 큐(Priority Queue)는 각 요소에 우선순위가 할당된 큐 자료구조로 일반적으로 높은 우선순위를 가진 요소가 낮은 우선순위를 가진 요소보다 먼저 처리되는 큐이다. 우선순위 큐는 일반적인 큐와 달리 요소를 삽입할 때마다 요소의 우선순위를 기준으로 정렬되거나, 우선순위가 가장 높은 요소가 항상 먼저 나오도록 구현된다.

Q. ⭐️Queue와 priority Queue의 차이 비교

Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 구조로 저장하는 형식이다. 이와 달리 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 시간 복잡도:

• Queue: enqueue->O(1), dequeue->O(1)
• priority queue: push->O(logn), pop-> O(logn)

c++에서의 우선순위 큐

1. 큐 헤더파일

c++에서는 우선순위 큐 priority_queue를 queue헤더 파일에서 제공한다.

#include<queue>

2. 우선순위 큐 생성

priority_queue<T> pq;

queue를 생성하듯이 다음처럼 우선순위 큐를 생성할 수 있다. T에는 정수, char 등의 기본 자료형과 struct, class 등도 올 수 있다.

C++의 우선순위 큐는 기본적으로 Max heap 으로 설정되어 있다. -> 즉 Max heap에서는 큰 값이 우선 순위가 큰 것 처럼 우선순위 큐도 큰 값의 우선순위가 높은 것이 default 이다. 내림차순이 기본

반대로 Min heap의 형태로 우선순위 큐를 설정하려면

이제 반대로 Min Heap으로 동작하도록 설정하고 싶다면, greater<int>를 사용하면 된다. 그러면 작은 값이 우선순위가 높아져 오름차순으로 정렬된다.

정렬 기준을 임의로 바꿔야하는 경우 축약한 선언은 불가하며, 아래와 같이 필요한 값들을 전부 넣어서 선언해야 한다.

#include <queue>
#include <vector>

using namespace std;

int main() {
    // Min Heap으로 동작하는 우선순위 큐
    priority_queue<int, vector<int>, greater<int>> pq; // 작은 값이 우선순위가 높음

    pq.push(90);
    pq.push(70);
    pq.push(85);

    // 작은 값이 우선순위가 높으므로, 70이 가장 우선순위가 높음
    // 따라서 top() 메서드를 사용하면 70이 출력됨
    cout << pq.top() << endl; // 출력: 70

    return 0;
}

T에 pair을 넣는 경우

우선순위 큐에 pair가 들어가게 작성해야 할 경우가 있다면 다음과 같이 작성할 수 있다. T에 pair<int, int>를 작성

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // pair<int, int>가 들어가는 Max Heap 우선순위 큐
    priority_queue<pair<int, int>> maxHeap;

    // pair<int, int>에는 첫 번째 값이 우선순위가 된다
    // 따라서, (우선순위, 값) 형태로 pair를 넣어준다.

    // 시험 점수들을 pair로 묶어서 넣어봅시다.
    maxHeap.push({90, 1});
    maxHeap.push({70, 2});
    maxHeap.push({85, 3});

    // pair의 첫 번째 값이 우선순위이므로, (90, 1)이 가장 우선순위가 높음
    // 따라서 top() 메서드를 사용하면 (90, 1)이 출력됨
    cout << "(" << maxHeap.top().first << ", " << maxHeap.top().second << ")" << endl; // 출력: (90, 1)

    return 0;
}

우선순위 큐 기본 함수

데이터 추가 .push 큐이름.push(데이터) 로 데이터 추가

pq.push(2);

데이터 삭제 .pop 큐이름.pop(데이터) 로 데이터 삭제

pq.pop(2);

첫번째 데이터 반환 .front 큐이름.front() 로 큐의 첫번째 데이터 반환

pq.front();

마지막 데이터 반환 .back 큐이름.back() 로 큐의 마지막 데이터 반환

pq.back();

큐 사이즈 반환 .size 큐이름.size() 로 큐의 현재 사이즈 반환

pq.size();

비었는지 확인 .empty 큐이름.empty() 로 큐가 비어있는지 확인

pq.empty();

두 큐의 내용 바꾸기 .swap 큐이름.swap() 로 큐의 내용을 서로 바꿔준다.

pq.swap(queue1,queue2);

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

2
10
15

예제 출력 1

20

예제 1:

10kg, 15kg을 버티는 2개의 로프에 5,5 씩 중량 할당 가능 6, 6씩 중량 할당 가능…10,10 할당 가능, 11, 11부터는 할당이 불가 → 10,10이 가장 최대로 들 수 있는 중량 →20kg

문제 요약:

로프를 병렬로 연결했을 때, 각각의 로프에 모두 고르게 w/k의 중량이 걸릴 때, 최대로 들 수 있는 중량 구하기

최대로 들 수 있는 중량 : k개의 로프 중 버틸 수 있는 중량이 가장 작은 로프의 버틸 수 있는 중량 * k개 이다.

풀이 방법:

1. 로프의 갯수 N, 로프의 중량을 담은 벡터 rope 입력받기

2. 벡터 rope의 중량들을 오름차순 정렬

3. 정렬된 벡터에서 버틸 수 있는 무게가 가장 낮은 중량의 로프 i의 무게 rope[i] 와

   i 로프가 가장 낮은 중량인 로프의 개수 n-i를 곱해 최대값을 찾는다.

n - i : 인덱스는 0부터 시작이니까 자기보다 큰 용량의 로프 개수 + 자기 자신

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> rope(N);
    int answer = 0;

    // 로프의 무게 입력받기
    for(int i = 0; i < N; ++i) {
        cin >> rope[i];
    }
    //무게 오름차순 정렬
    sort(rope.begin(), rope.end()); 

    // 각 로프를 사용할 때의 최대 무게 계산
    for(int i = 0; i < N; ++i) {
        answer = max(answer, (N - i) * rope[i]); 
    }
    cout << answer << endl;

    return 0; 
}