깃 - 커밋 메시지를 추적할 수 있게 작성하자

깃허브

깃허브란?

가장 대표적인 코드 저장소

• 다양한 오픈소스 코드, 회사에서 제공하는 코드를 참조하다보면 실력울 높일 수 있음.

• fork를 사용하면 쉽게 남의 코드를 내 코드 저장소로 가져올 수 있다 -> 버그나 개선 사항이 있을 경우 가져온 프로젝트에서 수정 후 PR(Pull Request)를 요청해 반영할 수 있음. 내가 여러가지 공부를 해봤다(fork) / 내가 독창적으로 만들어서 공부를 했다. 두가지를 분리해야한다. fork를 한경우

• 질문 : 왜 fork를 하였는가?

• 목적이 있어야 한다.

• 단순 코드 뿐만 아니러 정보를 정리해서 전달하는 기능도 수행

  국내외 개발자 / 회사 블로그

• https://blog.naver.com/sicle_officail/2222071769230

  • 개발자로 경력을 전환한 비전공자들의 학습을 돕기 위해 정리한 블로그

    회사 블로그

    어떤 회사에 취직하고 싶나?

• ex) 라인에 취직하고 싶다면 그 회사가 어떤 일을 하는지 유심히 봐야함

• 그 회사의 기술 블로그를 봐야함. (어떤 주제를 다루는지 - 내가 관심이 있나?)

  회사 블로그에 주목해야 하는 이유

• 최신 개발 지식과 기술 학습에 유용한 교재

• 오픈 소스로 도움 받을 수 있음

• 기술 블로그 개발자 채용 공고에도 주목할 필요가 있다.

중고신입은 회사에서 어떤 인재상을 원하는지 안다.

좋은 개발자 커뮤니티

StackOverflow

개발 관련 다양한 질문과 답변이 올라오는 사이트

• 활용 힌트
  • 글이 올라온 날짜 확인
  • 운영체제나 컴파일러/인터프리터 버전 확인
  • upvote / downvote 수를 보라
  • 첫 답변만 맹신하지 말 것.

    유튜브 / 강의

    The Ultimate List of YouTube Channels to Boost your Neb Development and Programming Skills https://devandqear.com/posts/the-ultimate-list-of-voutube-channels-to-boost-your-web-development-and-programming-skills/ 유튜브에도 좋은 개발 관련 내용이 많다 • 멋진 내용은 영어권에 집중되어 있지만, 자막과 코드를 보면서 학습해보자. 대학교에서도 좋은 강의를 제공한다 : httos://online-learning.harvard.edu/course/cs50-introduction-computer-science?delta=0 • cs 50으로 cS 101(입문) 전에 들으면 좋은 내용으로 구성 https://missing.csail.mit.edu/ • MIT 컴퓨터과학에서 과외로 들어두면 좋은 내용으로 구성

사례 : RFC, W3C, man page

목적이 명확히 있을때 이용할 것! 학습 목적으로는 피할 것.

