[알고리즘] Leetcode Maximum subarray 파이썬 풀이

카테고리 : 알고리즘 리딩타임 : 1 분 페이지뷰 : --

문제 링크

https://leetcode.com/problems/maximum-subarray

풀이 방법

동적 프로그래밍 문제.

nums와 같은 값을 가지는 dp 배열을 생성한다.

이때, dp[i]의 의미는 nums[0]부터 nums[i] 까지의 subarray 중 최댓값이다.

nums[i] 원소에 대해 우리는 2가지 행동을 취할 수 있다.

  1. nums[i-1] 원소와 nums[i] 원소를 더 하는 것

  2. nums[i]를 시작으로 새로운 subarray를 시작하는 것

이걸 그대로 점화식으로 나타낸다면

1
dp[i] = max(dp[i-1]+nums[i], nums[i])

가 된다.

모든 루프를 끝내면,

dp 배열 중 가장 큰 값을 리턴.

코드

1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
  def maxSubArray(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    dp = [num for num in nums]
    for i in range(1, len(nums)):
      dp[i] = max(dp[i-1]+nums[i], nums[i])

    return max(dp)

댓글 공유

[알고리즘] Leetcode best time to buy and sell stock 파이썬 풀이

카테고리 : 알고리즘 리딩타임 : 1 분 페이지뷰 : --

문제 링크

https://leetcode.com/problems/best-time-to-buy-and-sell-stock

풀이 방법

가장 싼 가격(min_price)와 답이 되는 가장 비싼 이익(max_profit)을 선언해놓고

prices 배열을 돌면서 모든 price를 조사할건데,

min_price는 계속 가장 싼 가격으로 업데이트 되고

max_profit은 현재 price에서 min_price를 파는 값과 기존 max_profit 중 최대값을 업데이트 한다.

모든 가격을 조사한뒤 max_profit을 리턴.

루프가 첫 원소부터 돌고 가장 싼 가격이 업데이트 되고 그 가장 싼 가격에서 현재 가격에 팔면 얼마나 이득인지 계산하므로

팔고 사는게 아닌, 사고 파는 순서가 보장된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
  def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    max_profit = 0
    min_price = float('inf')
    for price in prices:
      min_price = min(price, min_price)
      profit = price - min_price
      max_profit = max(profit, max_profit)

    return max_profit

댓글 공유

[책] 플랫폼 제국의 미래

카테고리 : 리뷰 리딩타임 : 2 분 페이지뷰 : --

플랫폼 제국의 미래

  • 아마존의 제프베조스 또한 모든 시민이 빈곤층으로 전락하지 않도록 충분한 현금을 미급해주는 마이너스 소득세 방안도 제안. 기본소득을 주장.
    제프 베조스가 최저소득 제도를 주장하는 이유는 그가 미래의 작업 환경이 어떻게 바뀔지 이미 보았기 때문이다.
    아마존은 자사의 핵심 역량인 로봇 얘기를 공개적으로 하지 않는다. 정치인들에게 원성을 들을 거라는 사실을 알기 때문이다.
    기업가는 일자리를 창출한다고? 아니다. 그들은 일자리를 창출하지 않는다.

  • 20세기 가장 큰 부자는 직원에게 최소 임금을 주며 자기 물건을 팔게 하는 데 통달한 사람이었지만, 21세기 가장 큰 부자는 임금을 한 푼도 주지 않아도 알아서 물건을 팔아주는 로봇에 통달한 사람이다.

  • 아이폰은 사치품. 사치품은 비합리적이고 성적이며 뇌의 이성적 신호를 쉽게 압도해버린다. 예컨대 전 세계 400대 부자 중에는 기술 부문이나 다른 산업 부문보다 사치품과 소매유통업 부문에서 부를 축적한 사람이 더 많다. 사람들은 부자가 어떤 사람인지 보다 이들의 회사에 더 큰 관심을 보인다.(자라/로레알/H&M/루이비통 등) -> 부와 권력을 많이 소유한 사람은 주택, 난방, 음식, 섹스 파트너에 상대적으로 쉽게 접근할 수 있다. 이러한 점을 노린 것이 애플의 프리미엄 정책.
    저자가 25년동안 사치품 브랜드 업체를 상대로 컨설팅을 한 경험으로 이들 회사에는 공통적으로 핵심적인 다섯 개 특성이 있음을 발견했다.

1. 우상화된 창업자 - 죽음은 신비로운 힘을 발휘한다. 우상화된 인물이 일상적인 삶으로 인해 필연적으로 받을 이런저런 판단을 면하게 해주고 평범할 수 있던 한 개인을 전설의 반열에 올려놓는다. 죽음은 명성을 완전히 파괴하는 어리석은 행동과 노화로부터 우상화한 영웅을 보호해준다. 우상화된 창업자가 현실에서 괴짜였는지 어쨌는지는 중요하지 않다. 그것은 애플이 증명한다. 스티브 잡스의 사망 이후 애플은 한층 더 성장했다.
2. 장인정신 - 애플이 적용한 사치품의 본질은 단순성, 즉 궁극적 세련미에 있다. 애플 제품은 아주 단순하고 조리 있고 꼭 필요한 것으로 보여 이성적으로 다른 대안을 떠올릴 수 없다. 인지심리학에선 매력적인 사물이 사람을 기분 좋게 만들고 창의적인 도전을 하도록 자극하며 보다 더 강한 회복탄력성을 보장해준다고 설명한다.
3. 수직적 통합 - 애플의 성공을 결정지은 것은 아이폰이 아니라 애플의 브랜드 가치를 보여주며 정교하게 설계된 애플 매장이었다.
4. 세계 무대로의 확산
5. 프리미엄 가격 - 애플은 기술브랜드에서 사치품브랜드로 전환. 애플은 이 책이 설명하는 다른 기업(아마존, 페이스북, 구글)들 보다 저자가 볼 때 22세기까지 살아남을 가능성이 가장 높다. 적어도 현재까지 넷 가운데 창업자와 창업 당시 경영진이 모두 물러난 뒤에도 살아남은 유일한 기업이다.

  • 말콤 글래드웰은 <다윗과 골리앗>에서 ‘상대방이 설정한 조건 아래서 싸우지 마라’라는 핵심을 지적하며 터무니 없을 정도로 커다란 성공을 거두는 기업의 전략을 말함. 승리를 장기적으로 지속하는 관건은 해자를 보다 깊이 파는 데 있다. 여기서 깊은 해자란 파는 데 돈과 시간이 많이 드는(경쟁자의 입장에서) 진입장벽을 말한다.

  • 페이스북은 다른 어떤 기업보다 빠르게 성장하고 있는데 그 이유는 우리가 갈망하는 것이 페이스북에 있기 때문이다. 특히 페이스북의 인스타그램은 온갖 생각을 낳고 온갖 욕망을 일으킨다. 다시 말해 구글은 ‘어떻게’ 가질 수 있는지 방법을 제시하고 아마존은 ‘언제’ 배송을 받는지 제시하지만, 페이스북은 당신이 갖고 싶어 할 그 ‘무엇’을 제시한다.

  • 나이키 신발은 신을수록 그 가치가 점점 줄어들지만 나이키 신발을 신고 있는 사진을 페이스북에 올리면 올릴수록 페이스북의 가치는 점점 커진다. 사용자는 페이스북이라는 네트워크를 더 강력하게 만들어 그 플랫폼이 수행하는 사업의 핵심(데이터 처리 및 반복)을 현금화 한다. 저자는 이런 기업을 두고 ‘벤저민 버튼’같은 기업에 취직하고 투자하라고 한다. 어떤 사람의 150개의 ‘좋아요’를 분석하면 그 사람의 배우자보다 그 사람에 대해 더 알 수 있고 300개를 분석하면 그 사람 자신보다 그 사람에 대해 더 알 수 있다고 한다. 이러한 차이점이 트위터와 페이스북의 가치가 벌어지는 이유이다.

  • 인간은 글보다 이미지를 6만배 더 빨리 받아들인다.

  • 사람들은 애플을 세상에서 가장 혁신적인 회사, 아마존은 가장 평판이 좋은 회사, 페이스북은 가장 일하기 좋은 회사라고 생각하지만 구글에 주는 신뢰는 다른 거인기업들이 받는 신뢰와 견줄 수 없을 정도로 크다. 오늘날 구글이 현대적인 신으로 추앙받는 이유 중 하나는 구글이 우리의 가장 깊숙한 비밀을 알고 있기 때문이다. 구글에 질문할 때 우리는 성직자나 어머니, 가장 친한 친구 혹은 의사에게도 선뜻 말하지 못 하는 것까지 스스럼없이 털어놓는다. 구글에 하는 질문 중 6개 가운데 1개는 질문자가 다른 누구에게도 하지 않은 질문이다.

  • 벤 호로위츠, 피터 틸, 에릭 슈미트, 살림 이스마일 등 많은 사람들이 사업적 성공에 필요한 점으로 클라우드 컴퓨팅(자신의 컴퓨터가 아니라 인터넷으로 연결된 다른 컴퓨터로 정보를 처리)과, 가상화, 경쟁자를 압도하도록 10배의 생산성을 달성하게 해주는 네트워크 효과 등으로 이루어진 저비용 구조를 꼽는다. 그런데 이런 설명은 기술과 아무 관련이 없는 보다 깊은 차원의 어떤 측면을 무시하는 처사다. 진화심리학 관점에서 볼 때 성공한 모든 사업은 뇌, 심장, 생식기라는 신체의 세 부위 가운데 적어도 하나에 반드시 자신의 매력을 호소한다.

  • 예외적인 존재가 되기에 지금보다 더 좋은 때는 없다. 그와 동시에 평균적인 존재가 되기에 지금보다 더 나쁜 때는 없다. 예를 들어 요즘은 링크드인을 통해 전 세계의 인재들이 무한 경쟁할 수 있다. 재능이 특출한 사람은 전 세계의 수천 개 기업이 붙잡으려 안달하지만 그럭저럭 괜찮은 정도의 인재는 다른 그럭저럭 괜찮은 전 세계 수천만명의 인재와 경쟁해야 하므로 임금이 제자리걸음을 하거나 하락한다.

그렇다면 위대함을 타고나지 않았을 때는 어떻게 행동하는 것이 좋을까? 저자는 다음과 같은 항목을 제시한다.
변화에 적응하라.
대학에 가라.
도시로 거점을 옮겨라.
자기 경력을 알려라.
첨단 기술 게임에 동참하라.(=사회 변화를 무시하지 말고 나이가 먹더라도 따라가야 한다. 특히 기술분야)
자신의 지분을 늘려라.(일을 할 때 월급만으로 보상받지 않고 회사의 지분까지 요구)
좋은 조건을 찾아 옮겨 다녀라.(=이직)
조직이 아니라 사람에게 충성하라.
기업계에서 정의를 찾지 마라.
자신이 눈에 띌 수 있는 곳으로 가라.(회사에서 핵심 기능이 무엇인지 파악해 그 부서를 지향해야 한다)
운동하라.(=회사에서 신체적/정신적 힘을 과시. 스트레스받는 상황에서도 평점심을 유지)
도움을 구하고 도움을 줘라.
워라밸이라는 헛된 신화를 믿지 마라.(모든 일은 재능을 우선해야하지만 대개 얼마나 끈기를 많이 발휘하느냐에 달려 있다)

댓글 공유

[책] 재능은 어떻게 단련되는가

카테고리 : 리뷰 리딩타임 : 2 분 페이지뷰 : --

재능은 어떻게 단련되는가

  • 신중하게 계획된 연습은 특별히 개선해야 할 필요가 있는 특정 부분을 찾아내 그 부분만 집중적으로 훈련하는 것이다.

  • 노엘 터치(미시간 경영대학원 교수) - Comfort Zone, Learning Zone, Panic Zone
    Comfort Zone에서는 실력이 늘지 않고 Panic Zone에서는 너무 어려워 접근 방법조차 알지 못 한다.
    Leaning Zone을 제대로 파악하는게 중요!(칙센트미하이가 말한 몰입의 영역과 비슷하다)

  • 바이올린 협주곡을 연주할 때 제대로 연주했는지 아닌지 당신이 어떻게 알겠는가?

  • 피드백을 받을 수 있는 교사,코치,멘토의 존재가 반드시 필요하다.

  • 사람들은 대개 특정 활동을 계속해서 반복하는 것을 두고 연습이라고 하지만 그런 연습은 그다지 효과적이지 않다.
    무심코 하는 연습보단 오래 하기 힘들 정도의 집중이 필요한 연습을 해야한다.
    뛰어난 운동선수들조차 연습 시간을 제한하는 것이 집중력을 유지하는 비결이라고 밝혔다.

  • 잘하는 법을 이미 알면서 무언가를 하는 것은 즐겁다. 하지만 신중하게 계획된 연습은 그와 정반대의 것을 추구한다(지루하다). 연습이 끝난 다음에는 타인의 피드백을 통해 아직 미흡한 부분이 어디인지 정확히 찾아내야하고 가장 고통스럽고 힘든 부분을 반복해야한다. 우리를 위대함의 길로 인도하는 길이 쉽고 재밌다면 누가 그 길을 마다하겠는가? 사람들이 대부분 그런 연습을 하지 않기 때문에 당신은 그만큼 차별화된 존재가 된다.

  • 신중하게 계획된 연습만 하는 것이 재능을 단련시키는 데에 전부인가?
    아니다. 개인의 신체적 변화나, 주변 환경, 그 연습이 얼마나 훌륭하게 설게되었는가 등을 배제하지 않을 수 없다.

  • 연습은 반사적으로 잘하는 것이 아니다. 흔히 사람들은 위대한 성과자들이 아주 오랫동안 연습해 왔고 같은 일을 수없이 반복해 왔으니까 그 일을 반사적으로 할 수 있다고 생각한다. 하지만 사실 그들이 연습을 통해 습득한 것은 반사적으로 하지 않는 능력이다. 그들은 자동장치가 작동해 발전을 멈춘 상태가 되지 않도록 스스로 노력한다. 편안함과 거리가 먼 일을 지속적으로 수행한다. 그것이 바로 그들이 자기 분야에서 오랫동안 최정상의 자리를 지키는 방법이다.

  • 연습은 다른 사람들보다 더 많이 인식하고, 더 많이 배우고, 더 많이 기억할 수 있게 해준다. 그리고 그것이 결국 개인의 한계를 넘도록 해준다. 신중하게 계획된 연습으로 여러 해를 보내면 실제로 몸과 뇌가 변한다. 이것이 위대한 성과자가 우리와 근본적으로 다른 존재처럼 보이게 만드는 이유이다.->’미엘린’이라는 물질이 생성된다.

실생활에서의 연습 방법

음악 모델

프레젠테이션:준비한 발표문을 분석하고 각 부분마다 가장 강력하게 전달해야 할 핵심 느낌을 결정하고 반복적으로 연습하되 녹화한 영상을 보면서 피드백을 받아 그 느낌을 더 효과적으로 낼 수 있도록 연습.

체스 모델

수 많은 케이스 스터디를 하면서 나라면 어떻게 할 것인지 연습.

스포츠 모델

스포츠 선수들이 기본적인 체력에 집중하는 것처럼 일상 생활에서도 해당하는 능력이 요구하는 기초적인 부분에 있어 녹슬지 않게 주기적으로 연습(기초 수학/회계/과학 등 예전에 이미 봤던 교재를 보며 기본적인 기술을 다시 살펴보기)
메타인지를 통해 자신이 무엇을 알고 모르는지 인식

  • 사후 평가를 통해 무엇을 못 했고 잘 했는지, 개선되어야할 부분은 무엇인지 평가.
  • 큰 그림 그리기 - 하버드 경영대학원의 마이클 포터 교수는 기업에 자문을 할 때 해당 기업과 그 관련 산업을 철저히 연구하면서 준비한다. 도서관에서 20시간 정도 집중해서 파고들면 그 분야에 대해 CEO보다 훨씬 많은 것을 알게 된다고 한다. 이 때 중요한 것이 큰 그림을 그리면서 해당 분야가 하나의 시스템으로 어떻게 작동하는지 사고 모형을 구축하는 것.

기업에서의 적용 사례

  • 직원은 일만 하는 것이 아니라 능력을 키우고 성장한다는 사실을 이해

  • 최고의 기업이 직원에게 업무를 배분하는 방식은 운동 코치가 선수에게, 음악 교사가 제자에게 연습할 내용을 정해 주는 방식과 매우 흡사하다. 즉 현재 능력의 범위를 넘어설 수 있도록 가장 중요한 기술을 단련시킨다,

  • 권위가 아닌 영감을 통한 인재 양성이 가장 효과적임을 이해

  • 신중하게 계획된 연습은 굉장히 힘든 과정이기 때문에 강력한 동기부여 없이는 누구도 오래 버티지 못 한다. 저성과자에 대해 해고나 강등 등 부정적인 유인으로 관리하는 것은 비효율적이다.

  • 캘리포니아 주립대학의 제임스 코프먼은 혁신은 모두 동일한 발달 과정의 연속선상에 있으며 참신하고 개인적으로 유의미한 해석(mini-c)에서 출발해 개인들 상호간에 의미있는 것으로 인정하는 단계(little-c)를 지나 훌륭한 창의적 성과(big-c)로 나아가는 궤도로 따른다고 한다. 이는 창조성이라는 부분도 타고나는 것이 아닌 신중하게 계획된 연습을 통해서 계발할 수 있다는 걸 뜻한다. 창조는 우리가 흔히 생각하는 것보다 훨씬 더 의시적인 노력에 가깝고 어떤 분야에서 최고가 되기를 갈망하고, 그러기 위해 열심히 노력하며, 혁신을 지향하는 것으로 이루어진다.

  • 창의적인 사람들은 자기 자신(이 문제를 해결하는 것이 나에게 이익이 될까?)이 아니라 과업(이 문제를 어떻게 하면 해결할 수 있을까?)에 초점을 맞추었다.

  • 열정은 타고나는 것이 아니라 개발이 가능하다. 어느 분야이건 세계적 수준의 대가들에게는 더 나아지려는 열정이 있지만, 그들 대다수도 처음부터 그랬던 것은 아니다. 어릴때부터 연습을 시작하는 음악이나 스포츠 등의 분야에서 아이들에게는 일정량의 강요가 불가피하다는 사실이 그것이다. 관련 지식을 습득하는 데만 몇 년이 걸리는 특정 분야에서 장차 최고의 자리에 서게 될 사람들도 젊은 시절엔 자기 길을 분명하게 정하지 못한 경우가 흔했다.

댓글 공유

[컴퓨터구성] 3주차

리딩타임 : 1 분 페이지뷰 : --

조합논리회로 (Combinational Circuits)

  • 입력에 의해 출력이 결정

Half Adder

  • 2개의 비트를 산술연산
    S = x xor y = x’y + xy’
    C = xy
  • 진리표

Full Adder

  • 3개의 비트를 산술연산
    S = x xor y xor z = x’y’z + x’yz’ + xy’z’ + xyz
    C = xy + xz + yz

  • 진리표

순서논리회로 (Sequential Circuits)

  • 피드백(Feedback)을 가진 조합회로로 구성
  • 입력 값과 현재 기억 상태에 따라 출력이 결정

Flip-Flop

  • 1비트를 기억하는 소자
  • clock pulse generator에 의해 synchronization이 일어남
  • 래치라고도 함

SR Flip-Flop

  • R(Reset)과 S(Set) 두 입력을 받아서 Q(현재 상태)와 Q’(다음 상태)의 2가지 출력을 가진다
  • 진리표
  • 특성표

D Flip-Flop

  • 특성표

JK Flip-Flop

  • RS 플립플롭보다 많이 쓰이는 플립플롭(RS플립플롭의 문제점 보완)
  • 진리표
  • 특성표

Level-triggering vs Edge-triggering

  • 클락이 올라갈 때 positie
  • 클락이 내려갈 때 negative

Excitation table

  • 플립플롭에서 현 상태와 다음 상태를 알 때 플립플롭에 어떤 입력을 넣어야 하는가를 나타냄
  • RS 플립플롭의 excitation table
  • JK 플립플롭의 excitation table
  • D 플립플롭의 excitation table

댓글 공유

[알고리즘] 프로그래머스 불량 사용자 파이썬 풀이

리딩타임 : 3 분 페이지뷰 : --

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/64064

풀이 방법

먼저 banned_id를 기준으로 user_id를 하나씩 돌면서

  • 서로 글자수가 같고,
  • *를 제외한 모든 글자가 서로 똑같은 user_id를 찾는다.

그걸 candidates 리스트로 넘겨준다. 그러면 각 banned_id가 가질 수 있는 후보 리스트가 완성이 된다.

이제 candidates의 각 리스트를 돌면서 dfs로 모든 경우의 수를 따져주면 된다.

dfs의 파라미터로

앞으로 탐색해야할 banned_id에 해당하는 user_id 리스트 candidates,

선택하지 않은 user_id 리스트 users,

이번 경우의 수가 담긴 result,

최종 결과가 들어갈 세트 results가 들어간다.

중간에 기존에 있던 레퍼런스들이 아닌 deepcopy를 이용해 기존 내용이 똑같이 담긴 새로운 리스트들이 생성되는데

그렇게 하지 않으면 재귀를 이용한 백트랙킹이 안되기 때문이다.

이해가 되지 않는다면 예를 들어보자.

입력값이 user_id: ["frodo", "fradi", "crodo", "abc123", "frodoc"], banned_id: ["*rodo", "*rodo", "******"]로 주어졌을 때 (입출력 예시2번)

candidates는 [['frodo', 'crodo'], ['frodo', 'crodo'], ['abc123', 'frodoc']] 로 나오게 된다.

['frodo', 'crodo'] 이 리스트가 2번 들어간 이유는 banned_id에 "*rodo" 이 조건이 2번 들어가있기 때문에 중복처리를 해주지 않고 들어가 있기 때문이다.

이제 dfs 함수로 들어가 ['frodo', 'crodo'] 이 아이템부터 경우의 수를 따져본다.

여기서 frodo를 선택한다면 다음 아이템에선 frodo 또는 crodo,

다음 아이템에선 abc123 또는 frodoc을 선택할 수 있다.

반대로 여기서 crodo를 선택한다면 똑같이 다음 아이템에선 frodo 또는 crodo,

다음 아이템에선 abc123 또는 frodoc을 선택할 수 있다.

결국 results값으로

['frodo', 'crodo', 'abc123']

['crodo', 'frodo', 'abc123']

['frodo', 'crodo', 'frodoc']

['frodo', 'crodo', 'frodoc']

이 4 가지 경우가 나올 수 있다.

하지만 문제 조건에 나와있듯이 원소의 순서에 상관없이 리스트에 담긴 원소가 같다면 동일한 경우로 생각하기 때문에

중복된 부분을 제거해주어야 한다.

세트를 통해서 중복을 없앨 수 있고 그러기 위해선 중복된 케이스가 같은 원소여야 한다.

하지만

['frodo', 'crodo', 'abc123']

['crodo', 'frodo', 'abc123']

이 케이스를 세트에 넣어준다면 다른 원소로 인식이 될 것이다. (애초에 리스트는 세트에 삽입하지 못 하지만..)

같은 원소로 인식하기 위해서 dfs의 base case로 해당 스택까지 트랙킹해온 result배열을 정렬해 준다.

그리고 리스트를 튜플에 넣는다면 hashable하지 않기 때문에 리스트를 튜플로 바꿔준다. (원소의 순서 고정)

1
['frodo', 'crodo', 'abc123'] => {'crodo', 'frodo', 'abc123'}로 변한됨

마지막으로 세트로 선언된 results에 넣어주면

['frodo', 'crodo', 'abc123']

['crodo', 'frodo', 'abc123']

와 같은 케이스는 중복처리 되어 하나만 남게된다.

최종적으로 results가 가지고 있는 각 경우의 집합?의 갯수를 세어주면 된다.

코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
import copy

def dfs(candidates, users, result, results):
  if not candidates:
    results.add(tuple(sorted(result)))
    return

  new_candidates = copy.deepcopy(candidates)
  curr = new_candidates.pop()
  for item in curr:
    if item in users:
      new_result = copy.deepcopy(result)
      new_result.append(item)
      new_users = copy.deepcopy(users)
      new_users.remove(item)

      dfs(new_candidates, new_users, new_result, results)


def solution(user_id, banned_id):
  candidates = []

  for bid in banned_id:
    temp = []
    for uid in user_id:
      found=True
      if len(bid) != len(uid):
        continue
      for i in range(len(bid)):
        if bid[i] == "*" or bid[i] == uid[i]:
            continue
        else:
            found=False
            break

      if found:
        temp.append(uid)

    candidates.append(temp)

  results = set()
  dfs(candidates, user_id, [], results)

  return len(results)

배운 점

파이썬의 함수 인자 전달 방식은 call-by-object-reference이다.

mutable한 타입은 call-by-value로,

immutable한 타입은 call-by-reference로 함수의 인자가 전달된다.

나는 다른 언어를 쓰던 습관이 남아있어 call-by-value인 줄 알고

dfs를 할 때 인자로 넘겨준 값이 예상한 값과 다른 값이 나왔다.

copy 모듈을 이용해 deepcopy를 해서 레퍼런스가 아닌 새로운 객체가 넘겨지도록 바꾸어주었다.

++ 이러한 방식이 백트랙킹 임을 깨닫게 되었다!!!

++ 세트에 리스트를 넣을때는 튜플로 변환해서 넣어줄 수 있다는 것을 알았다.

댓글 공유

[알고리즘] 프로그래머스 튜플 파이썬 풀이

카테고리 : 알고리즘 리딩타임 : 1 분 페이지뷰 : --

문제 링크

풀이 방법

문자열 파싱을 할 줄 안다면 쉬운 문제이다.

먼저 문제에 주어진 입출력 예시를 보면,

각 {}로 나뉘어진 집합별로 나눈 다음에 집합 안의 숫자들을

배열에 순서를 지켜가면서 넣어주면 된다.

이 때, 각 집합을 길이 오름차순으로 나열한 다음 중복을 체크해주어야 한다.

코드

1
2
3
4
5
6
7
8
9
10
11
def solution(s):
    answer = []
    string = s[1:len(s)-1].replace('},', '}-').split("-")
    string = sorted([item[1:len(item)-1] for item in string], key=lambda item: len(item))

    for item in string:
        for digit in item.split(","):
            if int(digit) not in answer:
                answer.append(int(digit))

    return answer

댓글 공유

[운영체제] 3주차 IO Structure and Interrupts (1)

카테고리 : 운영체제 리딩타임 : 3 분 페이지뷰 : --

Modern Computer Systems

  • Consists of CPUs, Main Memory, other devices
  • Connected by a bus to access Main Memory
  • CPU and devices(controllers) execute simultaneosly and compete for shared memory
  • Memory controller unit(MMU) ensures these orders

Basic Understanding

  • OS(image) is stored in HDD(SSD)
  • When power is off, MM is empty(volatile) => so, when power is on, CPU can do nothing
  • Thus, to start computer, OS image must be loaded into MM

Bootstrap program

  • 하드웨어 제조사에서 개발
  • First program to run when power is on
  • Stored in Boot-ROM
  • Initializes computer system hardware (OS가 초기화 하지 않는 이유? 하드웨어는 제조사별로 다양하기 때문에 OS가 일괄적으로 초기화 불가능)
  • Loads OS from HDD(SSD) to first location of MM (addr = 0 or predefined)

What does CPU do?

  • Fetch Instr.=> Decode => Fetch Data => Execute => Store

Fetch Instrunction

AR <- PC & IR <- M[AR] & PC++

OS Booting

  • CPU simply fetch, decode, execute, store each line of OS image
  • Activates scheduler(=swapper)(pid=0), first process init()(pid=1)
  • Waits for interrupts to occur
  • Hardware interrupts: signals CPU by bus
  • Software interrupts: signals by sys calls(traps)
  • Modern OSs are interrupt-driven
  • Why interrupts necessary? : OS가 효율적으로 작동하기 위해
  • When interrupts necessary? : CPU가 요청한 operation을 I/O controller가 다 끝냈을 때

Memory Mapped I/O

Case1: CPU가 Memory Mapped I/O를 직접 수행

  • 키보드를 예시로 들면,

  • 키보드 컨트롤 레지스터로 보내기 위해 AC에 1을 저장

  • AC로부터 키보드 컨트롤 레지스터에게 1을 보냄 (CPU가 키보드에게 유저로부터 character를 받기 시작한다고 말해주는 것)

  • CPU가 키보드 컨트롤 레지스터로부터 내용을 읽어들임

MSB=1이면, 유저가 입력한 character가 데이터 레지스터로 입력되고 데이터 레지스터로부터 데이터를 읽어들임
MSB=0이면, 유저로부터 입력받은 character가 없음

Device contorllers

  • CPU로부터 명령을 받아 IO를 수행하고 상태를 유지
  • IO logic, Buffer(data register), status register로 구성
  • device controller의 operation이 끝나면 status register를 1로 세팅해 IO의 완료를 알림(interrupt)

I/O의 종류

Synchronous I/O

  • Control is returned to user process only at completion of I/O
  • 한 번에 한 개의 인터럽트밖에 수행하지 못 함

Asynchronous I/O

  • 현대 OS에 쓰임
  • Control is returned to another user process without waiting completion of I/O that it requested.
  • Multiple I/O may exist by multiple process(multiple interrupts may take place)

Interrupt servicing procedure

IRQ adressing

  1. 인터럽트 signal이 CPU에 도착

  2. OS가 리턴 어드레스를 저장 (push(stk_ptr, PC))

  3. CPU가 도착한 인터럽트 타입을 조사

3-1) Polling

  • 모든 device는 서로 같은 signal을 보냄
  • CPU가 모든 device를 조사

