728x90

💡 구조 💡

🔍 컴퓨터 구성 개요

🔍 컴퓨터의 구조

  • CPU: 중앙처리장치. 데이터를 처리하는 역할
  • Memory: 데이터를 저장하는 기능 수행
  • I/O: 컴퓨터와 외부 장치 사이에 데이터를 교환하는 기능 수행
  • System Bus: 위의 모든 컴퓨터 시스템 구성요소들을 연결하여 데이터 전송을 수행

🔍 컴퓨터 시스템

  • 하드웨어: 컴퓨터를 구성하는 기계적인 장치
    하드웨어는 중앙처리장치, 기억장치, 입출력장치로 구성 이들은 시스템 버스로 연결되어 있다.
    시스템 버스는 데이터와 명령 제어 신호를 각 장치로 실어 나르는 역할
    • 중앙처리장치(CPU)
    • 기억장치: RAM, HDD
    • 입출력 장치: 마우스, 프린터
  • 소프트웨어: 하드웨어의 동작을 지시하고 제어하는 명령어 집합
    • 시스템 소프트웨어: 운영체제, 컴파일러
    • 응용 소프트웨어: 워드프로세서, 스프레드시트

🔍 용어정리

중앙처리장치 CPU
인간으로 따지면 두뇌에 해당하는 부분
주기억장치에서 프로그램 명령어와 데이터를 읽어와 처리하고 명령어의 수행 순서를 제어함

  • 중앙처리장치는 비교와 연산을 담당하는 산술논리연산장치(ALU)
  • 명령어의 해석과 실행을 담당하는 제어장치,
  • 속도가 빠른 데이터 기억장소인 레지스터로 구성
    개인용 컴퓨터와 같은 소형 컴퓨터에서는 CPU를 마이크로프로세서라고 부름

기억장치
프로그램, 데이터, 연산의 중간 결과를 저장하는 장치

  • 주기억장치: ROM(Read Only Memory) 비휘발성, RAM(Random Access Memory) 휘발성 속도빠름
  • 보조기억장치: 하드디스크, CD💿, 자기테이프
    레지스터 -> 캐시기억장치 -> 주기억장치(main memory) -> 보조기억장치 (용량🔺, 단순🔺, 저렴🔻, 느림🔻)

입출력 장치

  • 입력 장치: 컴퓨터 내부로 자료를 입력하는 장치 (키보드, 마우스)
  • 출력 장치: 컴퓨터에서 외부로 표현하는 장치 (프린터, 모니터, 스피커)

시스템 버스
하드웨어 구성 요소를 물리적으로 연결하는 선
각 구성요소가 다른 구성요소로 데이터를 보낼 수 있는 통로
용도에 따라 데이터 버스, 주소 버스, 제어 버스로 나눠짐

  • 데이터 버스: 중앙처리장치와 기타 장치 사이에서 데이터를 전달하는 통로
    기억장치와 입출력장치의 명령어와 데이터를 중앙처리장치로 내보내거나,
    중앙처리장치의 연산 결과를 기억장치와 입출력장치로 보내는 '양방향' 버스
  • 주소 버스: 데이터를 정확히 실어나르기 위해서는 기억장치 '주소'를 정해주어야 함
    주소버스는 중앙처리장치가 주기억장치나 입출력장치로 기억장치 주소를 전달하는 통로이기 때문에 '단방향' 버스
  • 제어 버스: 주소버스와 데이터버스는 모든 장치에 공유되기 때문에 이를 제어할 수단이 필요함
    제어버스는 중앙처리장치가 기억장치나 입출력장치에 제어 신호를 전달하는 통로
    신호 종류: 기억장치 읽기 및 쓰기, 버스 요청 및 승인, 인터럽트 요청 및 승인, 클락, 리셋
    제어버스는 읽기 동작과 쓰기 동작을 모두 수행하기 때문에 '양방향' 버스

깃 허브 : 컴퓨터 구조 - 1. 구조

728x90

'Computer Science > Computer Architecture' 카테고리의 다른 글

6. 파이프라이닝  (0) 2023.06.27
5. 패리티비트 & 해밍코드  (0) 2021.08.02
4. 고정소수점 & 부동소수점  (0) 2021.08.02
3. Cache Memory  (0) 2021.07.20
2. CPU  (0) 2021.07.18
728x90

