날마다 새로운 코딩

고정 헤더 영역

글 제목

메뉴 레이어

날마다 새로운 코딩

메뉴 리스트

  • 홈
  • 방명록
  • 전체 카테고리 (27)
    • Algorithm (27)
      • Tree (1)
      • Segment Tree (1)
      • Indexed Tree (2)
      • LCA (2)
      • Graph (1)
      • Union-Find (2)
      • Prim (3)
      • Kruskal (7)
      • Dijkstra (4)
      • Bellman-Ford (2)
      • LIS (2)
홈방명록
  • Algorithm 27
    • Tree 1
    • Segment Tree 1
    • Indexed Tree 2
    • LCA 2
    • Graph 1
    • Union-Find 2
    • Prim 3
    • Kruskal 7
    • Dijkstra 4
    • Bellman-Ford 2
    • LIS 2

검색 레이어

날마다 새로운 코딩

검색 영역

컨텐츠 검색

Algorithm/LIS

  • [백준][BOJ2565] 전깃줄

    2021.08.17 by bedamino

  • [백준][BOJ1965] 상자넣기

    2021.08.09 by bedamino

[백준][BOJ2565] 전깃줄

1. 문제 : https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 2. 풀이 : Binary Search 3. 설명 그림[1]과 같이 3개의 전깃줄을 제거하였을 때, 남아있는 모든 전깃줄이 교차하지 않음을 확인할 수 있다. 전봇대A를 기준으로 위치 1부터 10까지 차례대로 전깃줄을 연결하였을 때, 연결되는 전봇대 B의 위치 순서는 그림[2]와 같으며, 교차하지 않는 전깃줄은 최대 증가수열임을 알 수 있다. 마찬가지로, 전봇대 B를 기준으로 위치 1부터 ..

Algorithm/LIS 2021. 8. 17. 22:38

[백준][BOJ1965] 상자넣기

1. 문제 : https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 2. 풀이 : Binary Search 3. 시간복잡도 : O(NlogN) 4. 설명 최장 증가 수열(LIS, Longest Increasing Subsequence) 문제이다. 그림[1]과 같이 LIS를 저장할 배열을 만든다. 상자를 처음부터 하나씩 LIS 배열에 위치를 찾아 넣는다. 위치를 찾을때에는 이분탐색을 사용하며, 동일한 크기의 상자가 들어올 수도 있으므로 lower bound를 ..

Algorithm/LIS 2021. 8. 9. 20:46

추가 정보

최신글

페이징

이전
1
다음
TISTORY
날마다 새로운 코딩 © Magazine Lab
페이스북 트위터 인스타그램 유투브 메일

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.