• 인터넷 표준 문서(Request for Comments), 웹 표준 문서(World Wide Web Consortium), 유닉스 매뉴얼 페이지 • 모두 공급자 입장에서 작성했다는 특징이 있다 • 명료하게 어떤 목적을 달성하기 위해 무엇을 해야 한다는 식으로 기술되어 있다 • 반대로 사용자 입장에서는 학습용으로 사용하기 아주 어려운 특징이 있다 • 사례 중심도 아니고 문제 해결 방식도 아니다 • 매뉴얼 페이지에서 대안: TLDR(httos://aithub.com/tldr-pades/tlar) • (그나마) 쉽게 읽는 방법 • 곡 필요한 제약 사항 중심으로 본다: 예) URI 최대 길이가 있을까요? • 참고 구현체(reference implementation)를 본다 + 주의) 현실적인 문제로 인해 표준과 다를 수 있다: 예) 실질적인 URI 최대 길이는?

메일링 리스트

• Infoq: 소프트웨어 아키텍트, 개발, AI https://www.infog.com/ • OReilly: 프로그래밍, AI, 인프라스트럭처 https://www.oreilly.com/emails/newsletters/ • JetBrains: 자바, PHP, Net, C++, 커뮤니티 a httos://www.etbrains.com/resources/newsletters/ • 깃허브: 흥미로운 저장소를 일/주/월 단위로! a https://github.com/explore/email • 해커뉴스: 여러 가지 다양한 개발 소식을 전해주는 해커뉴스 https://hndigest.com/

사례 : pdf 서적

• 최근에는 기업이 스폰서해서 무료로 공개하는 좋은 책들이 늘어나는 중 > 기업들이 집필에 간접적으로 기여 • Monolith to Microservices: https://www.nginx.com/resources/library/monolith-to-microservices/(O'Reilly) • Web Application Security: https://www.nginx.com/resources/library/web-application-secunty/

• I Heart Logs: Event Data, Stream Processing, and Data Integration: https://www.confluent.io/ebook/i-heart-logs-event-data-stream-processing-and-data-integration/(O'Reilly) • DEEP LEARNING WITH PYTORCH: https://pytorch.ora/deep-learning-with-pytorch (Manning) • Designing Distributed Systems: https://azure.microsoft.com/en-us/resources/kubernetes-ebook-collection/(O'Reilly)

  사례 : 위키

  • https://help.ubuntu.com/community/CommunityHeloWiki • 우분투에서 만든 위키 • 우분투와 관련된 하우투, 팁, 각종 트릭을 소개 • 설치, 하드웨어 추가, 서버 설정, 보안, 시스템 관리 등 여러 분야에 걸쳐 유용한 정보를 소개 • https://docs.microsoft.com/ko-kr/ • 개발자 위키의 원조라고도 볼 수 있는 MSDN • 마이크로소프트 관련 제품들에 대한 포괄적인 정보를 제공 • 비주얼 스튜디오로 윈도우 애플리케이션을 개발할 때 필수

결론

• 아쉽지만 컴퓨터와 소프트웨어는 영어 문화권이 강세 • 최신 자료는 모두 영어를 중심으로 되어 있음 > 최근에 한국어로 번역 작업이 진행되고 있긴 하지만 아무래도 영어 자료가 풍부함 • 묻고 답하는 내용은 대부분 영어로 진행됨 • 프로그래밍 언어도 모두 영어를 기준으로 만들어져 있음 • 한국어를 기반으로 만들어진 프로그래밍 언어도 있지만 주류가 아님 • 상업적인 목적으로 개발할 경우에는 영어 기반의 언어가 대세 •열심히 읽고 생각하고 실생활에 적용합시다!

정보 찾는 팁

• 무작정 검색 엔진에서 키워드만 넣는다고 해법이 나오지는 않는다 • 내가 무엇을 찾는지를 먼저 생각하고, 다른 사람이 이런 정보를 어떻게 표현했을지를 유추하는 습관을 기르자 > 자주 사용하는 용어와 검색 엔진 옵션을 잘 조합하면 빠르고 정확하게 내가 원하는 답을 찾을 수 있다

구글검색

• 개발 관련 검색은 비교적 단순하다(1)

• 오류를 찾을 경우 정확한 오류 메시지를 따옴표 안에 넣어서 검색한다 • 소프트웨어 설치 방법이 필요한 경우 정확한 소프트웨어 패키지 이름(예: Python 3. 기과 버전 이름과 목표 운영제제(예: Windows 10, Ubuntu 18.04, Macos X Catalina)를 기술한다 • 하우투, 튜토리얼 문서를 찾을 경우 • howto나 tutorial이라는 단어를 붙인다 • 뒤에 설명할 filetype: " 을 사용해 pdf나 pptx와 같은 문서 형식을 명시적으로 지정한다 • 뒤에 설명할 site:”를 사용해 slideshare(slideshare.net)나 Speaker Deckispeakerdec.com)로 검색 범위를 한정한다

• 개발 관련 검색은 비교적 단순하다(2)

• 콩두를 검색할 경우 프로그래밍 언어 이름을 명시적으로 붙이는 편이 유리하다 + 예) 최근 프로그래밍 언어 사이에서 유사한 형태가 많다 • 검색 유효성을 판단하기 위해 날짜 정보가 있을 경우 이를 확인하자! • 개념 정립 과정에서 문서를 검색하고 싶은 경우 이미지 검색에서 마음에 드는 그림을 눌러 해당 사이트로 들어가는 방법도 추천한다 • 다양한 방법을 사용했음에도 불구하고 내가 원하는 정보가 검색 엔진으로 거의 검색되지 않을 경우라면 두 가지를 의심한다

1. 너무 당연하므로 해당 주제에 대해 아무도 질문하고 대답하지 않는다 + 주변 사람에게 상황을 설명하고 조언을 얻는 방법도 좋다
2. 정말 나에게만 발생하는 문제다 + 검색이 아니라 질문으로 대응할 필요가 있다

HTML : 웹 페이지의 구조를 나타냄 CSS : 웹 페이지 안에 존재하는 요소들의 스타일을 나타냄 JS : JS로직을 통해 문서의 구조와 스타일에 변화를 줄 수 있음. - 브라우저에서는 Javascript에서 HTML, CSS에 접근할 수 있는 API를 제공함

브라우저에서는 Window Object를 제공해주고,자바스크립트에서는 해당 객체를 통해 각종 html element나 css에 접근하고 조작을 가할 수 있다.

Javascript의 특징

HTML+CSS와 함께 사용해 client side 웹 프로그램을 작성할 수 있다. 웹 브라우저에서 바로 실행이 가능하다.

alert 명령어

alert 뒤에 따라오는 괄호 안에 들어있는 메시지를 브라우저 경고창에 띄워주는 명령어

실습방법

Javascript 코드를 작성한다. lecture01.js

alert("hello world");

해당 코드를 로드하는 HTML 파일을 작성한다

index.html

<html>
    <head>
    ...
    <script src="lecture01.js"></script>
    ...
    </head>
    <body>
    ...
    </body>
</html

console 이용

개발자 도구 (Developer Console)

브라우저의 우측 상단 메뉴에서 더보기, 개발자 도구 메뉴를 이용해 활성화 여러 탭 중 console 탭을 사용해 console 을 확인 가능 직접 명령어를 입력해 실행 가능하며 (>) , 그 결과를 바로 확인 가능 (<)

console.log 명령어

console.log 뒤에 따라오는 괄호 안에 들어있는 메시지를 콘솔창에 출력하는 명령어 console.log 명령어 괄호 안에 여러 개의 메시지를 콤마(,)로 구분하여 활용할 수도 있음

변수

변수 선언과 초기화

var name=prompt("") : 해당 문장을 출력후 사용자에게 값을 입력받아 입력 받은 값을 저장하게 함.

변수의 이름을 사용하면, 변수의 값을 읽어서 사용 가능 var var1 = "1", var2 = "2", var3 = "3";

console.log(var1); alert(var2); prompt(var3);

자료형

기본 자료형

자료형이란?

변수에 저장할 수 있는 값의 종류를 자료형이라고 한다.

자료형의 종류

number Type: 숫자 var a=100, b=3.14; string Type: 문자열 var c="안녕하세요", d="a"; boolean Type: 맞다/틀리다를 표현 var e = true, f = false; typeof() 명령어 typeof 뒤에 따라오는 괄호 안에 들어있는 변수의 type을 알려주는 명령어

var a=100;
console.log(a,typeof(a));
//100 "number"라고 출력

var c="안녕하세요";
console.log(c,typeof(c));
//안녕하세요 "string"라고 출력

var e=true;
console.log(e,typeof(e));
//true "boolean"라고 출력

prompt는 사용자로부터 받은 문자열을 결과로 돌려주기 때문에

import sys
sys.setrecursionlimit(2000) #최대 재귀를 늘려줘야 런타임 에러를 피할 수 있다

def dfs(v):
    visited[v] = True
    next = numbers[v] #다음 방문 장소
    if not visited[next]:
        dfs(next)


for i in range(int(input())):
    n = int(input())
    count = 0
    numbers = [0] + list(map(int,input().split()))
    visited = [True] + [False] * n
    for j in range(1,n+1):
        if not visited[j]: #방문 안했을때
            dfs(j) #DFS 실행
            count += 1 
    print(count)

순열이 처음에 무조건 순회가 된다는 점을 몰랐다. dfs 함수 안에서만 해결하려해서 헷갈렸다.

코드참조 https://claude-u.tistory.com/434

설명참조 https://duwjdtn11.tistory.com/522

def bfs(x,y):
    #큐를 생성
    queue = deque()
    #큐에 시작 노드 넣기
    queue.append((x,y))
    while queue:
        #큐에서 맨 밑 노드 팝
        x,y = queue.popleft()
        #상하좌우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            #범위를 넘어갈 때
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            #이동할 수 없는 칸 일 때
            if graph[nx][ny] == 0:
                continue
            #처음 방문하는 칸일때만 +1을 해줌
            if graph[nx][ny] == 1:
                #최소경로에 1을 더해줘서 갱신
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))
    return graph[n-1][m-1]



