3. 컴퓨터의 연산(모든 것은 덧셈에서 시작한다)

컴퓨터의 CPU는 내부의 디지털 회로를 통해 연산을 수행한다. 이 때 사용되는 디지털 회로는 AND, OR, XOR, NOT이 있다. 컴퓨터의 기본 연산 단위인 2진수 0과 1을 통해 값을 계산하고 자릿수 올림까지 계산한다. 컴퓨터의 덧셈 반가산기 기본적으로 1자리 수 두 개의 입력을 받고 합과 자리올림을 계산한다. 만약 1과 1을 더할 경우 이진수에서는 10이므로 합은 0으로 표현하고 자릿수가 하나 올라갔기 때문에 Carry 값을 1로 표현하게 된다. 즉, 반가산기는 1bit에 대한 연산을 진행하는 계산기이다. 만약, 16진수 연산을 진행해야할 경우, 16진수 한자리는 4bit이므로, 반가산기가 4개 필요하게 된다. 전가산기 만약, 0010과 0011을 더하는 경우 단순히 더하는 연산 뿐만 아니라 그로..

• format_list_bulleted 컴퓨터 구조 및 이론
• · 2023. 7. 28.
• textsms

백준 1620, 두 개의 자료구조를 사용(+ 문자열을 숫자로 바꾸기)

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 해당 문제는 문자열을 입력받으면 숫자를 출력하고, 숫자를 입력받으면 문자를 출력하는 문제이다. 따라서 문자(String)와 숫자(Integer)가 매핑된 자료구조를 사용해야 한다. 만약, String을 Key로 갖고 Integer가 Value인 Map을 활용하면, 문자를 입력받았을 때 숫자를 출력할 수 있다. 하지만 Integer를 입력받았을 경우, 이 자료구조로 문자..

• format_list_bulleted 알고리즘
• · 2023. 7. 26.
• textsms

백준 1012, DFS 연결된 요소 찾기(+ 테스트 케이스 : 배열 초기화하기)

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해당 문제는 1로 연결된 연결 요소의 개수를 찾는 문제이다. 따라서 DFS 알고리즘을 통해 탐색한다. (물론 BFS도 가능하다. 필자는 DFS 재귀 로직을 통해 작성하는 것이 더 간편하다고 생각해서 DFS를 사용하였다.) Key Point 맵이 주어져 있다. -> 2차원 배열을 통해 맵을 구현하고, ny[] / nx[]를 사용한다. DFS 혹은 BFS를 통해 연결되어 있는 노드들을 방문처리 한다. 맵을 방문하..

• format_list_bulleted 알고리즘
• · 2023. 7. 26.
• textsms

백준 2559, 구간합 문제

https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 연속되는 배열의 요소를 더한 값의 최대값을 구하는 문제이다. 연속되는 값을 더하는 문제의 경우 구간합(부분합) 알고리즘으로 접근해야 한다! Key Point 연속되는 수의 합을 구해야 하는 문제이다. -> 구간합(부분합) 알고리즘을 사용한다. 최대값을 구하는 문제이다. -> 최소값을 상수로 결정해야 한다. (해당 최소값과 비교를 통해 최대값을 갱신하기 때문) 만약, 최소값을 구하는 문..

• format_list_bulleted 알고리즘
• · 2023. 7. 25.
• textsms

2. 컴퓨터의 수 체계

컴퓨터가 이해할 수 있는 수는 0과 1이다. 즉, 컴퓨터가 표현하는 수의 단위는 bit이다. 1bit는 0과 1을 표현할 수 있으며, 이를 디지털 표기라고 이해할 수 있다. 1bit = 0,1 총 2가지 표현 가능 2bit = 0,1,2,3 총 4가지 표현 가능 4bit = 0,1,2,3, ... , 14,15 총 16가지 표현 가능 따라서 Nbit는 총 2^N가지의 수를 표현할 수 있으며 최소 값은 0, 최대 값은 2^N - 1이다. 2진수, 16진수 변환 실제 컴퓨터에 표기되는 값들은 2진수가 아닌 16진수인 경우가 대부분이다. 앞서 4bit는 총 16개의 숫자를 표현할 수 있다고 하였다. 따라서 4bit를 하나의 숫자 혹은 문자로 표현할 수 있다. 그것이 바로 16진수이다. 이처럼 2진수 네 자리로..

• format_list_bulleted 컴퓨터 구조 및 이론
• · 2023. 7. 24.
• textsms

백준 2178, 최단거리 BFS 문제 (+ 공백없이 숫자를 입력받는 법)

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해당 문제는 맵이 주어지고, 맵의 처음부터 맨 끝 지점까지 최단거리를 구하는 문제이다. Key Point 맵이 주어져 있다. -> 2차원 배열을 통해 맵을 구현하고, ny[] / nx[]를 사용한다. 그래프의 노드 간 가중치가 모두 동일한 최단거리 문제이다. -> BFS를 사용한 최단거리 알고리즘을 사용한다. 숫자를 공백없이 입력받는 법 1. String 문자열을 사용 cin >> n >> m; for(int i = 0; i <..

• format_list_bulleted 알고리즘
• · 2023. 7. 24.
• textsms