3-2) Vectored Interrupt

  • 모든 인터럽트는 unique id가 부여(IRQ n)

  • device마다 서로 다른 signal을 보냄

  • signal이 도착하면 CPU는 인터럽트 벡터를 확인해 interrupt service routine(ISR)의 시작 주소를 얻음.

  1. ISR 실행 (PC = some_address)

  2. 인터럽트 서비스가 끝나면 CPU는 다시 바로 전의 프로세스로 돌아감 (PC = pop(stk_ptr))

Multiple IO Management

  • OS는 DST(Device-Status Table)라는 것을 유지
  • 이 테이블 안에는 여러 device의 상태정보를 저장
  • DST pointer 사용

DMA structure

  • CPU는 MM<-> Buffer in device controller간 데이터를 이동시키기엔 너무 아까움

  • MM은 CPU가 주로 쓴다

  • MM은 1 word씩 전송하므로 다른 장치들이 MM을 사용할 경우, CPU의 동작에 큰 영향

  • DMA controller는 CPU를 쓰지 않고 직접 MM과 Buffer에 접근해 데이터를 전송

  • CPU가 메모리를 쓰지 않을때 Cycle Stealing해 메모리에 접근하고 접근이 완료됐을 때 interrupt를 일으켜 작업완료를 알림

Disk Read operation summary