from collections import deque
n, m = map(int,input().split())
graph = []
for i in range(n):  
    graph.append(list(map(int,input())))

dx = [-1, 1, 0 , 0]
dy = [0, 0, -1 , 1]
print(bfs(0,0))

def dfs(n):
    #시작노드 방문 처리
    visited[n] = True
    #시작노드 출력
    print(n, end=' ')
    #인접 노드 방문 하였는지 확인
    for i in graph[n]:
        if visited[i] == True:
            continue
        #방문하지 않았으면
        else:
            visited[i] = True
            dfs(i)

def bfs(n):
    queue = deque([n])
    visited[n] = True
    while queue:
        v = queue.popleft()
        print(v, end=' ')
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


from collections import deque
n, m, v = (map(int, input().split()))
visited = [False] * (n+1)
graph = [[] for _ in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
for i in range(1,n+1):
    graph[i].sort()   
print(graph)

dfs(v)
print()

#방문 기록 초기화를 시켜줘야함...
visited = [False] * (n+1)
bfs(v)

dfs, bfs 함수 짜는건 수월했으나, 그래프에 노드들을 저장할 때의 아이디어가 부족했음. 마지막에 다 구현해두고 bfs(v)가 1이 출력되어서 에러를 찾고자 고생했는데, 알고보니 dfs(v)에서 이미 방문처리를 다 해두어서 1만 출력된것이었음. visited리스트 요소들을 모두 False처리를 해주면서 해결함.

'이것이 코딩테스트다' 유튜브 강의 내용을 기반으로 하였다.

DFS

• DFS는 깊이 우선 탐색 이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘.
• DFS는 스택 자료구조(혹은 재귀 함수) 를 이용한다.

  DFS의 구체적인 동작 과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 함
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 더이상 2번의 과정을 수행할 수 없을때까지 반복한다.

이후 매번 스택의 최상단 노드를 확인하면서 인접한 노드 중에 방문하지 않은게 있다면 방문하면 된다. 이제 다시 스택의 최상단 원소는 2로 바뀌었기 때문에 dfs가 진행됨. 1번은 방문했기 때문에 7에 방문. dfs는 깊이 우선으로 탐색을 진행하기 때문에, 그래프에서 가장 깊은 부분을 우선적으로 탐색한다. 가장 깊게 들어갔다가 더이상 깊게 들어갈 수 없다면 다시 돌아와서 다른 방향으로 가야한다.

그래프가 출제되면 노드의 번호가 1번부터 시작하는 경우가 많기 때문에 인덱스 0에 대한 내용은 비워두고, 1번 인덱스부터 해당노드에 인접한 노드들을 리스트 형태로 담아줄 수 있다. 1번 노드에 인접한 노드들은 2,3,8번임을 넣어줌.

문제에서 나오는 인덱스 번호를 그대로 매핑할 수 있기 때문에 그래프에 0번 인덱스도 포함시킨다

BFS

• BFS는 너비 우선 탐색이며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
• BFS는 큐 자료구조를 이용한다.
• 특정 조건에서의 최단 경로 문제를 해결 하기 위한 목적으로도 효과적으로 사용될 수 있음.

BFS 구체적인 동작 과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다.

큐의 원소가 위에서 들어와서 아래로 나간다고 가정. bfs는 너비 우선 탐색으로서, 시작 노드부터 가까운 노드를 우선적으로 해서 탐색한다. 넓게 2,3,8(1로부터의 거리가 1)부터 방문하는 것을 확인할 수 있다. 7,4,5 세 노드는 모두 시작 노드인 1번으로부터 거리가 2임. 6은 거리가 가장 멀기 때문에 가장 나중에 탐색된다. 각 간선의 비용이 동일해서 최단경로 풀 때 사용. 큐를 위해서 덱 라이브러리를 불러와주고, 현재 노드가 8개이기 때문에 1번부터 8번까지 8개의 원소를 모두 처리할 수 있도록 총 원소가 9개인 리스트 객체를 만들어주고, 0번 인덱스는 사용하지 않는다. 각 노드와 연결된, 인접한 노드들을 차례대로 넣어준다. 방문 처리는 visited리스트를 만들어줌.

1.시작노드를 큐에 넣어줌. 2.시작 노드를 방문 처리한 뒤에 3. 큐가 빌 때까지, 더이상 수행할 수 없을 때까지, 반복을 해준다. 4. 큐에서 하나의 원소를 꺼낸다. (팝레프트를 통해 가장 먼저 들어온 원소를 꺼낼 수 있다.)해당 노드의 번호를 출력해준다 5. 꺼낸 노드와 인접한 노드를 하나씩 확인하면서 아직 방문하지 않은 노드가 있다면 큐에 넣어준다.

dfs와 bfs를 이용해서 방문 처리가 이루어지는 지점에서만 카운트를 수행하면 된다. list(map(int,input()))) : 원소를 입력받은 후, 해당 원소들을 int로 바꿔서 저장한다. 연결된 모든 위치에서 방문처리를 한다. 리턴값을 사용하지 않기 때문에, 단순히 연결된 모든 노드에 대해서 방문 처리를 수행하기 위한 목적으로 수행된다. 결과적으로, 이 dfs는 한번 수행되면, 해당 노드와 연결된 모든 노드들도 방문 처리를 할 수 있게 하고, 시작 노드가 방문 처리가 되었다면, 즉 처음 방문하는 것이라면, 그 때만 result값을 증가시킨다. 큐에 원소를 넣어서 방문처리 할 때 초기 원소의 값이 1인 원소에 한해서만, bfs를 진행한다. 상하좌우 탐색을 진행하면서, 옆에 있는 노드를 방문하게 되고, 이 노드까지의 거리는 2라고 기록한다. 이 노드 또한 큐에 담기게 되고, 이 노드와 상하좌우 연결되어 있는 노드들을 확인해서 인접한 노드를 방문. 그 노드 또한 방문 처리 한 후, 큐에 넣는다. 매번 새로운 지점을 방문할때, 이전 지점까지의 최단거리에 1을 더한 값을 기록할 수 있도록 한다.

