연의 기록 🪁

이 글은 플로이드 알고리즘을 학습하며 이렇게 짜면 왜 안될까?를 고민한 과정을 작성한 글입니다. 플로이드 알고리즘 자체가 처음이라면 아래 링크에서 플로이드 알고리즘에 대한 개념을 익힌 후 글을 읽으시는 것을 추천합니다.https://blog.encrypted.gg/1035 [실전 알고리즘] 0x1C강 - 플로이드 알고리즘안녕하세요, 이번에는 플로이드 알고리즘을 다루겠습니다. 이제 최단경로 알고리즘인 플로이드, 다익스트라 알고리즘만 다루고 나면 나름 길었던 그래프 파트가 끝납니다. 목차는 눈으로 한 번blog.encrypted.gg 최단거리플로이드 알고리즘은 그래프의 모든 정점간의 최단거리를 구하는 알고리즘이다. 구현하는 방법은 간단한 편이다.NxN크기의 배열을 큰 값(INF)으로 초기화한다.각 정점간의 ..

개요LCS(Longest Common Subsequence)는 최장 공통 부분 수열로, 두 문자열 사이 공통되는 부분을 말한다. 즉 문자열의 상대적인 순서만 같으면 된다.예를들어 아래와 같이 2개의 문자열이 있을 때LCS는 ABCCE이다. 이런 LCS는 DP를 활용해서 구한다.과정먼저 AABCCDE와 A의 공통부분을 구한다고 가정해보자. 표에는 현재까지 가장 긴 공통부분의 길이를 저장할 것이다. 그러면 표는 아래와 같이 된다. (A는 길이가 1이니 최대 공통부분의 길이는 1이다.)이제 AABCCDE와 AB의 최장공통부분수열의 길이를 구해보도록 하자. 그러면 아래와 같이 될 것이다.여기서 주목해야 하는 부분은 공통되는 부분인 B가 나왔을 때이다. 저곳은 AAB와 AB의 LCS의 길이를 기록한 부분인데 AB..

https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 분석문제에서 요구하는 것은 주어진 숫자를 이진수로 바꾸고 포화 이진트리로 나타냈을 때 해당 트리가 이진트리가 맞는지를 판별하는 것이다.이진수를 포화 이진트리로 나타내려면 앞에 0을 채워서 값을 가공해줘야 한다. 이 부분을 좀 더 분석해보도록 하자.아래와 같이 생긴 것이 포화 이진트리이다. 리프노드를 제외하고 모두 2개의 자식노드를 가지고 있는 것을 포화 이진트리라고 한다. 1층짜리 포화 이진트리라면 노드의 수는 1개, 2층이면 3개, 3..

dfs를 응용하여 무향그래프에서의 사이클을 판단할 수 있는 코드이다.  간단하게 설명하자면 점을 하나씩 순회하며 사이클이 존재하는지 판별하는 코드이다. 예를 들어 아래와 같은 그래프가 있다고 하자. 눈으로 봐서는 2 3 5 사이클이 존재함을 알 수 있다. 아래 코드에서는 1에서부터 dfs를 하며 바로 사이클을 찾게 된다.dfs 가장 아래 path.pop_back()은 4와 같이 사이클에 포함되지 않는 노드를 제거하는 코드이다. 인접한 노드가 전에 방문한 노드밖에 없을 때의 경우이다.#include #include #include using namespace std;vector> graph; // 그래프 인접 리스트vector> edges; // 간선 정보vector visited;vector path;b..

https://www.acmicpc.net/problem/16724문제설명UDLR(상하좌우)로 각 칸에 있는 사람들이 어떤 방향에 있는지 주어진다. 사람들이 화살표를 따라 쭉 이동했을 때 모든 사람이 안전구역으로 들어갈 수 있도록 하려면 몇 개의 안전 구역을 만들어야 하는지를 묻는 문제이다. 아이디어이 문제는 그래프의 사이클의 개수를 찾는 문제이다. 사이클 1개당 1개의 안전구역을 만들어 주면 된다. 그래서 dfs를 통해 그래프를 순회하며 부모(사이클의 시작점)를 기록해주고, 마지막에 부모가 총 종류가 있는지를 리턴해줬다.아래의 경우 부모가 2종류가 나왔으니 2를 리턴해주면 된다. 코드정답 코드는 아래와 같다. dfs를 이용해 순회하며 다음 블럭이 현재와 부모가 다르다면 Union함수를 통해 부모를 합쳐..

https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 분석아래와 같이 도넛모양, 막대모양, 8자모양 그래프가 있다.여기서 문제의 핵심은 “이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결”했다는 부분이다.즉 아래와 같이 정점을 찾으면 거기에 연결된 것은 도넛, 막대, 8자그래프 중 하나여야 한다는 소리이다.그렇기에 정점에 아래와 같이 도넛그래프 2개를 합친 것 같은 모양이 붙어있거나 하는 일..

