W3: 코드업 기초 100제 70번 대 이후 문제들 중 가장 어려웠던 10문제 write-up 작성하기 코드업 기초 (22.05.02 ~ 22.05.08) 코드업 마지막 과제로 71번부터 99번까지 풀어보았다 이번에는 정답률이 낮은 문제가 이전보다 많았고, 기초임에도 while문 탈출 조건을 제대로 고려하지 못해 틀린 문제가 몇몇 있었다 # 1079: [기초-통합] 원하는 문자가 입력될 때까지 반복 출력하기 [문제] 'q'가 입력될 때까지 입력한 문자를 계속 출력하는 프로그램을 작성해보자 [입력] 문자들이 1개씩 계속해서 입력된다. [출력] q'가 입력될 때까지 입력된 문자를 줄을 바꿔 한 줄씩 출력한다. [풀이] #include int main(){ char input; while(1){ scanf("..
W2: 코드업 기초 100제 70번 이하 문제들 중 가장 어려웠던 5문제 write-up 작성하기 코드업 기초 (22.04.25 ~ 22.05.02) 저번주에 이어서 31~70번 문제를 풀어보았다 이번에는 비트연산자를 복습할 수 있어서 좋았던 것 같다 개인적으로 힌트가 나온 문제들은 최대한 다른 방식으로 풀어보려했다 ㅎ (if-else를 switch로 구현해본다던지,,) # 1038: [기초-산술연산] 정수 2개 입력받아 합 출력하기 1 [문제] 정수 2개를 입력받아 합을 출력하는 프로그램을 작성해보자. (단, 입력되는 정수는 -1073741824 ~ 1073741824 이다.) [입력] 2개의 정수가 공백으로 구분되어 입력된다. ** 주의: 계산의 결과가 int 범위를 넘어가는지를 잘 생각해 보아야 한..
W1: 코드업 기초 100제 20번~30번대 문제들 중 가장 어려운 5문제 write-up 작성하기 코드업 기초100제 (22.04.18 ~ 22.04.24) 과제를 위해서 20-30번만 풀까 아니면 다 풀까 고민했는데 C는 기본중에 기본이고 거의 2년전에 배웠던 언어라서 다시 공부하고자하는 마음에 다 풀어보았다 ~.~ 개인적으로 너무 쉬워서 시간낭비라고 생각할 수도 있지만 알고리즘 말고 C언어 사용 자체에 대한 개념적인 부분들 중 까먹은 것들을 다시 상기시킬 수 있어서 괜찮았다고 생각한다 # 1020 : [기초-입출력] 주민번호 입력받아 형태 바꿔 출력하기 [문제] 주민번호는 다음과 같이 구성된다. XXXXXX-XXXXXXX 앞의 6자리는 생년월일(yymmdd)이고 뒤 7자리는 성별, 지역, 오류검출코..
[문제] Closest Numbers | HackerRank Find the closest numbers in a list. www.hackerrank.com [문제 설명] - 가장 작은 차이를 가지는 두 수의 조합을 담는 벡터를 반환하는 함수를 만들자 [문제 풀이] - 벡터에 있는 수를 오름차순으로 정렬 - for문을 돌면서 두 값의 차이를 구함 > 두 값의 차이가 min과 같다면 새로 만든 벡터에 두 원소를 push > 두 값의 차이가 min보다 작다면 새로 만든 벡터에서 모든 원소를 pop 하고 새로운 두 원소를 push > 두 값의 차이가 min보다 크다면 그냥 넘어감 [코드] vector closestNumbers(vector arr) { sort(arr.begin(),arr.end()); ve..
[문제] 17608번: 막대기 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 www.acmicpc.net [문제 풀이] - 우선 막대기를 입력받으며 stack에 저장 - 하나씩 pop하며 가장 높은 막대기와 비교 - 맨 오른쪽 막대기는 무조건 보이는 것임 [코드] #include #include using namespace std; int top=-1; int stack[100000]; int main() { int tc=0,num=0; int count=0, pre=0, com=0; cin>>tc; cin.ignore(); for(int i=0;i>num; ci..
[문제] Mini-Max Sum | HackerRank Find the maximum and minimum values obtained by summing four of five integers. www.hackerrank.com [문제 설명] - 입력: 5개의 띄어쓰기로 구분되는 숫자 5개를 한 줄로 입력받음 - arr: 주어진 arr에는 5개의 정수 값을 입력받을 수 있음 - 출력: 32bit 정수보다 커야함, 5개의 숫자 중 4개를 골라 가장 작은 합과 가장 큰 합을 출력 [문제 풀이] - 입력 받은 arr를 정렬(버블 정렬 사용)하여 오름차순으로 정리 - for문을 이용하여 두개의 출력 값을 계산 > 가장 합이 작을 때는 인덱스 0~3까지의 합 > 가장 합이 클 때는 인덱스 1~4까지의 합 - 출..
# A Maze Problem - 목표: 입구로부터 출구까지의 경로를 찾음 - 조건: 0은 지나갈 수 있고, 1은 지나갈 수 없음. 직진이나 대각선 방향으로 이동이 가능 > 한 개의 프로그램은 한 개의 미로 경로를 탐색 > 현재 위치에서 이동 가능한 모든 방향 (북쪽부터 시작 → 시계방향으로 이동) 대하여 이동 가능 여부 판단 > 처음 발견한 이동 방향으로 마우스의 좌표를 수정 > 이동 가능한 방향이 없을 경우, 이전 위치로 되돌아감 > 스택을 이용하여 이동했던 위치를 기록하고 이전 위치로 찾아감. 만일 백 트랙을 시도했으나 스택이 비어있다면 결과는 실패 # 미로 찾기 스택 구현 - 구현: 경우의 수를 진행할 때는 스택 안에 쌓고, 벽에 막히면 pop하여 이전 단계까지 돌아옴 # 미로 문제의 특성 - a..
# Matrix (m rows * n cols) - 2차원 배열: matrix[m][n] - Space complixity = S(m,n) = m*n → 얼마만큼의 기억장소를 필요로하는지 나타내는 척도 * 배열이 int 형일 때, S(m,n) = m*n*4 ex) 4 : 배열 안의 원소를 entry라고 하며 배열을 사용해 나타낼 때는 matrix[0][2]와 같이 나타냄 # Sparse Matrix - 희소 행렬: 행렬의 값이 대부분 0인 행렬 → 저장 공간은 큰데 의미있는 값은 적음 - A[m,n]: 대부분의 값이 0이며 이 행렬을 효과적으로 저장하는 방법을 찾아야함 → 중요한 목표 # Sparse Matrix solution - 0이 아닌 element만 저장한다 - 3튜플을 가지는 배열을 활용한다 ..
# 하노이 타워 (1) - 세 개의 기둥과 크기가 다양한 원판들이 존재 > 초기 상태: 한 기둥에 모든 원판이 꽂혀 있음 - 목표: 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥에 옮기는 것 - 조건 ① 한 번에 하나의 원판만 옮길 수 있다 ② 큰 원판이 작은 원판 위에 놓일 수 없다 - 알고리즘 더보기 세 개의 기둥 A, B, C가 있고 기둥 A에서 B로 n개의 원판을 옮긴다고 가정 1. 기둥 A에서 n-1개의 원판을 A, B가 아닌 기둥 C로 옮긴다 2. 기둥 A에 남은 1개의 원판을 B로 옮긴다 3. 기둥 C에 있는 n-1개를 기둥 B로 옮긴다 > 2번 과정: 1개의 원판이 이동하면 됨 > 1, 3번 과정: 원판의 수가 1개 줄어든 또 다른 하노이 타워 문제 → 재귀적인 방법으로 해결 가능 >..
# 유클리드 호제법 - 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나 - 호제법이란? > 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘을 나타냄 - 내용 > 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 함 (이때 a>b) > a와 b의 최대공약수는 b와 r의 최대 공약수와 같음 > 위의 성질에 의해 b를 r로 나눈 나머지 r'을 구하고 다시 r을 r'으로 나눈 나머지를 구하는 과정을 반복함 > 위의 과정에서 나머지가 0이 될 때 나누는 수가 a와 b의 최대 공약수가 되는 것 # 최대 공약수 (greatest common divisor) gcd(x,y) = gcd(s,x%y) if y>0 gcd(x,0) = x - 최대 공약수를 구하는 알고리즘 > y가 0이면 x를 ..