[문제]

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

[문제 풀이]

입력을 배열로 받고 오름차순으로 정렬한다. 1 2 3 4 5 라고 하면

각각의 대기 시간은 아래와 같다.

1번째 사람: 1

2번째 사람: 1+2

3번째 사람: 1+2+3

4번째 사람: 1+2+3+4

5번째 사람: 1+2+3+4+5

따라서 1*5 + 2*4 + 3*3 + 4*2 + 5 한 결과가 답이 된다.

코드로 표현하면 아래와 같다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] arr;

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = stoi(br.readLine());

        arr = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            arr[i] = stoi(st.nextToken());
        }

        Arrays.sort(arr);

        int ans = 0;
        int n = N;
        for (int i=0; i<N; i++, --n) {
            ans += arr[i] * n;
        }
        System.out.println(ans);
    }
}

[실행 결과]

실행 결과는 위와 같다.

728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

[BOJ] 1654 랜선 자르기 - Java  (0) 2021.07.14
[BOJ] 1931 회의실 배정 - Java  (0) 2021.07.14
[BOJ] 10799 쇠막대기 - Java  (0) 2021.07.14
[BOJ] 10828 스택 - Java  (0) 2021.07.14
[BOJ] 1158 요세푸스문제 - Java  (0) 2021.07.14
728x90

여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.

  • 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
  • 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
  • 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다. 

아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.

이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.

  1. 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 ‘( ) ’ 으로 표현된다. 또한, 모든 ‘( ) ’는 반드시 레이저를 표현한다.
  2. 쇠막대기의 왼쪽 끝은 여는 괄호 ‘ ( ’ 로, 오른쪽 끝은 닫힌 괄호 ‘) ’ 로 표현된다. 

위 예의 괄호 표현은 그림 위에 주어져 있다.

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다. 

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

[문제 풀이]

스택문제로 분류되어 있었지만 스택으로 문제를 해결하지 않았다.

'(' 에서는 cnt를 하나씩 증가시켜주고

')' 에서는 이전의 값을 보고 결정한다.

이전에서 '(' 였으면 () 이므로 레이저이다. 그래서 쇠막대기가 짤리므로 ans를 증가시킨다.

이전에서 ')' 였으면 )) 으므로 막대기의 끝을 의미한다. 따라서 ans를 1증가시켜준다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	static String s;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		s = br.readLine();
		int cnt = 1;
		int ans = 0;
		
		for (int i=1; i<s.length(); i++) {
			if (s.charAt(i) == '(') {
				cnt++;
			} else {
				if (s.charAt(i-1) == '(') {
					//()인 경우 레이저
					--cnt;
					ans += cnt;
				} else {
					//))인 경우 막대기 끝
					--cnt;
					ans++;
				}
			}
		}
		System.out.println(ans);
	}
}

[실행 결과]

실행 결과는 위와 같다.

728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

[BOJ] 1931 회의실 배정 - Java  (0) 2021.07.14
[BOJ] 11399 ATM - Java  (0) 2021.07.14
[BOJ] 10828 스택 - Java  (0) 2021.07.14
[BOJ] 1158 요세푸스문제 - Java  (0) 2021.07.14
[BOJ] 10845 큐 - Java  (0) 2021.07.14
728x90

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

  • push X: 정수 X를 스택에 넣는 연산이다.
  • pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 스택에 들어있는 정수의 개수를 출력한다.
  • empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
  • top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

[문제 풀이]

이전 큐 문제와 거의 동일한 문제이다.

참고: https://dos-soles.tistory.com/2?category=873473

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static Stack<Integer> stack = new Stack<>();

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        N = stoi(br.readLine());

        while (N-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch (st.nextToken()) {
                case "push":
                    stack.push(stoi(st.nextToken()));
                    break;
                case "pop":
                    if (stack.isEmpty()) {
                        sb.append("-1").append("\n");
                    } else {
                        sb.append(stack.pop()).append("\n");
                    }
                    break;
                case "size":
                    sb.append(stack.size()).append("\n");
                    break;
                case "empty":
                    if (stack.isEmpty()) {
                        sb.append("1").append("\n");
                    } else {
                        sb.append("0").append("\n");
                    }
                    break;
                case "top":
                    if (stack.isEmpty()) {
                        sb.append("-1").append("\n");
                    } else {
                        sb.append(stack.peek()).append("\n");
                    }
                    break;
            }
        }
        System.out.println(sb);
    }
}

