[알고리즘] 문제풀이 모음

개요

---

해당 페이지는 풀었던 알고리즘 문제 링크와 해답, 인사이트를 정리합니다.

(2023 IT 학습 계획 — devNote (tistory.com))에 따른 학습 내용입니다.

 

알고리즘 문제풀이

---

알고리즘은 참고 블로그에서 정리된 커리큘럼 순서대로 공부하고 문제풀이한 기록입니다.

 

Part1. 언어에 익숙해지고, 자유자재로 사용하기

1. 문자열 & 배열 처리
2. 반복문 & 재귀함수(*) 처리
3. 계산복잡도
4. 정렬 처리
5. 완전탐색
6. 정수론

해당 파트에서는 본인이 사용하는 언어(JS, Python, Java 등)의 기본적인 입출력 방식과 자료형, 정렬 방식에 익숙해지는 것을 목표로 합니다.

	출처	문제번호	유형	제목	학습 포인트	날짜
1	백준	2557	입출력	Hello World	언어의 가장 기본적인 출력문 작성 (일단 시작)	01-16
2	백준	10869	입출력	사칙연산	기본 입력문 작성 방법 / 연산의 경우, double로 계산되는 것을 인지하는가? double을 int로 형변환하는 방법	01-16
3	백준	2588	입출력	곱셈	자료형, 자릿수별 출력	01-26
4	백준	2753	조건문	윤년	if else	01-26
5	백준	10871	반복문	X보다 작은 수	반복문 (end와 sep은 덤)	01-26
6	백준	8958	배열	OX퀴즈	인덱스 , 이중for문	01-26
7	백준	4344	배열	평균은넘겠지	소수점 출력	01-26
8	백준	11654	문자열	아스키 코드	아스키 코드는 든든한 국밥	01-26
9	백준	1152	문자열	단어의 개수	split, remove	01-26
10	백준	2869	수학	달팽이는 올라가고싶다	나는 집 가고 싶다(import math)
11	백준	1978	수학	소수 찾기	컴퓨팅 사고
12	백준	10872	재귀함수	팩토리얼	공포의 재귀 시작
13	백준	1914	재귀함수	하노이 탑	print를 어디에 둘까?
14	백준	9663	재귀함수	N-Queen	방문한 지역 체크, 재귀
15	백준	2750	정렬	수 정렬하기	뭐야 쉽네(지옥의 3연벙 시작)
16	백준	2751	정렬	수 정렬하기2	어? 시간초과?(sys.stdin.readline)
17	백준	10989	정렬	수 정렬하기3	어? 메모리초과?(도수정렬)
18	백준	1181	정렬	단어 정렬	글자 크기 순 정렬, 중복제거
19	백준	2390	완전탐색	일곱 난쟁이	permutation, combination
20	백준	10819	완전탐색	차이를 최대로	max, abs, itertools 종합선물셋트

cf. 내가 최종 제출한 답안은 문제 사이트 접속 후, "내 제출" 탭에서 "Node.js"를 선택하면 확인 할 수 있다.

cf. 다른 사람 정답은 "숏코딩" 탭에서 "Node.js"를 선택하면 확인이 가능하다.

# 문제 1. Hello World! 출력

console.log("Hello World!")

# 문제 2. 사칙 연산

let input = "1 2";
// const fs = require('fs');
// const input = fs.readFileSync("/dev/stdin").toString().trim();

let A = parseInt(input.split(" ")[0]);
let B = parseInt(input.split(" ")[1]);
console.log(A+B);
console.log(A-B);
console.log(A*B);
console.log(Math.floor(A/B));
console.log(Math.floor(A%B));

내가 생각하는 Best 답안

• ES6 구조화 분해 문법 사용
• 간결한 import
• Array.map을 통한 간편한 형변환
• console.log 한번에 사용

const [A, B] = require('fs')
  .readFileSync('/dev/stdin', 'utf8')
  .toString()
  .split(' ')
  .map(Number);
console.log(A + B, A - B, A * B, Math.floor(A / B), A % B);

# 문제 3. 곱셈

const [A, B] = require('fs')
               .readFileSync('dev/stdin')
               .toString()
               .split('\n')
               .map(Number);
const [C, D, E] = [A * (B % 10)
    , A * (Math.floor(B / 10) % 10)
    , A * (Math.floor(B / 100) % 10)];
const F = E * 100 + D * 10 + C;
console.log(C, D, E, F);

내가 생각하는 Best 답안 :