📌요약AWS에 대해 공부하고 싶다면 SAA 자격증 추천Udemy강의 수강 -> 덤프로 감잡기+개념 빈칸 채우기최단기간에 자격증만을 따고 싶다면 덤프 푸시는 것 추천 개요우연히 전사 공지에서 AWS 바우처를 지원해준다는 공지를 보게되었습니다. 개발을 하며 AWS 서비스를 써보기는 했지만(EC2, S3, Lambda, ECR 등...) 정말 잘 쓰고있는게 맞나? 하는 고민을 한 적이 있습니다. 당시 SAA자격증의 존재는 알았으나 응시료가 150달러(약 20만원...)라는 것을 알고는 나중에 따자며 미뤄두고(잊어버리고) 있었습니다. 그러던 차에 이렇게 계기가 생겼으니 공부해보자하고 자격증 취득에 도전하게 되었습니다. 프로젝트를 진행하며 쓰는 서비스만 사용해오던 것이 아쉬워 AWS의 전반적인 서비스들과 사용 ..

AWS 서비스 개요데이터 변환 및 분석Redshift: 데이터 변환 및 분석을 위한 도구Identity 및 접근 제어aws:PrincipalOrgId: 조직 자체를 가리킴aws:PrincipalOrgPaths: 조직 내 특정 부서를 명시콘텐츠 및 데이터 전송CloudFront: 엣지 로케이션에 정적 콘텐츠를 배치, 원본 서버에서 값을 가져옴AWS Global Accelerator: 애니캐스트를 사용해 가장 가까운 서버로 라우팅하여 빠른 데이터 전송Kinesis Data Firehose: A서비스에서 B서비스로 데이터 전송Kinesis Data Stream: 데이터를 모아 특정 서비스(A)에 전달모니터링 및 감사AWS Config: 리소스 구성 변경 및 추적AWS CloudTrail: 로그 기록 및 내역 ..

퀵정렬은 숫자 하나(pivot)를 골라서 올바른 자리에 넣어가며 정렬을 진행한다. 이때 배열을 쪼개가며 재귀적으로 정렬을 하기 때문에 최종적인 시간 복잡도는 O(nlogn)이다. 동작 과정이론적인 내용에 들어가기 앞서 어떤식으로 동작하는지 확인해보도록 하자. 아래와 같이 {5, 4, 1, 7, 6, 2} 배열이 있다고 했을 때 맨 왼쪽을 피봇으로 잡고 left와 right를 아래와 같이 각각 지정한다.여기서의 left는 pivot보다 작아야하고, right는 pivot보다 커야한다. 이제 left를 하나씩 옮기며 5보다 큰 수가 처음으로 나오는 지점을 찾으면 아래와 같은 상태가 된다.right는 pivot보다 커야한다고 했는데 이미 pivot보다 작다. 그러니 여기서 멈춰준다.이제 left와 right가..

앞서 Socket 라이브러리에서의 Socket, Connect, Write, Read, Close 동작에 대해 살펴봤다. 이러한 동작들을 뒷단에서 프로토콜 스택과 LAN 어댑터가 처리해준다. 그림으로 보면 아래와 같다.저번엔 Socket 라이브러리까지 살펴봤으니 프로토콜 스택 내부를 살펴보도록 하자. TCP와 UDP는 용도에 따라 다르게 사용된다. TCP는 브라우저나 메일 등의 일반적인 데이터 송수신을 담당하고, UDP는 DNS 서버에 대한 조회와 같은 짧은 제어용 데이터 송수신을 담당한다. (영상 전송에도 사용된다.)아래에 있는 IP 담당은 패킷의 송수신을 제어하는 부분이다. 내부에 있는 ARP 프로토콜은 IP 주소에 대응하는 인터넷의 MAC 주소를 조사할 때, ICMP는 패킷 운반 시 발생하는 오류 ..

지난 글에서는 BAS가 셀을 합쳐 패킷으로 복원한 뒤 PPP 패킷을 추출하고, 터널링용 헤더를 붙여 송신하는 과정까지 살펴봤었다. 그때의 과정을 복기해보면 MAC와 PPPoE가 BAS에 전달되는데에 사용되기 때문에 BAS에서 버려진다고 했다. 이 과정에 대해 좀 더 살펴보도록 하자.우선 BAS 역할은 크게 아래 두 가지 이다.1. 본인 확인과 설정값 통지2. 터널링을 이용한 패킷 운반앞선 그림에 나온 동작은 2번 역할과 관련된 것이다.ADSL이나 FTTH 액세스 회선은 최초에 프로바이더(KT, SKT 등)가 사용자에게 할당한 인터넷 접속용 사용자명과 패스워드를 입력해 로그인을 해야 인터넷에 액세스할 수 있다. BAS는 PPPoE라는 구조를 사용해 이러한 역할을 한다. PPPoE는 PPP라는 방식을 ADS..