[실행 결과]

속도는 위와 같다.

728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

[BOJ] 1931 회의실 배정 - Java  (0) 2021.07.14
[BOJ] 11399 ATM - Java  (0) 2021.07.14
[BOJ] 10799 쇠막대기 - Java  (0) 2021.07.14
[BOJ] 1158 요세푸스문제 - Java  (0) 2021.07.14
[BOJ] 10845 큐 - Java  (0) 2021.07.14
728x90

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

[문제 풀이]

이번 문제에서는 큐 구현을 LinkedList로 구현하였다.

1부터 n까지 q.add(i)을 해주고 인덱스는 0부터 시작하므로 k-1일 해주었다.

한바뀌 돌며 빠져야 하는 값 r = (r-1+k) % list.size() 가 된다.

값이 다 빠지고 queue.isEmpty가 true가 되면 반복문을 빠져나온다. 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    static int n, k;
    static LinkedList<Integer> list = new LinkedList<>();

    public static int stoi(String s) {
        return Integer.parseInt(s);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        k = stoi(st.nextToken());

        for (int i=1; i<=n; i++) {
            list.add(i);
        }

        int r = k-1;
        sb.append("<");
        while (!list.isEmpty()) {
            sb.append(list.get(r)).append(", ");
            list.remove(r);
            if (list.size()==0) break;
            r = (r-1 + k)%list.size();
        }
        sb.setLength(sb.length()-2);
        sb.append(">");
        System.out.println(sb.toString());
    }
}

 

[실행 결과]

결과는 위와 같다.

728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

[BOJ] 1931 회의실 배정 - Java  (0) 2021.07.14
[BOJ] 11399 ATM - Java  (0) 2021.07.14
[BOJ] 10799 쇠막대기 - Java  (0) 2021.07.14
[BOJ] 10828 스택 - Java  (0) 2021.07.14
[BOJ] 10845 큐 - Java  (0) 2021.07.14
728x90

[문제]

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

  • push X: 정수 X를 큐에 넣는 연산이다.
  • pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • size: 큐에 들어있는 정수의 개수를 출력한다.
  • empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
  • front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
  • back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

[문제 풀이]

큐를 사용하는 문제이다.

자바에서 Queue를 사용하는 방법으로 Deque, Queue, LinkedList가 있는데 이 문제를 풀때는 Deque 사용!

Switch 구문을 이용해서 input 별로 처리해 주었다.

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

	static Deque<Integer> q = new ArrayDeque<Integer>();
	static int N;
	static String order;

	static int stoi(String s) {
		return Integer.parseInt(s);
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = stoi(br.readLine());
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			order = st.nextToken();

			switch (order) {
			case "push":
				q.offer(stoi(st.nextToken()));
				break;
			case "pop":
				if (q.isEmpty()) {
					sb.append("-1").append("\n");
				} else {
					sb.append(q.poll()).append("\n");
				}
				break;
			case "size":
				sb.append(q.size()).append("\n");
				break;
			case "empty":
				if (q.isEmpty()) {
					sb.append("1").append("\n");
				} else {
					sb.append("0").append("\n");
				}
				break;
			case "front":
				if (q.isEmpty()) {
					sb.append("-1").append("\n");
				} else {
					sb.append(q.peek()).append("\n");
				}
				break;
			case "back":
				if (q.isEmpty()) {
					sb.append("-1").append("\n");
				} else {
					sb.append(q.peekLast()).append("\n");
				}
				break;
			default:
				break;
			}
		}
		System.out.println(sb);
	}
}

[실행 결과]

사용한 메모리와 시간은 다음과 같다.

728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

[BOJ] 1931 회의실 배정 - Java  (0) 2021.07.14
[BOJ] 11399 ATM - Java  (0) 2021.07.14
[BOJ] 10799 쇠막대기 - Java  (0) 2021.07.14
[BOJ] 10828 스택 - Java  (0) 2021.07.14
[BOJ] 1158 요세푸스문제 - Java  (0) 2021.07.14

+ Recent posts