입구와 출구가 같음. 선입후출

큐

왼쪽에서 들어오고 오른쪽으로 나감 선입선출

리스트로 물론 구현할 수 있지만, 리스트 사용 시, 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있으므로 큐를 구현할 땐 꼭 deque 라이브러리를 사용하도록 한다.

하나의 deque 객체를 생성한 뒤에 삽입할땐, append, 삭제할 때는 popleft를 사용한다. 둘 다 시간 복잡도는 상수 시간으로, O(1)이다.

파이썬에서 리스트를 이용해서 특정 인덱스에 존재하는 원소를 꺼내기 위해, 팝 메소드를 호출하게 되면, 원소를 꺼낸 뒤에, 원소의 위치를 조정하는 과정이 필요하기 때문에, 원소를 꺼내는 연산 자체가, O(K)만큼의 시간 복잡도가 요구된다. 그렇기에, 리스틀 이용하지 않고 deque을 이용해서 큐를 구현하자!!

재귀함수

재귀함수란 자기 자신을 다시 호출하는 함수를 말한다. ex)

def recursive_function():
    print('재귀 함수를 호출합니다.')
    recursive_function()
recursive_function()

'재귀 함수를 호출합니다.' 문자열을 무한히 출력하게 되며, 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.

파이썬에서는 재귀를 호출하는 과정에서 깊이 제한이 있기 때문에, 별다른 설정을 하지 않고 함수를 재귀적으로 호출하게 되면 오류메시지가 나타남.

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.

• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.

  • 종료 조건을 포함한 재귀 함수 예제 def recursive_function(i):

    **#100번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100:
        return**
    print(i, '번째 재귀 함수에서'. i+1, '번째 재귀함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료합니다.')

    recursive_function(1)

    팩토리얼 구현 예제

    n! = 1 x 2 x 3 x ... x (n-1) x n

    #반복적으로 구현한 n!
    def factorial_iterative(n):
    result = 1
    #1부터 n까지의 수를 차례대로 곱하기
    for i in range(1,n+1):
        result *= i
    return result

    #재귀적으로 구현한 n!
    def factorial_recursive(n):
    if n <= 1: #n이 1이하인 경우 1을 반환
        return 1
    #n! = n * (n-1)!을 그대로 코드로 작성
    return n * factorial_recursive(n-1)

    최대공약수 계산(유클리드 호제법) 예제

    192와 162의 최대공약수가 12와 6의 최대 공약수와 같다는 것을 알 수 있다. 12는 6의 배수이므로, 6을 최대 공약수라고 말할 수 있다. 더 작은 수로 식의 형태를 바꾸는 형태가 반복적이며 동일한 구조를 가지고 있기 때문에 재귀적으로 직관적으로 코드로 옮길 수 있다.

dfs에서는 재귀함수를 이용하기 때문에 재귀함수를 잘 알아두어야 함.

문장을 표현할 때 사용하는 큰따옴표("문장") 기호 대신 작은따옴표('문장')를 사용하면 큰따옴표를 출력할 수 있다.

설계

코딩

import sys
from itertools import permutations

n = int(input())
num = list(permutations([1,2,3,4,5,6,7,8,9], 3)) 

for _ in range(n):
    test, s, b = map(int, input().split())
    test = list(str(test))
    remove_cnt = 0

    for i in range(len(num)):
        s_cnt = b_cnt = 0
        i -= remove_cnt

        for j in range(3):
            test[j] = int(test[j])
            if test[j] in num[i]:
                if j == num[i].index(test[j]):
                    s_cnt += 1
                else:
                    b_cnt += 1

        if s_cnt != s or b_cnt != b:
            num.remove(num[i])
            remove_cnt += 1

print(len(num))

참조 https://jainn.tistory.com/36

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

설계

파이썬 라이브러리 - itertools

코딩

import itertools

