분류 전체보기

    자 드가ㅈㅏ

    자 드가ㅈㅏ

    부산대 뭐든지 해봐 사업에 선정되었다! 이 프로젝트를 지원받으면서 하게될 줄은 상상도 못했다 ㄴㅇㄱ 운이 좋은거같다^0^ 11월 말까지 프로그램을 완성 시켜야 한다! 가즈아ㅏㅏ 그리고 네이버 소프트웨어야놀자 대학생 멘토단에 우리 동아리 PROJECT가 선정되었다. 다음주에 필요한 교육 이수하고, 9월부터 1월 말까지 열심히 활동하겠다! 일을 많이 벌렸다.. 할 수 있겠지.. 할 수 있을거야 혼잣말 여기까지

    [백준 11779] 최소 비용 구하기 2 C++

    [백준 11779] 최소 비용 구하기 2 C++

    11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 A 도시에서 B 도시로 가는 최소 비용을 알아야 한다. 간선의 비용은 음수가 없다. 위 두가지 정보로 다익스트라문제인걸 알았다. 다익스트라 알고리즘에 의해서 도착점을 발견하면 현재 가지고 있는 최소 비용이 도착점 까지의 비용이된다. bfs를 수행하면서 현재 정점에 도달하기 직전에 거쳐온 정점을 저장해둔다. 예시 입력을 그래프로 나타냈다. 1이 시작점이고 우선순위 큐에 의해서 queue에 4, 2,..

    [OS] Scheduling #1

    [OS] Scheduling #1

    Scheduling 지금까지 프로세스와 스레드에 대해 알아보았다. 오늘 내일은 프로세스의 CPU Scheduling에 대해서 알아보자 CPU Scheduling은 크게 2가지로 나뉜다 비선점형 스케줄링(Non-preemptive scheduling)과 선점형 스케줄링(Preemptive scheduling) 비선점형 스케줄링 - CPU가 프로세스를 실행하고 있다면 실행중인 프로세스가 종료되거나 스스로 CPU를 양보하기 전까지 다른 프로세스는 CPU는 사용할 수 없다. - 프로세스들 간의 협력이 중요하다. 선점형 스케줄링 - 사실상 모든 현대 스케줄러가 선점형이다 - 다른 프로세스가 CPU를 사용하고 있어도 강제로 프로세스를 쫓아내고 자신이 CPU를 사용할 수 있다. 스케줄링 알고리즘의 성능을 판단하는 척..

    [백준 14003] 가장 긴 증가하는 부분 수열5 C++

    [백준 14003] 가장 긴 증가하는 부분 수열5 C++

    14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이분 탐색 1. 문제 해결 아이디어 [백준 12015] 가장 긴 증가하는 부분 수열2 C++ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀.. hyeo-noo.tistory.com 위 문제에서 추가적인 요소만 넣어준다면 해결 ..

    [OS] Thread #1

    [OS] Thread #1

    Thread 스레드가 뭘까? 왜 있는걸까? 싱글 프로세스는 멀티코어 CPU의 장점을 활용할 수가 없다. 새로운 프로세스를 만드는데는 많은 자원이 필요하다. (시간, 메모리 공간) 프로세스간의 통신 오버헤드가 크게 발생한다. 프로세스간에 context swiching 비용이 크다. 위와 같은 프로세스의 단점을 보완하기 위해서 스레드가 탄생했다. 하나의 프로세스는 여러개의 스레드를 가질 수 있다. 프로세스는 각자의 고유 메모리를 가지고 있기 때문에 프로세스 내부의 스레드들은 하나의 메모리 공간을 공유한다. 그리고 스레드는 각자의 program counter와 stack pointer를 가진다. 위 사진처럼 스레드가 많아질 수록 프로세스의 메모리 공간이 각각의 stack공간으로 채워짐을 알 수 있다. 그리고 ..

    [백준 3055] 탈출 C++

    [백준 3055] 탈출 C++

    3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 1. 문제 해결 아이디어 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 위 문제랑 거의 똑같은듯 하다 고슴도치는 물이 곧 차오를 지역으로 가지 못하기 때문에 bfs를 통해서 물을 먼저 채워준다 이때 채워진 물을 nextwater 큐에 넣어준다. 물은 . 부분에만 채워질 수 있다. 물..

    [OS] Process #3 (Context Switching)

    [OS] Process #3 (Context Switching)

    Process의 context switching 우리는 컴퓨터가 다양한 프로그램을 동시에 실행시켜주는 것처럼 느낀다. 엄밀히 따지면 동시 실행이 아니다. CPU가 매우 빠른 속도로 프로세스들을 context switching을 시켜주는데 우리는 이 switching 순간을 절대로 느낄 수 없다. Context란? 프로세스가 수행되기 위해서 필요한 정보들이라고 이해하면 된다. Context는 주로 커널 내부에 존재하는 PCB(Process Control Block)에 저장되어 있다. (PCB는 linked list로 구성됨) 우리가 프로그램을 구동시키기 위해서는 프로세스를 생성해야 한다. 프로세스가 생성되면서 해당 프로세스만의 메모리 공간을 할당 받고 code, stack, heap, BSS 공간에 적절한..

    [OS] Process #2

    [OS] Process #2

    Process 프로세스의 상태 전이 표 프로세스는 Ready 상태일때 CPU를 할당받고 Running 상태로 상태전이가 일어난다. 이제 해당 프로세스는 CPU를 이용해 작업을 수행한다. 작업을 마치면 CPU를 반납하고 종료합니다. 만약 작업이 끝나지 않는경우 프로세스는 CPU를 반납하고 ready 상태로 다시 돌아간다. 만약 I/O 작업이 발생한다면 현재 CPU를 사용중인 프로세스는 Block 상태로 전이가 일어난다. I/O작업이 완료되면 해당 프로세스를 ready상태로 전이 시킨다. 작업이 종료되지 않았는데 CPU를 어떻게 반납을 할까? OS는 프로세스의 CPU독점을 방지하기 위해서 하드웨어로 구현된 timer interrupt를 발생시켜 프로세스가 특정 시간 간격동안만 실행할 수 있도록 한다. tim..

    [백준 14891] 톱니바퀴 C++

    [백준 14891] 톱니바퀴 C++

    14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 시뮬레이션 삼성 SW 기출 1. 문제 해결 아이디어 하나의 톱니가 돌아가면 다른 톱니도 돌아가야하므로 연쇄반응을 구현해야한다. 재귀로 풀어내려고 했고 현재 바퀴를 시계/반시계 방향으로 회전시키기 전의 3시, 9시 방향의 자기정보를 가지고 있어야 한다. 현재 영향을 주는 방향을 매개변수로 입력받아서(lr) (0은 양방향, 1은 오른쪽으로, -1은 왼쪽으로) 영향을 줄 바퀴를 정해서 함수를 호출했다. 로직은 이게 전부인듯 하다. 삼성 SW기출답게 구현력을 요구하는..

    [백준 6087] 레이저 통신 C++

    [백준 6087] 레이저 통신 C++

    6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net BFS 1. 문제 해결 아이디어 처음에 시뮬레이션 문제인가? 생각했는데 그냥 BFS에 조건이 몇 개 추가된 문제였다. 먼저 DP풀듯이 각 칸에 도달하기 위한 최소 거울의 개수를 구해야 겠다는 생각을 했다. 그리고 이미 방문한 칸에 다시 도달할 수 있어야 올바른 최솟값을 구할 수 있다고 깨달았다. 가장 기본적으로, 주어진 W, H 범위 내에서만 움직여야하고, 벽인 경우 que에 넣으면 안된다. que의 초기값이 하나의 점이 아니라 임의의 C에서 4방향으로..