devkty 님의 블로그

[참고 사이트]https://blog.encrypted.gg/1035https://velog.io/@kimdukbae/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall-Algorithmhttps://velog.io/@asbazq/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Floyd-Warshall플로이드 알고리즘2차원 배열에서 모든 정점 쌍 사이의 최단 거리를 구해주는 알고리즘 입니다.방향/무방향 그래프 둘다 사용 가능합니다. 또한 음의 가중..

9:30 ~컴퓨터 시스템 3.4부터 공부를 하기 시작했다.오늘 팀 코어타임에 컴퓨터 시스템 3.8부분을 발표하기로 했기 때문에 3.4 완료 후 3.8부분을 먼저 공부했습니다. 관련 내용은 따로 포스팅 하겠습니다.내일 퀴즈 내용으로 플로이드 관련된 내용이 나온다고 하여 파이썬 코드를 짜보았습니다.해당 내용관련 개념도 다음 페이지에 포스팅하도록 하겠습니다.퀴즈대비 11404 플로이드https://www.acmicpc.net/problem/11404import sysinput = sys.stdin.readline # 입력을 빠르게 처리n = int(input()) # 도시(노드) 개수m = int(input()) # 버스(간선) 개수INF = int(1e9) # 무한대로 초기화 (10억 이상이면 ..

4주차 컴퓨터시스템(챕터3 ~ 3-3까지)3장에서는 기계어 코드와 기계어 코드의 읽기 쉬운 형태인 어셈블리 코드에 대해 자세히 알아봅니다.기계어 코드를 배워야하는 이유는 무엇인가? 어셈블리 코드를 이해하면 컴파일러의 최적화 성능을 알 수 있으며, 코드에 내재된 비효율성을 분석할 수 있습니다. 원리를 알고 있으니 프로그래밍하는데 큰 도움이 됩니다.+하드웨어를 사용하기위해서 고급언어를 컴파일러가 해석을 할 때 환경에 따라 다르기 때문에 기계어 코드를 배워야한다. 고급언어의 추상화 때문에, 어셈블리어 컴파일을 보면서 자바코드를 효율적으로 수정할 수 있다. 그렇기 때문에 어셈블리어를 배우고, C프로그램이 어떻게 기계어 코드 형태로 컴파일되는지 공부합니다. C코드로 표현된 계산에 대해서 최적화 컴파일러는 실행 순..

오늘은 본가에 다녀왔다. 머리도 정리해야하고, 다음주부터 있을 C언어 전공책을 가지러 갔다. 그런 관계로 오늘은 토요일날 정리하다 못한 컴퓨터 시스템을 정리하고 공부를 좀 더하다가 집에 들어가보겠다.본가 다녀온 동안 먹은 것들을 사진으로 남겨보았다.

아침부터 점심 지나기까지 3번 배낭 문제를 Top-down 방식으로 푸는 것에 시간을 쏟았다. dp Top-down방식의 문제가 별로 없어 이번 문제에서 연습을 하고자 했다. 그런데 개념만 알고 처음 구현해 봐서 코드가 익숙치 않다. 100퍼센트 이해됐다고는 생각 안해서 다음에 다시봐야겠다.3번 12865 아주 평범한 배낭https://www.acmicpc.net/problem/12865K 값이 증가할 수록, 주어진 물품의 무게에 도달할 때마다. +1씩 추가된다. 그전값도 반복된다. 그럼 그전값하고 새로 만들어진 값을 비교해서 가장 큰 값을 출력하면 되지 않을까?찾아본 결과 원래 풀던 for 반복문으로도 풀수 있지만, 이번에는 Top-down 방식을 적용시켜 풀었다.# K 값이 증가할 수록, 주어진 물품..

[참고 사이트]https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-SubsequenceLCS는 두가지의 의미가 있습니다.기본적으론 최장 공통 부분수열(Longest Common Subsequence)이고, 최장 공통 문자열(Longest Common Substring)을 의미하기도 합니다.위의 예시처럼 최장 공통 부분수열(Longest Common Sub..

새로운 주차가 시작됐다. 계획을 다음과 같이 수립했다.코어 타임(그룹 스터디 타임): 토,월은 컴퓨터 시스템(그 외에는 알고리즘)키워드: 동적 프로그래밍, 그리디 알고리즘컴퓨터 시스템: 3장 프로그램의 기계 수준 표현 (특히 3.4, 3.7, 3.8)공부 타입 및 목표: 개념 코드 위주의 이해, 하 ~ 중 반복 숙달로 문제 작성 가능(그러나 몇몇개념은 문제로 이해)자리를 전체적으로 옮겼다. 이후 첫번째 문제를 풀어보았고 팀원분들과 함께 코어타임과 코어타임을 어떻게 활용할지 알아보았다.컴퓨터 시스템은 자신의 담당 범위를 공부하여 코어타임에 공유하기로 했다.DP의 개념을 공부하고 바로 문제를 풀어보았다. DP는 문제량으로 밀어야 능숙해질 것 같다.1번 2748 피보나치 수 2https://www.acmicp..

DP란?복잡한 문제를 여러 개의 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 나중에 같은하위 문제가 다시 발생하면 저장된 결과를 사용하는 알고리즘입니다.즉, 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘입니다.상황에 따라 구현 방식은 다르다. 가장 쉬운 문제는 피보나치 문제이다.원래 피보나치 수열은 N번째 항을 재귀로 호출해 중복된 연산으로 계산이 오래걸린다. 그러나 DP를 통해 하위의 배열을 미리 만들고, 중간 결과를 저장해서 시간복잡도를 O(N)까지 줄일수 있습니다.DP문제가 어려운 이유는 문제를 보고 DP를 생각해내기 어렵다는 점입니다. 테이블을 정의해야하고 점화식을 찾은 후에 초기 값을 정의해야합니다. 의외로 점화식 찾기가 어렵기 때문에 많은 문..

9:00 ~시험을 치기 전에 복습을 하고, 시험에 쳤다.13:00 ~ 14:004주차 발제를 진행했다.14:00 ~ 15:00코치님들과 함께 티타임을 했다. 이후 친 시험에 대해서 코드리뷰를 진행했습니다.[추가] 1번 1338 바닥 장식https://www.acmicpc.net/problem/1388# 같은 행일때 같게 치면 근처(왼,우) 스캔해서 같은 값이면 하나로 치면 될 것 같음# 순회하면서 같은거 나오면 한개로치고 아니면 따로 셈import sysinput = sys.stdin.readline# 방 바닥의 세로 크기 N, 가로 크기 MN,M = map(int, input().split())graph = [] # 2차원 리스트의 맵 정보 저장할 공간for _ in range(N): gr..

9:30 ~어제 풀었던 내용을 복기했다. 오늘은 시험 전날이기 때문에 문제 푸는 것에 집중해보겠다.### **14번 18352 특정 거리의 도시 찾기**https://www.acmicpc.net/problem/18352도시와 도로의 개수가 주어지면 최단 거리 기준 K인 도시가 무엇인지 뽑는 문제이다. 만약에 도달할 수 있는 도시가 없다면 -1을 출력한다. BFS로 한 단계식 탐색하며 찾다가 K 거리에 도달하면 결과를 저장한다. 그래프 리스트로 도시들을 관리하고 거리 리스트로 -1로 초기화해 거리를 저장한다. 큐를 통해 도시를 탐색하고 거리를 갱신한다.```pythonimport sysfrom collections import dequeinput = sys.stdin.readline# 도시 개수(N), 도..