• String을 배열처럼 쓰면 CharArray가 된다.
• JS에서는 +(String Concat이 됨)를 제외하고, String (- , / , * , %) String 연산 시 Number로 자동 형변환 한다. 
• Array.forEach(a => console.log(a~))을 통한 간편한 Iteration 

const [a,b]=require('fs').readFileSync('/dev/stdin').toString().split('\n');
[b[2], b[1], b[0], b].forEach(n=>console.log(a * n))

# 문제 4. 윤년

const [year] = require('fs')
              .readFileSync('dev/stdin')
              .toString()
              .split(' ')
              .map(Number);
console.log((year % 4 === 0 && year % 100 !== 0) || year % 400 === 0 ? 1 : 0)

내가 생각하는 Best 답안 :

• 여러개의 input을 받지 않는 경우, 굳이 구조화분해를 할 필요 없음

const year = require('fs')
              .readFileSync('dev/stdin')
              .toString();
console.log((year % 4 === 0 && year % 100 !== 0) || year % 400 === 0 ? 1 : 0)

# X보다 작은 수

const input = require('fs').readFileSync('dev/stdin').toString();
const [N, X] = input.split('\n')[0].split(' ').map(Number);
const A = input.split('\n')[1].split(' ').map(Number);
console.log(A.filter(i => i < X).join(' '));

• JS에서 String을 Number로 형변환 없이 비교연산(<, >, =)을 할 경우, 빈칸 때문에 오동작할 수 있다.
  (형변환 없이 비교연산을 바로 수행하려면, .trim()을 붙여야 한다.)

내가 생각하는 Best 답안

const [n, x, ...arr] = require('fs').readFileSync('/dev/stdin')
                      .toString()
                      .trim()
                      .split(/\s+/)
                      .map(Number);
console.log(arr.filter(num=> num < x).join(' '));

• 적절한 정규식 (\s+ ->스페이스, 탭, 공백문자 1개 이상)을 활용한 불필요한 split 연산 방지
• 적절한 Spread 연산자(...)과 배열 구조화 분해 문법을 활용하여 Input 변수들을 깔끔하게 할당

# OX 퀴즈

const [N, ...ArrList] = require('fs').readFileSync('dev/stdin').toString().trim().split(/\s+/);
ArrList.forEach(arr => {
    let oCount = 0;
    const totalScore = Array.from(arr).reduce((prev_value, item) => {
        if (item === 'O') {
           oCount = oCount + 1;
           return prev_value + oCount;
        } else if (item === 'X') {
           oCount = 0;
        }
        return prev_value;
     }, 0);
    console.log(totalScore);
})

• String을 CharArray로 형변환하기 위해, Array.from(String) 문법을 사용할 수 있다.
• Array를 하나의 축약 Value로 바꾸는 경우, .reduce() 문법을 활용하면 유용하다.
  축약 결과 Value = Array.reduce( (축적변수값, arr[i]값) => { return 다음 축적변수값}), 축적변수 초기값) 
• 몇번 연속되었는지를 확인하는 패턴은 Iteration 문 외부에 Count 변수를 하나 두고, 경우에 따라 + 또는 초기화하는 방법으로 구현할 수 있다.

내가 생각하는 심박한 답:

• 연속된 숫자의 값이  1 + 2 + 3... 형식으로 더해진다는 것에 착안하여, N * (N + 1) / 2 공식을 활용한 것
• Array.shift()를 사용하면, 맨 첫번째 값을 없애면서 가져올 수 있다.
• Array.pop()을 사용하면, 맨 마지막째 값을 없애면서 가져올 수 있다.

const input = require("fs").readFileSync("/dev/stdin").toString().split('\n');
input.shift();
input.pop();
input.map((ox) => console.log(ox.split("X")
				.reduce((acc, cur) => acc + (cur.length * (cur.length + 1)) / 2
                                , 0)
                                ));

1+2+...+N = N*(N+1) / 2

• 출처 : Why does a triangular sequence use this formula Xn = n(n+1) /2? - Quora

# 평균은 넘겠지

const [N, ...testCaseList] = require('fs')
                        .readFileSync('dev/stdin')
                        .toString()
                        .trim()
                        .split('\n')
testCaseList.forEach(testCase => {
    const [n, ...scores] = testCase.split(' ').map(Number);
    const avgValue = scores.reduce(((val, item) => item + val), 0) / n;
    const avgOverCount = scores.reduce(((val, item) => item > avgValue ? val + 1 : val), 0);
    console.log(`${((avgOverCount / n) * 100).toFixed(3)}%`);
})