n = int(input())
arr = [i for i in range(n)]
cases = list(itertools.combinations(arr, n//2))
min_sum = n * n * 100

for i in range(n):
   arr[i] = list(map(int, input().split()))

for case_start in cases:
    sum_start = 0
    sum_link = 0
    for i in case_start:
        for j in case_start:
            if i == j: continue
            sum_start += arr[i][j]
    case_link = [i for i in range(n) if i not in case_start]
    for i in case_link:
        for j in case_link:
            if i == j: continue
            sum_link += arr[i][j]
    min_sum = min(min_sum,abs(sum_start - sum_link))

print(min_sum)

참조 https://tw0226.tistory.com/41

참고 https://rebro.kr/59

루트

• 트리의 가장 위쪽에 있는 노드.
• 루트는 트리 하나에 1개만 존재.

  리프

• 가장 아래쪽에 있는 노드
• 단말 노드, 외부 노드라고도 함.
• 물리적으로 가장 밑에 위치 한다는 의미가 아니라** 가지가 더이상 뻗어나갈 수 없는 마지막**에 노드가 있다는 것!

  비단말 노드

• 리프를 제외한 노드

  자식

• 어떤 노드와 가지가 연결되었을 때, 아래쪽 노드

부모

• 어떤 노드와 가지가 연결되었을 때, 위쪽에 있는 노드
• 노드의 부모는 하나뿐!

  레벨

• 루트에서 얼마나 멀리 떨어져 있는지 나타내는 것.

  차수

• 각 노드가 갖는 자식의 수
• 모든 노드의 차수가 n이하인 트리를 n진 트리라 함.
• 위 그림은 모든 노드의 자식이 3개 이하이므로 삼진트리임.
• 모든 노드의 자식이 2개 이하면 이진트리

  높이

• 루트에서 가장 멀리 있는 리프까지의 거리 -> 리프 레벨의 최댓값

순서 트리와 무순서 트리

형제 노드의 순서관계가 있는지에 따라 분류. 순서 관계가 있으면 -> 순서 트리 순서 관계가 없으면 -> 무순서 트리

순서 트리의 검색

너비 우선 검색

• 낮은 레벨 부터 왼쪽에서 오른쪽으로 검색, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법

깊이 우선 검색

• 리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것을 우선으로 함.
• 리프에 도달해서 더 이상 검색할 곳이 없으면 일단 부모 노드로 돌아가고 그 뒤 다시 자식 노드로 내려감
• 깊이 우선 검색은 세 종류의 스캔 방법으로 구분

1. 전위 순회

노드 방문 -> 왼쪽 자식 -> 오른쪽 자식

노드 A의 통과 시점에 주목하면, 'A를 방문->B로 내려감->C로 내려감'의 순서

트리 전체의 스캔

A->B->D->H->E->I->J->C->F->K->L->G

2. 중위 순회

왼쪽 자식 -> 노드 방문 -> 오른쪽 자식

노드 A의 통과 시점에 주목하면 'B로 내려감 -> A를 방문 -> C로 내려감의 순서

트리 전체의 스캔

H->D->B->I->E->J->A->K->F->L->C->G

3. 후위 순회

왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

노드 A의 통과 시점에 주목하면 'B로 내려감 -> C로 내려감 -> A를 방문'의 순서

트리 전체의 스캔

H->D->I->J->E->B->K->L->F->G->C->A

알고리즘 스피드는 완료까지 걸리는 절차의 수 로 결정됨. 예를 들어 선형검색의 경우에는 하나,하나씩 검색하기 때문에 데이터가 10개 라면, 아이템을 찾기까지 10개의 스텝이 필요하다. input size가 N이라면 N스텝이 요구된다고 할 수 있다. -> 선형검색의 시간 복잡도는 O(N)임.

Big O를 사용하면, 시간 복잡도를 빠르게 설명할 수 있다.

O(1) , 상수 시간

인풋이 100개라도 끝내는건 한번이면 충분하다 이 경우, 인풋이 얼마나 크든 동일한 수의 스텝이 필요하다. 이 함수의 시간 복잡도는 constant time(상수 시간)임. N이 얼마나 크던 상관 없이 끝내는데 동일한 스템이 필요하다 요걸 읽는 방법은 O(1)

이번에 두개의 출력을 해보쟈

그러면 끝내기 위해 2개의 스텝이 필요하다. 따라서 시간복잡도는 O(2)?? 아님!!! 여전히 동일하게 O(1)로 표현 Big O는 함수의 디테일엔 관심이 없기 때문!!

Big O는 러프하게, 어떻게 이 함수가 작동하는지 인풋사이즈에 따라! 표현

따라서 위 함수가 프린트를 2번 하더라도 여전히 O(1)로 표현한다. Big O는 상수(constant)에 신경을 쓰지 않는다. 예를 들어, 항상 200개의 스텝이 필요한 함수가 있다면, 인풋 사이즈와 관계 없이 이 함수의 시간 복잡도는 O(1)이다. 여전히 constant time(일정한 시간/ 상수)이니까!

constatnt time 알고리즘은 인풋 사이즈와 관계없이, 스텝이 정해진 알고림즘임.

O(N), 선형 검색

각아이템을 다 프린트 하는 함수. 배열 사이즈가 10이라면 10번 프린트를 한다. 만약 배열 100개 라면, 100개 스텝으로 이어진다. 선형 검색이랑 비슷하다. 배열의 각각 아이템을 위해 모두 작업을 해야한다. 배열이 커지면, 필요 스텝도 커질것. 이를 빅오로 표현하면, O(N). 그리고 이전처럼, 상수는 관계없음 하지만 O(2N)에서 2는 상수이므로 버려버림 -> O(N)으로 표현 O(2N) 이든, O(N)이든, 인풋이 증가하면, 스텝도 선형적으로 증가한다는 사실자체는 변하지 않기 때문! O(N)혹은 선형 시간복잡도를 그래프로 표현한 그림.

O(N^2) , 2차 시간

2차 시간은 중첩 반복이 있을 때 발생 배열의 각 아이템에 대해 루프를 반복하여 실행. 따라서 시간 복잡도는 인풋의 n^2인것.

인풋이 10개라면, 완성하는데 100번의 스텝이 필요한 것. 왜냐면 루프안의 루프에서 함수를 실행하기 때문! 따라서 2차 시간 보단 선형 시간 복잡도가 더 효율적인것으로 선호된다.

O(log N), 로그시간

이건 이진검색 알고리즘 설명할 때 쓰는거다. 이진검색에선, 인풋 사이즈가 더블이 되어도, 스텝은 딱 +1밖에 증가를 안했다. 왜냐면 이진검색에서는 각 프로세스의 스텝을 절반으로 나눠서 진행하기 때문임.->요걸 표현하면 O(log N)이 됨. 로그는 지수의 정 반대이다. 우리가 찾는 것은 몇번을 나눠야 , 예를 들어 32를 2로 몇 번을 나눠야 1이 나올까 임. 이진검색에서는 매번 스탭을 진행할 때 마다 인풋을 일단 반으로 나누고 시작함. 그렇기 때문에 인풋이 2배로 커져도, 검색을 하기 위한 스텝은 +1만 증가하는것. 왜냐면 한번만 더 나누면 되는것이기 때문. 빅오 노테이션에서는 base를 쓰지 않음! 빅오의 특성상 로그의 밑 숫자는 사라진다. 선형 시간보다는 빠르고 상수시간보다는 느리다.

하지만 이진검색은 정렬되지 않은 배열엔 사용할 수 없다.

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        //setContentView(R.layout.activity_main); //화면에 보이게 하는 거.

        LinearLayout l = new LinearLayout((this));
        l.setOrientation(LinearLayout.VERTICAL);

        LinearLayout.LayoutParams params = new LinearLayout.LayoutParams(
                LinearLayout.LayoutParams.MATCH_PARENT,
                LinearLayout.LayoutParams.MATCH_PARENT
        );

        setContentView(l, params); // 화면에 들어가서 보임.

        Button b = new Button(this);
        b.setText("Button");
        l.addView(b);

    }
}