앞서 메시지를 받으면 프로토콜 스택이 메시지를 송출해준다고 했었다. 이번 글에서는 이렇게 송출된 메시지가 어떻게 해서 인터넷까지 송출되는지 알아볼 것이다.개요먼저 집에서 인터넷으로 나가기까지의 전체적인 과정을 살펴보도록 하자.클라이언트에서 만든 패킷은 다양한 형태로 변화하며 프로바이더(ISP : KT, SKT 등)에 도착하게 된다. 참고로 좌측 끝에 있는 인터넷 접속용 라우터는 패킷 송신과 패킷 중계 동작을 한다.패킷 중계는 다른 네트워크에서 들어온 패킷을 목적지로 전달하는 중간 역할이고, 패킷 송신은 자신과 직접적으로 연결된 장치가 생성한 패킷을 받아 네트워크로 전송하는 것이다.패킷 중계 동작은 이더넷의 라우터와 거의 같다. 여기서 주목할 곳은 패킷 송신 동작이다. 이더넷에서의 패킷 송신의 주 목적은 ..

브라우저에 google.com을 입력했을 때 일어나는 일에 대해 말해보세요. 라는 질문은 기술면접 준비를 해봤다면 한번쯤 들어봤을법한 질문이다. 이에 내부 동작을 차근차근 정리해보고자 한다.일반적으로 클라이언트가 요청을 보내고 서버가 응답을 보낸다. 라고 하는데 내부적으로는 많은 일들이 일어난다. 1. URL 입력: 사용자가 웹 브라우저에 URL을 입력한다. 2. 도메인 이름 추출: 브라우저는 입력한 URL에서 도메인 이름을 추출한다.3. DNS 쿼리 전송: 브라우저는 DNS 리졸버에 도메인 이름을 전달하여 해당 IP 주소를 요청한다. 4. IP 주소 수신: DNS 리졸버가 도메인 이름에 대한 IP 주소를 반환한다. 5. 소켓 연결 수립: 이제 브라우저는 IP 주소를 사용하여 해당 서버와의 TCP/IP ..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr문제 분석문제에서 요구하는 것은 각 심사관이 심사하는데 걸리는 시간과 사람의 수가 주어졌을 때, 모두가 심사를 받는데 걸리는 시간의 최솟값을 구하는 것이다.문제 요구사항 자체는 복잡하지 않지만 문제는 제한사항이다.입국심사를 기다리는 사람도 매우 많고, 각 심사관이 심사하는데 걸리는 시간도 커서 순회를 해서 구한다기보다는 나누기로 구할 생각을 해야한다. 예를들어 입국 심사관이 각각 5, 7분에 한명씩 심사를 한다고 했을 때 100분동안 심사할 수 ..

이 글은 아래 글을 읽으며 정리한 내용과, 추가로 궁금한 점을 정리한 글입니다.https://mangkyu.tistory.com/286 [MySQL] B-Tree로 인덱스(Index)에 대해 쉽고 완벽하게 이해하기인덱스를 저장하는 방식(또는 알고리즘)에 따라 B-Tree 인덱스, Hash 인덱스, Fractal 인덱스 등으로 나눌 수 있습니다. 일반적으로 B-Tree 구조가 사용되기 때문에 B-Tree 인덱스를 통해 인덱스의 동작mangkyu.tistory.com  B- Tree는 BinaryTree(자식이 2개인 트리)에서 개념을 확장해 n개의 자식을 가질 수 있도록 한 것이다.DB에는 페이지라는 개념이 있는데, 페이지란 디스크와 메모리(버퍼풀)에 데이터를 읽고 쓰는 최소 단위이다. 인덱스와 PK, 테..

현재 의존 관계는 위와 같다. 여기서 memberController만 @Autowired를 이용하고 memberService과 memberRepository는 자바 코드를 이용해 스프링 빈에 직접 등록해보려고 한다. 먼저 memberService와 memberRepository는 각각 아래와 같다.(메서드 생략)public class MemberService { private final MemberRepository memberRepository; public MemberService(MemberRepository memberRepository){ this.memberRepository=memberRepository; }}public class MemoryMemberRepos..

