알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 123 / 456 / 780의 순서로 퍼즐을 만들면 되는 문제였습니다. 이때 0을 1~8 이외의 숫자인 9로 정해준뒤 이동시키는 문제였습니다. 따라서 123456789의 순서로 만들어주면 됩니다. -> 123 / 456 / 789 9를 가진 칸은 비어있음을 의미함으로 해당 위치에서 4방향 탐색을 통해서 이동할 수 있는 곳으로 이동합니다. 3*3 배열이기에 위의 과정을 전부 확인해봅니다(브루트 포스) 이동하는 과정에서 123456789의 순서로 나열되는 것이 ..

문제 링크입니다 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 방문한 위치를 1차원 배열이 아닌 2차원 배열을 이용해서 확인해야되는 문제였습니다 문제 접근 방법 1. 현재 가지고 있는 스티커의 갯수를 통해서 3가지의 방법을 확인한다. 2. S개의 이모티콘이 만들어졌을 경우, 시간을 return 한다. 문제 접근 방법 - 1번(BFS() 함수를 참고해주세요) 현재 N개의 이모티콘에서 갈 수 있는 방법은 3가지 입니다. 1. check[N][N]이..

문제 링크입니다 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net BFS를 이용해 갈 수 있는 편의점에 들리면서, 도착점에 갈 수 있는지를 확인하는 문제였습니다. 편의점에 들릴 때마다 맥주의 갯수를 20개로 계속 바꾸어줘야 했습니다. 문제 접근 방법 1. 출발점, 도착점, 편의점의 위치를 pair로 받는다. 2. 위치 + 맥주의 갯수를 담을 수 있는 구조체를 선언한 뒤, 큐로 만들어준다. 3. 출발점에서 N개의 편의점 중, 갈 수 있는 곳을..

Multiplying Out and Factoring Expressions Product - of - Sum 형태로 표현이 주어졌을 때, 분배법칙을 이용해 곱셈 전게를 할 수 있습니다. X(Y + Z) = XY + XZ (X + Y)(X + Z) = X + YZ (X + Y)(X' + Z) = XZ + X'Y

Boolen algebrea - 부울 대수 변수의 값이 true and false 지만, 보통 0과 1로 표현합니다. -> 0과 1은 수치적인 값이 아닙니다. 주요 연산은 AND, OR, NOT이 있습니다. Switching algebra와 Boolean algebra는 주로 교환 가능하게 사용됩니다. /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// Basic Operations 부울 표현식은 하나 이상의 변수 또는 상수를 통해 기본 연산을 적용하여 형성됩니다. 상수 혹은 변수의 간단한 표현은 X, Y', 0과 ..

디지털 시스템의 산술 연산은 일반적으로 이진법으로 수행됩니다. 이진 산술을 수행하는 논리 회로의 설계는 십진수보다 훨씬 쉽기 때문입니다. 덧셈과 곱셈 테이블이 훨씬 간단하다는 점을 제외하면 이진 산술은 십진법과 거의 같은 방식으로 수행됩니다. Binary arithmetic in this unit: +, -, *, / Binary Arithmetic 1. Addition 2. Substraction 3. Multiplication(용어 기억) 4. Division(용어 기억) 우리는 음수값 없이는 뺄 수 없다는 것을 알았으므로 제수를 한 칸 오른쪽으로 이동하고 다시 시도합니다. 10010 에서 11011을 뺐을 때, 111의 값이 나왔습니다. 그래서 몫의 첫번째 부분에 10010의 위에 1을 적어줍니다...

Analog circuits 과 Digital circuits 의 차이점 Analog circuits 전자 시스템이 연속적으로 변하는 신호를 가지고 있다. 신호는 주어진 범위에서 임의의 값을 가진다. 아날로그 시스템은 항상 무작위적 변형과 교란인 노이즈를 포함한다 아날로그 회로는 디자인하기 허려워서 디지털 신호보다 더 많은 숙련도를 요구한다. Digital circuits 디지털 신호는 연속적인 범위(아날로그에서 사용)보다는 분리된 아날로그 범위를 사용한다. 같은 범위 안에 있는 값은 같은 값을 나타낸다. 2개의 값으로 표시된다. GND - 0V , 다른 값은 전원이 공급된다. false -> 0, true -> 1 디지털로 표현된 신호는 noise 때문에 품질저하 없이 이동할 수 있다. 더 많은 이진수..

문제 링크입니다! https://www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net 위상정렬과 DP를 활용해서 최대 점수를 구하고, 경로를 구하는 문제였습니다. 예를 들어 1 -> 2 -> 3 -> 5 or 1 -> 4 -> 7 -> 5의 경로가 있다고 가정하겠습니다. 5번을 도착하기 위해서는 3번과 7번을 거쳐가는 2가지 방법이 있습니다. 이때 최댓값을 구하기 위해서는 3번까지 왔을 때의 값과 7번까지 왔을 때의 값을 비교하면 됩니다. 3번과 7번의 ..

문제 링크입니다! https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1번 PD의 경우 1번 -> 4번 -> 3번 2번 PD의 경우 6번 -> 2번 -> 2번 -> 5번 -> 4번 3번 PD의 경우 2번 -> 3번 순으로 공연을 맡습니다. 1번을 방송하기 위해서는 선행이 없음으로 바로 방송할 수 있습니다. 2번의 경우는 6번을 먼저 방송 후 방송해야 합니다. 3번의 경우는 4번과 2번을 먼저 방송해야 합니다. 따라서 X번 -> ..

문제 링크입니다! https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 그래프를 사용한 DP 문제였습니다. 먼저 지을 수 있는 건물을 지은 다음, 해당 건물을 짓고 난 다음에 지을 수 있는 건물을 지어보는 식으로 최댓값을 찾아가는 문제였습니다. ex) 1 -> X , 2 -> X , 3 -> 2 , 4 -> 1,2 , 5 -> 1,3 (A -> B는 B를 짓고 나서 A를 지을 수 있다는 의미입니다.) 해당 경우, 1번과 2번을 먼저 짓습니..

문제 링크입니다! https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 1. 백조를 먼저 이동시켜본다. 2. 백조가 못만났을 경우 얼음을 녹인다. 3. 1번과 2번을 반복한다. -> 이 방법이 가장 생각하지 쉬운 방법입니다. 하지만 시간초과가 나는 방법이였습니다. 시간 초과가 나지 않는 다른 방법은 1. 백조를 이동시킨다. 2. 백조가 얼음을 만났을 경우 다음 탐색에서 시작할 좌표임으로 큐에 넣어준다. 3. 백조가 못만났..

문제 링크입니다! https://www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net BFS를 이용한 문제였습니다. 완전 탐색을 통해서 파도 -> 모래 확인 -> 이전 모래 확인을 반복한다면, 시간 초과가 나는 문제였습니다. (최악의 경우로서 1000*1000 배열에서 100번만 확인해도 1초가 넘습니다.) -> BFS를 통해서 '.'의 좌표에서 8방향으로 탐색한 뒤, 모래가 전부 사라지는 곳을 다시 BFS에 넣어주는 식으로 진행해야합..