![]()
벌써 예선을 치른 지 1달이 다 되어가지만.. 더 늦으면 완전히 까먹어버릴까 봐 여기 기록을 해둬야겠다. 보통 이런건 한 7문제씩 푼 사람들이 쓰지만 ㅠㅠ 상승 곡선을 그리기 위해 올해부터 적는다! 아직 2학년이라 올해 처음 acm에 참가하였지만, 우리 학교가 워낙 알고리즘 불모지이기 때문에 학교에서 참가한 팀은 우리 팀 밖에 없어 우리가 자동으로 학교 1위 팀이 되었다. (해당 과목 교수님은 정말 대단하신데 ㅠㅠ) 덕분에 모자란 실력에도 불구하고, 본선을 목표로 공부했고 팀원들 모두 어느 정도 본선은 갈 것이라 생각했다. (결과는 뒤에 나와요 ㅎㅎ) 잠깐 참가하게 된 과정을 말해보자면.. 나는 작년에 PS(Problem solving)를 처음 접했고, 작년 2학기에 c++을 배우고 겨울부터 본격적으로 ..
![]()
이번엔 ARM 어셈블리 코드로 작성한 파일을 디버깅하는 방법에 대해 알아보겠습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 @ suhwan++20201108 @ debug practice .text _start: .global _start mov r1, #0 loop: cmp r1, #10 bge exit add r1, r1, #1 b loop exit: mov r0, #0 mov r7, #1 swi 0 .end cs 먼저, 이번에 사용할 코드입니다. 아주 단순하게 1부터 10까지 r1을 +1씩 증가시키고, 10이 되면 프로그램을 종료하는 코드입니다. 1. 디버그 옵션 설정 -> 디버그 옵션은 as(오브젝트 파일로 변환)할 때 "-g" 옵션을 설정하면 ..
![]()
이번엔 미리 버퍼에 저장해둔 문자열을 출력해봅시다! 순서는 다음과 같습니다. 1) 문자열의 주소(맨 앞 포인터)를 레지스터에 담습니다.(adr 명령어 사용) 2) 포인터를 하나씩 증가시키면서 바이트 단위로 로드해서 출력합니다. 3) 위 과정을 문장이 끝날 때까지 반복합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 @ suhwan++20201108 @ write sentence .text _start: .global _start adr r3, msg @ r3
![]()
본 포스팅에서는 sp(stack pointer)를 이용해 항상 .data 밑에다가 자잘하게 써왔던 버퍼를 대체하는 것을 보여드립니다! 1. 기존 버퍼 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 @ suhwan++20201108 @ system call test .text _start: .global _start @ sys_read (fd, pstr, len); @ r0 r1 r2 mov r0, #0 @ fd
![]()
arm assembly 코드를 짜면서 자주 사용하지만 항상 헷갈리는 system call에 대해 정리해봅니다. 코드에 대한 대략적인 설명은 @(주석)에 쓰여 있습니다! 0. 기초 아래 코드에서 공통되는 내용입니다. fd File Descriptor의 약자이며, 리눅스에서 프로세스가 파일을 다룰 때 사용하는 개념으로, 간단히 파일에 접근을 어떻게 할 것인지 지정하는 역할을 합니다. pstr 포인터입니다. 보통 버퍼의 앞 부분을 가리키는 데에 사용하며, 주소 값을 갖습니다. len 버퍼의 길이를 의미합니다. swi swi(software interrupt)는 어떤 장치가 다른 장치의 일을 잠시 중단시키고 자신의 상태 변화를 알려 주는 것입니다. 아래 코드에서는 잠깐 멈춰 입출력 혹은 종료를 하도록 합니다. ..
![]()
문제 링크 : https://www.acmicpc.net/problem/1946 문제 분류 - 그리디 알고리즘 풀이 우선 문제를 읽고, 지원자의 숫자 N의 제한이 10만이라는 점을 보고 빠르게 O(n^2)로 모든 지원자들을 계속해서 비교해나가는 풀이는 포기했다. 그렇다고 O(nlgn)의 방법으로 이분탐색을 하자니.. 딱히 절반 절반 줄여나갈 포인트가 생각이 안 났고 그다음 생각난 것이 아래와 같은 풀이이다. 먼저, 입력에서 각 지원자들의 성적 순위가 주어졌기 때문에 본능적으로 무언가 정렬을 해야 할 듯하다. 따라서 정렬을 하고 보니 두 성적 중 아무 성적이나 1위를 하고 있는 신입 사원은 어떻게 뽑든 반드시 선발되기 마련이다. 만약 성적이 (1, x)인 신입 사원이 선발이 되지 않았다면, 선발될 수 있는..
![]()
그리디 알고리즘(Greedy Algorithm)은 "탐욕적인"이라는 뜻의 greedy에서 유래된 알고리즘이다. 다른 말로 "욕심쟁이 기법" 이라고도 부르는데 만약 여러 노드를 갖는 그래프에서 A노드 -> B노드까지의 경로를 탐색하려 할 때 모든 경로를 고려하지 않고 단지, 현재의 위치(노드)에서 가장 최적의 경로(예를 들면 에지의 가중치가 작은) 를 도착지까지 매 순간마다 가장 좋은 방법만을 선택하는 방법이다. 다익스트라 알고리즘도 그리디 알고리즘의 한 예시인데 간단히 설명하자면, 한 노드를 시작점으로 출발해 목적지에 연결될 때 까지 현재 연결된 노드로부터 연결된 에지들의 가중치 중 최소만을 선택하는 방법을 말한다. (사이클이 생기지 않는 선에서) 만약 위 그림에서 노드 1->6 까지의 최단 거리를 구하..
우리가 보통 행렬의 곱셈을 구현하기 위해서는 n x n 행렬이 A, B가 있을 때 주어진 행렬의 모든 원소(n^2 가지)에 대해 A행렬의 가로, B행렬의 세로를 곱해줘야 하기 때문에 O(n^3) 번의 연산이 필요하게 된다. 이렇게 되면 n이 조금만 커져도, 또는 거듭제곱의 수가 조금만 커져도 필요한 연산의 수가 매우 크게 증가하기 때문에 연산의 수를 줄이는 알고리즘이 필요하다. 우리는 이 문제를 분할 정복(divide & conquer)로 해결할 수 있는데 예를 들어 행렬 A를 m번 거듭 제곱한다 하면, A^(m) = A^(m/2) * A^(m/2)로 나눌 수 있다는 점을 이용한다. (행렬의 곱셈법칙에 따라서) 만약 A^8 를 구하기 위해 곧이곧대로 A를 7번 곱하게 되면 연산은 총 7 * n^3번 해야..
![]()
본 내용은 Computer networking : a top-down approach 책을 바탕으로 정리하였습니다. Index 1. 링크 가상화 : MPLS 2. 데이터 센터 네트워킹 3. 총정리 드디어 프로토콜 스택의 마지막 포스팅이다! 이 다음 포스팅부터는 1~15까지 배운 내용을 토대로 예시 문제를 통해 복습해볼 예정이다. 1. 다중 프로토콜 레이블 스위칭 : MPLS 다중 프로토콜 레이블 스위칭(Multiprotocol Label Switching, MPLS)은 가상회선 네트워크의 주요 개념인 고정 길이 레이블을 도입함으로써 라우터의 전달속도를 향상시키기 위해 발전해왔다. MPLS의 목표는 고정 길이 레이블과 가상회선을 기반으로 데이터그램을 전달하기 위해서 데이터그램을 선택적으로 레이블링해서 라우..
![]()
본 내용은 Computer networking : a top-down approach 책을 바탕으로 정리하였습니다. Index 1. addressing, ARP 2. Ethernet 3. switches 4. VLANS 앞 장에서는 브로드캐스팅과 다중 접속 프로토콜(multiple access)에 대해 다루어보았고, 이제 링크 계층에서의 스위치 근거리 네트워크에 대해 설명해보려 한다. 우선, 스위치 네트워크에서는 링크 계층 프레임을 전달하기 위해서 IP 주소가 아닌 링크 주소(MAC address)를 사용한다는 것을 다시 한번 상기해보자. 이번 장에서는 링크 계층 주소체계와 이더넷 프로토콜, 링크 계층 스위치에 대해 살펴볼 예정이다. 1. addressing, ARP 호스트와 라우터들은 네트워크 계층 주..
![]()
본 내용은 Computer networking : a top-down approach 책을 바탕으로 정리하였습니다. Index 1. link layer 소개 2. link layer services 3. 오류 검출 및 정정 기술 4. 다중 접속 링크와 프로토콜 5. CSMA, CSMA/CD 프로토콜 1. link layer 소개 드디어 링크 계층까지 왔다!! 앞에서는 네트워크 계층이 호스트 사이에서 통신 서비스를 제공하는 것까지 살펴보았다. 이번엔 네트워크 계층에서 내려와 링크 계층에서 개별 링크를 따라 패킷이 어떻게 전달되는지 살펴볼 것이다. 먼저 몇 가지 용어에 대해 정리해보자. 노드 : 호스트, 라우터, 스위치 등이 노드가 될 수 있다. 링크 : 인접한 노드들을 연결하는 통신 채널로 유. 무선, L..
![]()
본 내용은 Computer networking : a top-down approach 책을 바탕으로 정리하였습니다. Index 1. SDN 2. OpenFlow 1. SDN 개요 SDN은 software defined network의 약자로 기존에 자유롭게 활동하던 라우터들을 한데 묶어 중앙 집중형으로 컨트롤하게 하는 네트워크 가상화 접근 방식이다. SDN은 그전에 network layer에서 배운 컨트롤 플레인과 데이터 플레인을 분리하고, 물리적 장비와 구분되는 소프트웨어 프로그래밍 가능한 인프라를 생성하면서 구현된다. 1.1 왜 중앙 집중형 컨트롤 플레인일까? 중앙 집중 시, 네트워크를 관리하기 쉬워지고, 트래픽 흐름이 매우 유연해진다. 예시로, 기존 상태인 경우 한쪽 경로가 빠르기 때문에 모두 그쪽..