DI와 IoC스프링에는 DI(Dependency Injection, 의존성 주입)이라는 개념이 있다. @Autowired가 있으면 스프링이 연관된 객체를 스프링 컨테이너에서 찾아서 넣어주는 것이다. 또 스프링은 @Component 어노테이션이 있으면 스프링 빈으로 자동 등록하고 이런 객체들의 생성, 설정, 관리를 담당한다. 이렇게 프레임워크(스프링)가 객체의 생성과 생명주기를 관리하는 것을 IoC(Inversion of Control, 제어의 역전)이라고 한다. 이렇게 글로만 읽어서는 잘 와닿지 않는다. 예제를 통해 DI와 IoC에 대해 이해해보도록 하자. 코드를 보기 전 MemberController에서 MemberService객체를 사용하려는 상황이라고 가정하자. 이 경우 아래와 같이 선언해서 사용할..

개발을 하기 전 스프링에서 웹을 개발하는 3가지 방법에 대해 간단히 살펴보도록 하자. 크게 정적컨텐츠, MVC와 템플릿엔진, API 방식으로 나뉜다.정적 컨텐츠실습정적컨텐츠란 서버에서 따로 작업을 하지 않고 그대로 파일을 웹 브라우저에 내려주는 것이다. 정적이라는 말 그대로 바뀌지 않는 컨텐츠이다. main/resources/static폴더에 hello-static.html파일을 생성하고(cmd+n) 아래 코드를 넣어보자. 정적 컨텐츠 입니다.서버를 실행한 뒤 localhost:8080/hello-static.html로 접속하면 정적컨텐츠입니다.라는 화면이 보일 것이다.동작 원리내부적으로는 웹 브라우저에서 localhost:8080/hello-static.html요청이 온 것을 보고 내장된 Tomcat..

스프링부트에는 Maven과 Gradle이 있다. 둘 다 필요한 라이브러리를 땡겨오고 빌드 라이프사이클을 관리해주는 역할을 한다. 요즘은 Gradle을 주로 사용한다. 스프링 라이브러리 자체도 Gradle로 프로젝트를 관리하고 있다. 이 글에서는 스프링부트 프로젝트를 생성하고 빌드하는 방법에 대해 다룬다.⭐ 환경macOS, IntelliJ Untimate 버전에서 진행 1. 프로젝트 생성인텔리제이를 열고 New Project버튼을 누른다. 이후 아래와 같이 설정한다.Language, Type, JDK, Java, Packaging부분을 잘 맞춰줘야 한다.그리고 간단하게 웹 어플리케이션을 실행하기 위해 spring web과 Thymeleaf를 프로젝트에 추가해주도록 하자.참고로 spring boot 어플리케..

컴퓨터 구조의 큰 3가지 요소는 CPU, Memory, I/O이다. 프로그램은 크게 3가지로 나누어 볼 수 있다. Application Software 고급 언어로 작성되어 있다. System Software Compiler(컴파일러): HLL(High-level language)코드를 기계어로 번역한다. Operating System(운영체제): I/O를 관리하고, 메모리와 저장공간을 관리한다. 일들을 스케줄링하고 자원을 공유한다. Hardware Processor, Memory, I/O controllers가 포함된다. 앞서 컴파일러가 HLL을 기계어로 번역한다고 했는데 프로그램 코드는 High-level language, Assembly language, Hardware representation ..

📌C/C++를 테스트하는 프레임워크인 Google test를 M1맥북에서 세팅하는 과정에 대해 다루는 글입니다. 보통 WSL에 깔아서 많이 사용하는데 M1, M2맥북에서는 잘 되지 않는다고 해서 docker를 이용해 환경을 세팅했다. 명령어들은 iTerm에 입력하며 진행했다. 먼저 아래 이미지를 pull 받고 이후 컨테이너를 생성하여 실행한다. https://hub.docker.com/r/srzzumix/googletest/ Docker hub.docker.com docker pull srzzumix/googletest docker run -it -v /$(pwd):/code srzzumix/googletest sh 여기까지 실행했다면 아래와 같이 #으로 시작하는 커맨드라인으로 진입하게 된다. docke..

처리량(throughput) : 링크 내에서 성공적으로 전달된 데이터의 양, bps지연시간(latency) : 요청이 처리되는 시간. 어떤 메시지가 두 장치 사이를 왕복하는데 걸린 시간병목현상(bottleneck) : 전체 시스템의 성능이나 용량이 하나의 구성 요소로 인해 제한 받는 현상네트워크 성능 분석 명령어네트워크 병목 현상은 아래 원인들로 인해 유발될 수 있다.네트워크 대역폭네트워크 토폴로지서버 CPU, 메모리 사용량비효율적인 네트워크 구성만일 네트워크와 관련된 테스트와 관련없는 테스트를 각각 진행한 뒤 문제점이 네트워크와 관련되어있다 라는 결론이 나왔다면 네트워크 성능 분석을 해야한다.ping(Packet INternet Grouper)ping [IP address or Domain addres..