• JS에서 반올림의 경우, Math.round(Num) 보다 Num.toFixed(자릿수)로 계산하는 것이 더 정확하고 심플하다.
• 위에서 언급하였듯이 배열에서 축약 Value(sum 또는 count If)을 도출해낼 때, reduce를 사용하면 간편하게 계산이 가능하다.

# 아스키 코드

const input = require('fs').readFileSync('dev/stdin').toString().trim();
console.log(input.charCodeAt(0));

• JS에서 String 또는 Char를 Ascii 코드로 바꾸어 연산할 경우, String.charCodeAt(0) 함수를 사용한다.

# 단어의 개수

const input = require('fs').readFileSync('dev/stdin').toString().trim();
console.log(input ? input.split(' ').length : 0);

• JS 상에서, 빈 String을 Split 연산하여도 길이가 1인 배열을 반환하는 사실을 인지하고 있는가?

# 달팽이는 올라가고 싶다

const [A, B, V] = require('fs').readFileSync('dev/stdin').toString().trim().split(' ').map(Number);
console.log(Math.ceil((V - B) / (A - B)))

• 해(X)를 구하는 방정식(등호 또는 비교)을 만들어 활용할 수 있는가?
• 올림 연산을 위해 Math.ceil과 같은 적절한 함수를 이용할 수 있는가?

# 소수 찾기

const [N, ...arr] = require('fs').readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);
const isPrime = (num) => {
    if (num < 2)
        return false;
    if (num === 2) 
        return true;
    return Array.from({length: num - 2}, (v, i) => i + 2)
                .reduce((val, item) => num % item === 0 ? false : val, true);
}
console.log(arr.reduce((val, item) => isPrime(item) ? val + 1 : val, 0));

• 소수의 개념정의(1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수)를 인지하고 있는가?
• 배수인지 약수인지 체크할 때 나머지를 보고 연산한다는 사실을 인지하고 있는가?
• Array.from({length : n}, (value, index) => index ~ )을 통해 연속된 숫자 배열을 만들수 있음을 알고 있는가?

내가 생각하는 인상적인 답

const [N, ...arr] = require('fs').readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);

const isPrime = num => {
	if (num < 2) return false;
	for (let i = 2; i <= Math.sqrt(num); i++) {
		if (num % i === 0) return false;
	}
	return true;
}

console.log(arr.filter(v => isPrime(v)).length);

• 소수 계산 시 수학적으로 2에서 ~ 루트(N)까지만 나눠보고, 딱나눠지지 않으면 소수로 판명할 수 있다.
• reduce 함수를 쓰지 않고도, 배열을 filter 후 length로 값을 도출한 것

# 팩토리얼

const n = Number(require('fs').readFileSync('dev/stdin').toString())
console.log(Array.from({length: n}, (val, index) => index + 1)
				 .reduce((val, item) => val * item, 1));

• 팩토리얼 개념(N! = N* N-1 * ... * 3 * 2 * 1)을 이해하고 있는가?
• 0! = 1이라는 사실도 알고 있는가?
• 빈 배열에 .(reduce((prev_val, item) => next_val, 초기값) 을 쓰면, 초기값을 반환한다.

내가 생각하는 심박한 답안

const n = require('fs').readFileSync('dev/stdin').toString();
const f = n => !n ? 1 : n * f(n-1);
console.log(f(n));

• JS에서 Number형은 0과 NaN의 경우만 False로 인식하는 것을 인지하는가?(-1도 True이다)
• 재귀를 통해서도, 반복 작업을 쉽게 진행할 수 있다는 사실을 인지하는가?

 

Part2. 논리는 맞더라도, 비용 효율적인 코드 작성하기

1. 분할정복 (*, Divide & Conquer)
2. 이분탐색
3. 스택 & 큐
4. 우선순위 큐

 

Part3. 그래프 개념을 통해 복잡한 데이터 관련 문제를 처리하기

1. 그래프(vertex, edge, node, arc) 활용
2. BFS(너비우선) 탐색 알고리즘 활용
3. DFS(깊이우선) 탐색 알고리즘 활용
4. 위상정렬

 

Part4. 재귀, 분할정복은 이해하더라도, 더 효율적인 코드를 작성하기

1. 동적 프로그래밍 기법
2. 그리디 알고리즘 활용

참고

---

 

📚한 장으로 보는 알고리즘 공부 순서📚 (velog.io)