1-유저 CPU가 유저 프로세스 a를 실행하는 도중 IO instruction을 보면 IO가 일어남

컨텍스트 스위치가 일어남

2-커널 CPU가 device controller에 있는 레지스터를 로드하기 위해 OS 프로세스 A를 실행시킴

3-커널 CPU가 DST(device-status table)을 조정하기 위해 OS 프로세스 B를 실행시킴

컨텍스트 스위치가 일어남

4-유저 CPU가 새로운 유저 프로세스 b를 실행시켰다고 하면

5-디바이스 device controller가 레지스터를 decode하고 어떤 명령이 필요한지 인식

6-디바이스 device controller가 512 바이트를 디스크에서 local buffer로 이동

7-디바이스 device controller가 CPU에게 인터럽트 시그널을 보냄

8-유저 CPU는 유저 프로세스 b가 인터럽트된 것을 인식

컨텍스트 스위치가 일어남

9-커널 CPU가 어떤 인터럽트인지 조사하기 위해 OS 프로세스 C를 실행시킴

10-커널 CPU가 ISR(interrupt service routine)를 실행하기 위해 OS 프로세스 D를 실행시킴

ISR이 끝나면 DMA가 실행됌
컨텍스트 스위치가 일어남

11-유저 CPU는 8번에서 인터럽트된 유저 프로세스 b를 다시 실행시킴