Add TextView

package com.example.myapplication;

import androidx.appcompat.app.AppCompatActivity;

import android.os.Bundle;
import android.view.View;
import android.widget.LinearLayout;
import android.widget.TextView;


public class MainActivity extends AppCompatActivity {

    int count = 1;
    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main); //화면에 보이게 하는 거.

    }

    public void onClick(View view) {
        LinearLayout l = (LinearLayout) findViewById(R.id.LinearLayout);//linearlayout id 설정해야함
        TextView textView = new TextView(this);
        textView.setText("TextView" + count);
        count++;
        l.addView(textView);
    }
}

화면을 넘어갈 때 스크롤을 해주고 싶다. ->ScrollView : 스크롤 뷰 안에 들어있는 애를 스크롤해줌. 스크롤 뷰 안에 스크롤 하고 싶은 애를 넣으면 됨.

텍스트뷰 넣을 때마다 linearlayout이 확장 되는 것을 원하므로 layout_height는 wrap_content로 되어야한다

스크롤이 생성되면서 29아래로 더 보임

Table Layout

stretchedColumns

0, 1, 2 순. 적은 칸이 늘어남

shrinkColumns

layout_column

layout_span

Menu

ctrl + o : overriding 할 수 있는 목록이 나옴

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main); //화면에 보이게 하는 거.

    }

    //...을 누르면 얘가 실행됨
    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        MenuInflater inflater = getMenuInflater();
        inflater.inflate(R.menu.sample,menu);
        return true;
    }
}![](https://velog.velcdn.com/images/born_a/post/c03250fc-5c46-421f-a474-540606ba5b9b/image.png)

Handling click events

public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main); //화면에 보이게 하는 거.

    }

    //...을 누르면 얘가 실행됨
    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        MenuInflater inflater = getMenuInflater();
        inflater.inflate(R.menu.sample,menu);
        return true;
    }

    @Override
    public boolean onOptionsItemSelected(MenuItem item) {
        switch (item.getItemId()) {
            case R.id.item1:
                Toast.makeText(this,"아이템1",Toast.LENGTH_SHORT).show();
                break;
            case R.id.item2:
                Toast.makeText(this,"아이템2",Toast.LENGTH_SHORT).show();
                break;
            case R.id.item3:
                Toast.makeText(this,"아이템3",Toast.LENGTH_SHORT).show();
                break;
            case R.id.item4:
                Toast.makeText(this,"아이템4",Toast.LENGTH_SHORT).show();
                break;

        }
        return super.onOptionsItemSelected(item);
    }
}

