Skip to content

week 01~03 {swjungle} {ALGORITHMS}

INDEX#

CSAPP#

  • WEEK01: ~1.4. 프로세서는 메모리에 저장된 인스트럭션을 읽고 해석한다
  • WEEK02: 1.5. 캐시가 중요하다 ~ 1.7. 운영체제는 하드웨어를 관리한다
  • WEEK03: 1장 끝까지
  • Extra: 3장. 프로그램의 기계수준 표현 (특히 3.2, 3.4, 3.7, 3.8)

컴퓨팅사고로의 전환#

개발자는 컴퓨터에게 일을 잘 시켜야 한다. 그럼 일을 잘 시킨다는 건 뭐임?

  • Halting Problem: 컴퓨터가 답을 내게 만들어야 함 (멈춰야 함.) 무한루프는 생각보다 치명적인 에러임 이미 컴퓨터가 풀 수 있는 문제들을 여러분에게 주어지고 그 문제를 풀 능력을 기르는 것이 이번 주차의 목표.

백준문제 풀기: 키워드 위주로. 기초문제는 오늘 안에로 다 풀어주시고. 파이썬 언어로 풀기를 바람

시험

  • 매주 목요일 오전 10:00 ~ 11:30
  • 깃헙에 풀 리퀘스트를 생성하여 제출.
  • 풀이를 리뷰할 사람을 정해 코드리뷰.

WEEK01#

TIPS#

0014 Python 🐍으로 옮겨적을것

문제풀이#

0011 Algorithms ♾️#문제풀이 회고용 페이지에 추가할 것

WEEK02#

Doit!#

Doit 자료구조와 함께 배우는 알고리즘 기초 파이썬 편#Chapter04 스택과 힙

TIPS#

  • 0014 Python 🐍으로 옮겨적었습니다.
    • Exception을 상속하는 클래스는 raise가 가능해지는구나 p.157
    • try - except - else - finally
      • try: 원래 처리할 내용
      • except: 예상 에러 발생시 처리할 내용
      • else: 에러 미발생시 처리할 내용
      • finally: 심지어 중간에 리턴을 했을지라도 에러 발생여부 상관없이 무조건 실행하는 내용
    • BaseException과 Exception 간의 차이
    • __contains__: in 문법 사용 가능
    • dataclass ValueError mutable default class list is not allowed, use default_factory {python}

문제풀이#

다시 풀 문제#

  • 13334 철로 {boj} {priorityqueue} → 길이 d의 모든 선분 L에 대하여 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 문제가 힙이야?
    ~~- 11725(트리부모찾기): 멍청하게 10_000 ** 2 크기의 행렬을 생성하려고 했다.
  • 1707(이분그래프): 20분동안 문제를 다르게 바라보았다. 그래도 실마리는 찾은 것 같다.
    • 집합 안에서 정점끼리 인접하지 않아야 한다. DFS 돌면서 핑퐁하면서 집합을 다르게 준다. 두 개의 집합으로부터 중복되는 원소가 있다면 set.교집합() 결과가 비어있지 않으면 이건 이분그래프가 아니게 된다는 것임
  • 21606(아침산책) {boj} {dfs}: 73점,
    • Ai = 0인 케이스, Ai = 1인 i는 2개 이하인 케이스, N<= 100인 케이스는 모두 맞추었으나
    • 1 <= i < N 인 모든 정수 i에 대해 트리의 i번 정점과 i+1번 정점 사이에 간선이 존재하는 경우 (35점)과 추가 제한조건 없는(92점) 케이스는 틀렸다.
  • 2573(빙산): 시간초과
    • 대충봐도 비효율적이긴 한데... 시간 안에 구현하려면 깊게 생각할 시간이 부족해지지 않나???
  • 10000(원 영역): 시간초과

문제를 풀 때가 아니다, 머리에 든 게 없다 그래프를 다시 공부하자.

Prerequisites#

WEEK 03#

동적 프로그래밍 & 그리디 알고리즘

WEEK 04에서 C를 들어가는데, 미리미리 준비해주는 것이 좋을 것 같다. C '언어'를 배우는 게 아니다. C는 사실 제공되는 기능이 거의 없다. 기계를 이해하는 것, CPU 구조를 이해하는 데 중요하다. | 0015.1 CSAPP Third Edition Bryant, Randal E. O'Hallaron, David. 💻

일정#

  • 8월 30일(수) 14:00까지 모든 DP 문제 완료
    • '상' 문제는 얻어가려고 시간 낭비하지 말고 ✅ 채우는 데에 집중하자.
  • 8월 30일(수) 20:00 CSAPP 브리핑(1장 전체)
    • 질문거리와 요약내용 최대한 압축해서 정리하자.
    • 미리미리 읽어놓아야 문제없겠지?