SW사관학교 정글
1.[WEEK01] 특별한 과제
개발 입문비전공자인 상태에서 처음 개발을 접한것은 2021년 초였다. 운이 좋게 교내 IT 동아리에 합격하여 들어갈 수 있었고, 그 곳에서 자바와 안드로이드 스튜디오와 파이어베이스를 이용해 앱을 개발하며 개발에 입문할 수 있었다.그러나 이 한 해 동안은 지금 돌아보면
2.[WEEK01] 미니프로젝트, 알고리즘 1주차
입소와 동시에 구성해주신 3명의 팀원과 함께 3박 4일간의 웹 사이트를 만들어오라는 미니 프로젝트 요구사항을 받게 되었다.어떤 웹사이트를 만들지에 대한 기획 자체는 굉장히 빠르게 진행되었던것 같다. 우리 팀원은 모두 어느정도 개발 경험이 있는 상태였기 때문에, 요구사항
3.[자료구조] Priority Queue(우선 순위 큐)
기본적으로 Heap 구조로 구성되는데, 이 Heap 구조는 이진 트리(binary tree) 형태로 구현된다.예를 들어 Priority Queue 안의 Heap 구조를 출력해보기 위해서는 다음과 같은 함수를 사용하면 된다.이를 출력 하면 다음과 같은 결과를 받아볼 수
4.[알고리즘] 백준1715 카드정렬하기
https://www.acmicpc.net/problem/1715정렬이 되어있는 상태에서 최소값이 구해질 수 있으므로, 힙 정렬을 사용하는 우선순위큐를 heapq 모듈을 이용해 구현한다.먼저 내가 시도했던 방법이다.이렇게 구하면 본문에 나오는 예제 같은 경우
5.[알고리즘] 백준 13334 철로
https://www.acmicpc.net/problem/13334 문제 유형이 우선순위큐로 알고 풀었기 때문에 어느정도 접근은 했던 것 같다. 문제 분류가 우선순위큐로 푸는것임을 몰랐다면 아마 시도하기 어려웠을 것 같다. 아래는 내가 구현한 코드이다 테스트케이스
6.[알고리즘] 백준 8983 사냥꾼
https://www.acmicpc.net/problem/8983최대 10만개의 사대와 10만 마리의 동물이 주어졌기 때문에, 완전탐색으로는 주어진 1초안에 끝내기 어려운 문제였다.처음에는 각 사대의 최대 동물 수를 잡는 문제라고 읽고, 접근조차 못하고 있었다
7.[알고리즘] 파이썬 이진 탐색 모듈 bisect
python docs에 의하면 bisect를 다음과 같이 설명하고 있다.이 모듈은 정렬된 리스트를 삽입 후에 다시 정렬할 필요 없도록 관리할 수 있도록 지원합니다. 값비싼 비교 연산이 포함된 항목의 긴 리스트의 경우, 이는 일반적인 방법에 비해 개선된 것입니다. 이 모
8.[알고리즘] 백준 9935 문자열 폭발
https://www.acmicpc.net/problem/9935자주 볼 수 있는 문자열 관련 스택 문제였지만, 한번도 시도해본적 없느 풀이법을 발견해서 포스팅하게 되었다.이전에는 한 문자에 대해서 어떤 조건에 해당한다면 pop을 시키는 식이었다면, 이번 문제
9.[알고리즘] 백준 1766 문제집 (위상정렬)
https://www.acmicpc.net/problem/17661부터 N까지의 문제가 있고, 각 문제의 선행 문제를 입력받은 뒤 문제에서 주어지는 조건에 맞추어 정렬된 문제 풀이 순서 결과를 출력하는 문제였다.사실 이 문제가 위상정렬이라는 개념을 요한다는것도
10.[알고리즘] 위상정렬(Topology Sort)
위상정렬 위상 정렬이란? > '순서가 정해져있는 작업' 을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 위 그림을 통해 알 수 있는 것은 6번 작업은 4번과 5번 작업 다음에 수행될 수 있다는 것이다. 이 처럼 순서가 정해져 있는 작업에
11.[알고리즘] 크루스칼(Kruskal)
그리디(Greedy) 알고리즘을 기반으로 간선에 가중치를 할당한 그래프의 모든 정점을 최소 비용으로 연결하는 최적해를 구하는 알고리즘이다.최소 신장 트리(Minimun Spanning Tree, MST)를 찾는 알고리즘에 프림 알고리즘과 크루스칼 알고리즘이 사용될 수
12.[알고리즘] 백준 11725 트리의 부모 찾기
https://www.acmicpc.net/problem/11725단순 DFS또는 BFS 문제였지만, 메모리와 시간 제약이 생각보다 깐깐했던 문제였다.처음은 아래와 같이 구현했었는데, 메모리 초과가 났다.메모리 초과를 개선한 코드는 아래와 같다. 기존처럼 2차
13.[알고리즘] 백준 1916 최소비용 구하기 (다익스트라)
https://www.acmicpc.net/problem/1916처음에는 Queue를 이용해서 bfs를 진행하며, 각 노드까지의 거리를 누적한 뒤 마침내 B라는 도착점에 도착했을때 발생할 수 있는 여러 경로의 비용 중 가장 최소값을 탐색이 끝난 뒤 출력하는 식
14.[알고리즘] 백준 1520 내리막길
https://www.acmicpc.net/problem/1520처음에는 보고 전형적인 2차원 리스트를 이용한 DFS 문제라고 생각하였다. 각 경로를 지나가며 현재 칸의 높이와 다음 높이를 비교하여 현재 칸보다 다음 칸의 높이가 낮다면, 다음 재귀 함수를 호출
15.[알고리즘] 백준 11053 가장 긴 증가하는 부분 수열
https://www.acmicpc.net/problem/11053문제를 보고 시간 초과가 날것을 알았지만, DFS로 구현이 가능할 것 같아 시도해보았다. 아래 코드는 DFS로 시간초과를 받은 코드이다.정답은 잘 나오지만, 이 코드의 전체 시간 복잡도는 O(N
16.[알로리즘] 백준 1700 멀티탭 스케줄링
https://www.acmicpc.net/problem/1700처음 문제만 보고는 쉽다고 생각했었다. 처음 내가 생각한 풀이는 다음과 같았다.각 물건 번호를 key로하고, 해당 물건이 사용되는 횟수를 value로 하는 dictionary를 하나 선언한다.이미
17.[알고리즘] 백준 11052 카드 구매하기
https://www.acmicpc.net/problem/11052다이나믹 프로그래밍 문제를 꽤 많이 풀었음에도, 다른 유형에 비해 적응하기가 어렵다고 느끼고 있다.그래서 간단한 문제에서 점화식을 도출하는 과정을 글로 정리해보려 한다.문제는 N개의 카드와 P1
18.[알고리즘] 백준 11660 구간 합 구하기 5
https://www.acmicpc.net/problem/11660누적합을 이용하는 DP 문제이다. 블로그 풀이들을 한참 보아도 이해가 가지 않다가 직접 그려보며 이해한 내용을 정리해보려한다.만약 아래와 같이 2차원 행렬이 주어졌다고 해보자그때 누적합은 아래
19.[알고리즘] 백준 1309 동물원
https://www.acmicpc.net/problem/1309 문제를 처음 보고는 2xn 타일링 문제와 유사하다고 생각하였다. 실제로 유사한 문제였으나 아직 점화식을 정의하는게 어려워서, 올바른 점화식을 도출하는데 어려움을 겪었다. 점화식은 다음과 같이 정의된다
20.[알고리즘] 백준 16236 아기 상어
https://www.acmicpc.net/problem/16236정글에서의 알고리즘 주차는 끝났지만, 개인적으로 매일 알고리즘 한 문제씩은 풀이하려고 한다.그 중에서도 나는 구현 문제에 유독 약하다고 생각해서 구현 문제를 한 문제 골라 풀어보았다.단순 bfs
21.[C언어] 레드-블랙 트리 기본 개념
레드-블랙 트리(Red-Black Tree) 기본 개념 잡기
22.[C언어] 레드-블랙 트리 삽입 연산 구현
이번 포스팅에서는 레드-블랙 트리에서의 삽입 연산이 어떤 과정을 통해 이루어지는지 그림을 통해 각 케이스를 알아보며, c언어로 직접 구현하는 것까지 기록해보려 한다.만약 레드-블랙 트리의 개념에 대해서 잘 모르는 상태라면 레드-블랙 트리 기본 개념 잡기 포스팅을 읽고
23.[알고리즘] 백준 2565 전깃줄
https://www.acmicpc.net/problem/2565 문제를 풀면서 처음 생각했던것은 입력받은 전기줄을 0번 인덱스 또는 1번 인덱스로 정렬한 뒤, 현재 연결된 전깃줄보다 다음 전깃줄 중에서 연결된 전깃줄의 번호가 작다면, 현재 위치에서 제거한 전깃줄의
24.[C언어] 레드-블랙 트리 삭제 연산 구현
본격적으로 포스팅을 시작 하기 전, 만약 레드-블랙 트리의 개념이 익숙하지 않거나 삽입 연산이 어떻게 이루어지는지 모르는 상태라면 아래 포스팅을 통해 간단하게나마 개념을 학습하고 삭제를 학습하는 것을 추천한다. 레드-블랙 트리 개념 잡기 레드-블랙 트리 삽입 연산
25.[C언어] 동적 메모리 할당 개념 잡기
동적 메모리 할당이란 컴퓨터 프로그래밍에서 실행 중(런타임)에 사용할 메모리 공간을 할당하는 것을 의미한다.프로그램이 실행되기 위해서는 메모리가 필요하다. 컴파일러는 컴파일 시점에 소스 코드를 읽고, 변수 타입들의 크기에 따라 메모리를 할당한다. 이처럼 프로그램이 실행
26.[C언어] Malloc-lab 동적 할당기 구현하기
Malloc-lab 동적 할당기(Dynamic Allocator) 구현 이번 포스팅에서는 카네기 멜론 대학교(CMU)의 malloc-lab 이라는 동적 할당기 구현 실습 과제를 구현하는 과정에 대해서 포스팅하려 한다. 만약 동적 할당과 관련된 개념이 익숙하지 않다면 동
27.[알고리즘] 프로그래머스 디펜스 게임
https://school.programmers.co.kr/learn/courses/30/lessons/142085처음에 아무 생각 없이 enemy 리스트를 내림차순 정렬한 뒤 k개를 탐색한 대상들에서 무적권을 사용하면 될 것이라고 생각하였으나, 이 경우 무적
28.[C언어] Web Server 와 WAS(Web Application Server)
Web Server 와 WAS(Web Application Server) 웹 서버와 WAS는 어떠한 차이점을 가지고 있을지 궁금하다면 다음 포스팅을 참고하자 웹 서버와 WAS의 차이 간단하게 소개하자면 웹 서버는 정적 컨텐츠를 다루며, WAS는 동적 컨텐츠를 처리한
29.[네트워크] HTTP(HyperText Transfer Protocol)
HTTP란? > HTML 문서와 같은 리소스들을 가져올 수 있도록 해주는 프로토콜이다. 현대 웹에서 이루어지는 모든 데이터 교환의 기초이자 클라이언트-서버 프로토콜이기도 하다. 클라이언트-서버 프로토콜이란 수신자(서버) 측에 의해 요청이 초기화 되는 프로토콜을 의미한
30.[네트워크] HTTP 통신과 소켓 통신
서버와 클라이언트는 요청과 응답을 주고 받기 위해서 다양한 방법을 사용할 수 있다. 그 중에서 소켓을 이용해서 데이터를 주고 받는 것과 HTTP 요청을 통해서 데이터를 주고 받는 것은 어떤 차이점이 있을까?HTTP는 애플리케이션 계층의 프로토콜이며, 연결은 전송 계층의
31.[pintos] Project 1. Alarm Clock을 구현하며 고민했던 점
드디어 말로만 듣던 스탠포드 대학교의 교육용 os인 pintos를 구현하는 주차에 접어들었다.Project1의 과제 목표는 다음과 같다.Alarm : 호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수핀토스에서 Busy-wating으로 구현되어있는 알람
32.[pintos] Project 1. Priority Scheduling, Syncronization, Donation을 구현하며 고민한 점
두 번째 해결 과제는 기존에 FIFO 방식으로 비선점으로 스레드가 스케쥴링 되던 구조를 Priority를 추가하여 선점이 가능하도록 변경하는 것이었다. 예를 들면 다음과 같다. 기존에는 무조건 처음 들어온 스레드가 가장 먼저 작업을 수행하고, 이후에 새로운 스레드가
33.[pintos] Project 2. USER PROGRAM
앞서 Project 1. Thread 에서는 운영체제에서 스레드간에 동기화와 스케쥴링 등을 직접 만들어보며 익힐 수 있었다. 그렇다면 Project 2. User Program에서는 어떤것들을 공부해볼 수 있을까? Project 2. User Program의 목표 >
34.[pintos] Project 3. Virtual Memory - 개요
가상 메모리 - SPT
35.[pintos] 예외 발생시 핸들러 호출 과정
project 3. virtual memory를 구현하면서. page fault 예외를 처리하기 위한 page_fault() 함수를 열심히 만들었다.page fault는 결국 수 많은 예외 중 하나인데, 어떻게 pintos는 발생한 예외가 page fault인지 판단하