DMA는 CPU와 무관하게 실행되고 있다가 512 바이트가 controller buffer에서 MM으로 옮겨지면 CPU에게 인터럽트 시그널을 보냄

12-유저 CPU는 유저 프로세스 b가 인터럽트된 것을 인식

컨텍스트 스위치가 일어남

13-커널 CPU가 DST를 조사하기위해 OS 프로세스 E를 실행시킴

14-커널 CPU는 8번에서 인터럽트된 유저 프로세스 b를 다시 실행하기 위해 OS 프로세스 F를 실행함

컨텍스트 스위치가 일어남

15-유저 CPU가 유저 프로세스 b를 다시 실행시킴

댓글 공유

[알고리즘] 프로그래머스 크레인 인형뽑기 게임 파이썬 풀이

카테고리 : 알고리즘 리딩타임 : 1 분 페이지뷰 : --

문제 링크

풀이 방법

스택을 이용한 전형적인 문제이다. moves 배열에서 인형뽑기를 할 각 열을 꺼내주고,

board의 해당 칸이 0보다 크면(=인형이 있으면) 그 인형을 뽑는다.

스택에 넣어주기 전, 스택의 top을 검사하여 뽑은 인형과 top이 같으면 인형 수를 2 증가시킨다.

코드

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
from collections import deque

