GitHub ID : soohyun-dev
윤수현의 개발 공간
GitHub ID : soohyun-dev
전체 방문자
오늘
어제
  • 분류 전체보기 (918)
    • 성장기록 (49)
      • 성장기록 (3)
      • 우아한테크코스 (16)
      • 프로젝트 (15)
      • TIL (14)
      • 테오의 스프린트 (1)
    • 프로그래밍언어 (88)
      • C언어 (14)
      • HTML\CSS (12)
      • JavaScript (7)
      • React (23)
      • Python (11)
      • JAVA (14)
      • TypeScript (6)
    • 알고리즘 공부 (736)
      • 코드업 - 파이썬 (108)
      • 백준 - 파이썬 (468)
      • 백준 - 자바스크립트 (125)
      • 프로그래머스 - 파이썬 (1)
      • 프로그래머스 - 자바스크립트 (34)
    • 책 리뷰 (9)
      • 프로그래밍 (3)
      • 독서 (6)
    • 전자기기 (1)
    • 일상, 일기 (18)
    • 기술 세미나 (2)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 프로그래머스자바스크립트
  • PYTHON
  • 백준
  • 프로그래머스풀이
  • 파이썬
  • 백준풀이
  • 영어독해
  • 프로그래머스
  • javascript
  • 코드업파이썬
  • 백준파이썬
  • 코딩테스트
  • 자바스크립트
  • 코테
  • 코드업
  • 프론트엔드
  • 독해
  • 영어
  • 코딩
  • 프로그래밍언어

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
GitHub ID : soohyun-dev

윤수현의 개발 공간

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 2352 반도체 설계 [ LIS ]
알고리즘 공부/백준 - 자바스크립트

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 2352 반도체 설계 [ LIS ]

2022. 12. 10. 10:41

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 2352 반도체 설계 [ LIS ]

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

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

 

2352번: 반도체 설계

첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주

www.acmicpc.net

 

 

문제풀이 소감 🧑‍💻

LIS 문제이다. 가장 긴 증가하는 부분 수열 문제를 풀어봤다면 어렵지 않게 접근할 수 있을 것이다.

 

효과적으로 위치를 부여하기 위하여 이분탐색을 사용하였음.

 

문제를 처음 딱 봤을 때 어려워 보이지만 까보면 12738 가장 긴 증가하는 부분 수열 3 문제랑 똑같다. 쫄지말자.

 

 

해결 전략 📝

 

  • 문제는 장황하지만 결국 말하고자 하는 것은 엇갈리지 않는 선을 찾아내는 것.
  • 엇갈리지 않는다? => 증가하는 부분 수열을 찾으라는 것이다.
  • 2565 전깃줄 문제와도 굉장히 유사함.
  • 최대 연결 갯수를 찾으라 하였으므로 이 문제는 가장 긴 증가하는 부분 수열을 찾으라는 문제다.

 

 

두 가지로 나누어서 풀어주면 된다.

 

  • LIS 끝 값에 담긴 값보다 크다면 LIS에 그냥 넣어준다.
  • LIS 끝 값보다 작다면 내부로 들어와야 한다. => 이분탐색을 사용하여 어느 위치에 할당할 것인지 찾은 뒤 해당 인덱스에 숫자를 할당한다.
  • 최종 LIS의 길이를 출력.

 

 

 

 

정답 💯

 

 

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

const [input_N, input_portnumbers] = input.map((v) => v.split(" ").map(Number));

function solution(N, portnumbers) {
  const binarySearch = (target, left, right) => {
    while (left < right) {
      const mid = ~~((left + right) / 2);
      if (LIS[mid] < target) left = mid + 1;
      else right = mid;
    }

    return right;
  };

  const LIS = [];
  portnumbers.forEach((portnumber) => {
    if (LIS.length === 0 || LIS[LIS.length - 1] < portnumber)
      LIS.push(portnumber);
    else {
      const changePlace = binarySearch(portnumber, 0, N - 1);
      LIS[changePlace] = portnumber;
    }
  });

  return LIS.length;
}

console.log(solution(input_N, input_portnumbers));
반응형

'알고리즘 공부 > 백준 - 자바스크립트' 카테고리의 다른 글

백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1365 꼬인 전깃줄  (0) 2022.12.10
백준/ Platinum 5 문제 , 백준 Node.js 자바스크립트 14003 가장 긴 증가하는 부분 수열 5 [ 이분탐색, LIS ]  (0) 2022.12.10
백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 14002 가장 긴 증가하는 부분 수열 4 [ 이분 탐색, LIS ]  (0) 2022.12.09
백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 12738 가장 긴 증가하는 부분 수열 3 [ 이분 탐색, LIS ]  (0) 2022.12.08
백준/ Bronze 1 문제 , 백준 Node.js 자바스크립트 24051 알고리즘 수업 - 삽입 정렬 [ 정렬 ]  (0) 2022.12.07
    '알고리즘 공부/백준 - 자바스크립트' 카테고리의 다른 글
    • 백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 1365 꼬인 전깃줄
    • 백준/ Platinum 5 문제 , 백준 Node.js 자바스크립트 14003 가장 긴 증가하는 부분 수열 5 [ 이분탐색, LIS ]
    • 백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 14002 가장 긴 증가하는 부분 수열 4 [ 이분 탐색, LIS ]
    • 백준/ Gold 2 문제 , 백준 Node.js 자바스크립트 12738 가장 긴 증가하는 부분 수열 3 [ 이분 탐색, LIS ]
    GitHub ID : soohyun-dev
    GitHub ID : soohyun-dev
    환영합니다!😊 이곳은 저의 개발에 관한 내용들을 정리하는 공간입니다. 알고리즘 풀이에도 관심이 많아요. 좋은 하루 되세요~! github : soohyun_dev

    티스토리툴바