Example) Options Menu

package com.example.myapplication;

import androidx.annotation.NonNull;
import androidx.appcompat.app.AppCompatActivity;
import androidx.constraintlayout.widget.ConstraintLayout;

import android.graphics.Color;
import android.os.Bundle;
import android.view.Menu;
import android.view.MenuInflater;
import android.view.MenuItem;
import android.widget.Toast;


public class MainActivity extends AppCompatActivity {

    @Override
    protected void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main); //화면에 보이게 하는 거.

    }

    //...을 누르면 얘가 실행됨
    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        MenuInflater inflater = getMenuInflater();
        inflater.inflate(R.menu.sample,menu);
        return true;
    }

    @Override
    public boolean onOptionsItemSelected(@NonNull MenuItem item) {
        ConstraintLayout constraintLayout = (ConstraintLayout) findViewById(R.id.constraintlayout);
        switch (item.getItemId()) {
            case R.id.White:
                Toast.makeText(this,"아이템1",Toast.LENGTH_SHORT).show();
                constraintLayout.setBackgroundColor(Color.rgb(255,255,255));
                break;
            case R.id.Red:
                Toast.makeText(this,"아이템2",Toast.LENGTH_SHORT).show();
                constraintLayout.setBackgroundColor(Color.rgb(255,0,0));
                break;
            case R.id.Green:
                Toast.makeText(this,"아이템3",Toast.LENGTH_SHORT).show();
                constraintLayout.setBackgroundColor(Color.rgb(0,255,0));
                break;
            case R.id.Blue:
                Toast.makeText(this,"아이템4",Toast.LENGTH_SHORT).show();
                constraintLayout.setBackgroundColor(Color.rgb(0,0,255));
                break;

        }
        return super.onOptionsItemSelected(item);
    }
}

• 라디오 그룹 먼저 생성 후 라디오 버튼을 넣자

n = int(input())
r = 0
for origin in range(1, n+1):
    nums = list(map(int, str(origin)))
    r = sum(nums) + origin
    if r == n:
        print(origin)
        break
    if origin == n:
        print(0)

import sys,math
from queue import PriorityQueue

input=sys.stdin.readline
inf=math.inf

#테스트 케이스
t=input()
t = int(t)

def dfs(x,y):
    global uy,ry
    #print("#",x)
    uy[x]=1
    if st[x]==1 and x!=1:return inf
    k=0
    for next in graph[x]:
        if next[0]!=y:
            if uy[next[0]]==0:
                zv=dfs(next[0],x)
                k+=min(zv,next[1])
    ry[x]=k
    return k

for _ in range(t):
    #섬의 수, 다리 수
    a,b=map(int,input().split())
    #0이 1개 들어있는 리스트 [0]에 (a+1)를 곱하면 [0, 0,..]이 됨
    #0이 a+1개
    #섬 노드들
    st=[0]*(a+1)
    uy=[0]*(a+1)
    #비용
    ry=[-inf]*(a+1)
    #a+1개 만큼의 공간을 만들어서 graph[n]이 n번 정점을 나타내도록 함.
    graph=[[]for i in range(a+1)]
    #다리 수 만큼 for문
    for i in range(b):
        y=list(map(int,input().split()))
        st[y[0]]+=1
        st[y[1]]+=1
        graph[y[0]].append([y[1],y[2]])
        graph[y[1]].append([y[0],y[2]])
    print(dfs(1,1))

코드 참고 https://joseph0528.tistory.com/64

따라서 아래와 같이 나타낼 수 있다.

graph = {1 : [2,3,4], 2 : [5], 3 : [5], 4 : [], 5 : [6, 7], 6 : [], 7 : [3]}

입력받은 값을 리스트로 만들 때는 주로 아래와 같은 방법을 사용한다

#만약 n개만큼의 정점이 존재하고, m개만큼의 입력을 받는다면 
graph = [[] for _ in range(n+1)] # n+1개만큼의 공간을 만들어서 graph[n]이 n번 정점을 나타내도록 해 준다 
for _ in range(m):
    x,y = map(int,input().split()) #만약 1 2를 입력받으면 
    graph[x].append(y) # 1번 정점에 2를 넣어주고 -> graph[1] = [2] 
    graph[y].append(x) # 2번 정점에 1을 넣어준다 -> graph[2] = [1]

출처 https://dndi117.tistory.com/22

참고 https://puleugo.tistory.com/42