욱이의 IT 생존일지

  • 홈
  • 태그
  • GitHub
  • Linkedin

공통 부분 문자열 1

[BOJ/5582/Golang] 백준 5582 - 공통 부분 문자열

접근 방식 이 문제는 직전 문제인 LCS (9251) 문제와 동일합니다. 다만 한 가지 더 출력해야 하는데요. 바로 찾은 LCS의 길이 뿐만 아니라, LCS 부분 수열 자체도 출력해야 합니다. 이 문제를 보고 처음 든 생각은, 아 뭔가 부모를 찾고 찾아서 거꾸로 이동하면서 출력하면 되겠구나.. 였습니다. 하지만 부모를 찾아갈 때 어떤 조건을 기준으로 이동할 것인지 생각하는 부분이 어려웠습니다. 중요한 점은 이전에 LCS의 길이가 증가할 때를 살펴보면, [i] == B[j]인 경우였습니다. 이 경우에 D[i][j] = D[i-1][j-1] + 1을 이용할 수 있었죠. 부분 수열 자체를 찾기 위한 꼬리에 꼬리를 무는 이동 조건도 이와 유사합니다. 이 전에 D[i-1][j] 또는 D[i][j-1]은 일치하지 ..

PS/BOJ 2021.05.21
1
더보기
프로필사진

Go언어와 Kubernetes를 좋아하는 엔지니어입니다. 꾸준히 배웁니다.

  • 전체 보기 (162)
    • PS (20)
      • BOJ (20)
    • IT (127)
      • Hadoop (1)
      • Airflow (7)
      • DevOps (6)
      • IT WIKI (25)
      • Network (16)
      • Kubernetes (18)
      • Docker (1)
      • containerd (2)
      • Istio (1)
      • Go (19)
      • OpenSource (1)
      • Python (5)
      • C++ (3)
      • OpenStack (6)
      • OS (10)
      • SQL (1)
      • Coding Tip (4)
    • 욱이야기 (7)
      • 욱이 취업 (1)
      • 욱이 (6)
    • Apple (7)
      • Mac (7)
      • iPhone & iPad & Acc (0)
    • 경제 공부 (1)
      • 부동산 공부 (1)

최근글

인기글

Tag

linux, go언어, Coding Test, 네트워크, k8s, 고, Go, 도커, Kubernetes, 컨테이너, 백준, docker, 고언어, 쿠버네티스, Network, 고랭, BOJ, 리눅스, Golang, Container,

최근댓글

Archives

Calendar

«   2025/05   »
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

방문자수Total

  • Today :
  • Yesterday :

Copyright © Kakao Corp. All rights reserved.

  • Wookiist GitHub
  • Wookiist Linkedin

티스토리툴바