def solution(board, moves):
    answer = 0
    moves = deque([move-1 for move in moves])
    stack = []

    while moves:
        found = False
        j = moves.popleft()

        for i in range(len(board)):
            if board[i][j] > 0:
                found=True
                curr = board[i][j]
                board[i][j] = 0
                break


        if stack and found:
            top = stack.pop()
            if curr == top:
                answer+=2
            else:
                stack.append(top)
                stack.append(curr)
        else:
            stack.append(curr)

    return answer

배운 점

파이썬의 변수 스코프에 대해서 헷갈려서 자꾸 에러가 났었다.

curr 변수가 루프를 돌면서 계속 살아있어서 만약 해당 칸에 인형이 없다고해도(=0) 전에 선택한 인형의 값이 남아있었다.

파이썬의 경우, 블록 스코프를 가지고 있는 다른 언어(C, Javascript…)와 다르게 함수 스코프이고,

오직 글로벌 변수와 로컬 변수밖에 존재하지 않는다.

이 기회를 통해서 다시 한번 파이썬의 변수 스코프에 대해 알게 되었다.

참고 링크

파이썬 변수 스코프에 관해서 - https://soooprmx.com/archives/5854

댓글 공유

Copyrights © 2020 Jin Seon. All Rights Reserved.
저자 이미지

Jin Seon

Aspiring developer dreaming about freedom


Software Enginner


Seoul