tenid's dev

1. 문제 설명

String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다.  

- 제한 사항

• seoul은 길이 1 이상, 1000 이하인 배열입니다.
• seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다.
• "Kim"은 반드시 seoul 안에 포함되어 있습니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> seoul) {
	string answer = "김서방은 ";

	for (int i = 0; i < seoul.size(); i++) {
		if (seoul[i] == "Kim") {
			answer += to_string(i) ;
			break;
		}

	}
    
	return answer+="에 있다";
}

3. 정리

for문을 이용하여 배열을 순회하여 "Kim" 문자열이 있는 인덱스를 찾아낸다.

전체 시간 복잡도를 단계별로 분석하면

최종적으로 O(n) 이다.

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12919

1. 문제 설명

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> absolutes, vector<bool> signs) {
	int answer = 0;

	for (int i = 0; i < absolutes.size(); i++) {
		bool sign = signs[i];

		sign == true ? answer += absolutes[i] : answer -= absolutes[i];
	}

	return answer;
}

1. 문제 설명

양의 정수 x가 하샤드 수이려면 x의 자릿수의 합으로 x가 나누어져야 합니다. 예를 들어 18의 자릿수 합은 1+8=9이고, 18은 9로 나누어 떨어지므로 18은 하샤드 수입니다. 자연수 x를 입력받아 x가 하샤드 수인지 아닌지 검사하는 함수, solution을 완성해주세요.

- 제한 조건

• x는 1 이상, 10000 이하인 정수입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

bool solution(int x) {
    bool answer = true;
    int sum = 0;

    for(int temp = x; temp > 0; temp/=10)
    {
        sum += temp % 10;
    }
    
	return x % sum == 0 ? true : false;

}

3. 정리

10과 나머지 연산 후 결과는 항상 1의 자릿수의 값이다. 그리고 10과 나누기 연산 후 결과는 해당 수의 자릿수가 감소한다. 이 점을 이용하여 자릿수의 총합(sum)을 구한 후 x와 하샤드 수인지 아닌지를 판별한다.

전체 시간 복잡도는 for문이 자릿수( log10(x) + 1 )만큼 반복하므로  O(log x) 이다.

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12947

1. 문제 설명

임의의 양의 정수 n에 대해, n이 어떤 양의 정수 x의 제곱인지 아닌지 판단하려 합니다.
n이 양의 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, n이 양의 정수 x의 제곱이 아니라면 -1을 리턴하는 함수를 완성하세요. 

- 제한 사항

• n은 1이상,  50,000,000,000,000 이하인 양의 정수입니다.

2. 풀이 코드

#include <string>
#include <vector>

using namespace std;

long long solution(long long n) {
    long long answer = 0;
    
    long long i;
    for(i=1 ; i*i <= n ; i++);
    
    if((i-1)*(i-1) == n) answer = i*i;
    else answer = -1;
    
    
    return answer;
}

3. 정리

사용하는 변수는 50,000,000,000,000 값의 범위가 int형이 표현하는 값의 범위를 초과하기 때문에 long long을 사용하며 for문을 이용하여 i 변수를 제곱근+1까지 실행한다. 이후에 i-1 = 제곱근, (i-1)*(i-1)이 n값과 일치 하다면  정답을 저장하는 변수에 i*i = (제곱근+1)* (제곱근+1) 값을 일치하지 않는다면 -1을 대입한다.

전체 시간 복잡도는 for문이 제곱근만큼 반복 하므로 O(√n) 이다.

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/12934

• 어떠한 집합에서  정해진 기준에 따라 원소의 순서를 선택하는 문제를 푸는 문제에 적합 ex) 순열
• 깊이우선탐색 (DFS)
• 모든 문제에 대해서 효율적인 알고리즘이라고 보장할 순 없으나 대부분의 문제 사례에 대해 효율적이다.
• ex) n-Queens, 부분집합의 합, 0-1 배낭문제 등

미로찾기의 경우 길을 찾다가 갈림길에서 먼저 특정한 방향으로 탐색을 시작한다. 그러다가 막힌 길이 나오는 경우 왔던 길을 다시 돌아와서 갈림길에서 다른 경로를 선택하여 탐색한다. 

# 상태공간트리

- 상태 공간: 해답을 탐색하기 위한 탐색 공간

- 상태공간트리: 탐색 공간을 트리 형태의 구조로 암묵적으로 해석

# 백트래킹 기법

상태공간트리를 깊이우선탐색으로 탐색하고, 방문 중인 노드에서 조건에 의해 더 하위 노드를 탐색하여도 해답이 없다고 판단이 된다면 하위트리를 방문하지 않고 부모 노드로 되돌아 간다. - 가지치기(pruning)

- 가지치기한 상태: 해당 노드의 방문하지 않는 하위트리 (pruned state)

# 유망함(promising) : 해답이 있다고 생각하는 것

# n-Queens 문제

n X n 체스판에 n개의 퀸을 배치하는 문제, 어떤 퀸도 다른 퀸에 의해서 잡히지 않도록 배치해야 함

즉, 같은 행, 열, 대각선에는 다른 퀸을 놓을 수 없음

- 백트래킹 적용:

• n^2개의 위치에 퀸을 놓을 수 있음
• 기준: 새로 놓을 퀸이 다른 다른 퀸을 잡을 수 있음(같은 가로,세로,대각선)
• 원소의 순서: 퀸을 놓을 수 있는 n개의 위치

4-Quenns 문제를 생각해보면 1번째 조건은 걑은 가로줄에 놓을 수 없으므로 4개의 퀸을 모두 다른 행을 선택해야하고 그 중에 4개의 열중에서 자리를 선택해야 하므로 4X4X4X4 =256 가지이다. 그리고 가지치기를 하는 경우는 퀸 2개를 놓았을 때 같은 열에 위치한다면 더 이상 다른 퀸을 놓지 않아도 유망하지 않다고 판단하고 더 이상 탐색하지 않는다.

구현이란 "풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제"를 의미한다.

• 알고리즘은 간단하나 코드가 길어지는 경우
• 실수 연산 및 특정 소수점 까리 출력해야 하는 경우
• 문자열을 어떠한 기준에 따라 처리해야 하는 경우
• 적절한 라이브러리를 찾아서 사용해야 하는 경우

보통 문제에서 2차원 공간을 필요로 하는 경우에는 행렬의 의미로 사용되는 경우가 많다. 

ex) 캐릭터 이동 문제

- 코드

for i in range(5):
    for j in range(5):
        print('(', i, ',', j, ')', end=' ')
    print()

- 결과

- 예시

2차원 공간인 배열의 이동을 1차원 배열을 2개 생성하여 방향벡터로 이용하는 경우가 있다.

# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
direction = ['동', '북', '서', '남']
# 현재 위치
x, y = 2, 2
print(f'현재 위치: {x},{y}')
for i in range(4):
    # 이동
    nx = x + dx[i]
    ny = y + dy[i]
    print(nx, ny, direction[i])

- 결과

- 문제

상하좌우

2배원 배열에서 U,D,L.R에 따라 상하좌우로 이동한다. 시작 지점은 1,1 이고 가장 오른쪽 아래 끝 지점은 N,N이다.

입력 조건:

첫째 줄에 배열의 크기기 N이 주어지고(1<=N<=100), 둘째 줄에서는 이동할 문자들이 주어진다. (1 <=이동 횟수 <=100)

출력 조건: 첫째 줄에 최종적으로 도착할 지점의 좌표를 공백을 기준으로 구분하여 출력

- 코드

n = int(input())
moving = list(input().split())

direction = ['U', 'D', 'L', 'R']
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
x, y = 0, 0

for move in moving:
    # 이동
    for i in range(4):
        if direction[i] == move:
            nx = x + dx[i]
            ny = y + dy[i]
            break

    # 범위 밖으로 나가는 경우는 그냥 넘어간다.
    if nx <= -1 or ny <= -1 or nx >= n-1 or ny >= n-1:
        continue
    else:
        x = nx
        y = ny

print(x + 1, y + 1)

- 결과

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요함
• 현재 상황에서 단순히 가장 좋아 보이는 것만을 반복적으로 선택했을 경우 최적의 해가 될 수 있는지 검토해야 하기 때문에 정당성 분석이 중요하다.

각 노드 상황마다 최적의 해를 찾을 경우 총합은 4+10+5 = 19 이지만 사실은 진짜 최적의 해는 4 + 9 + 8 = 21이다.

따라서 지금 같은 상황에서는 그리디 알고리즘이 최적의 해를 보장할 수 없다 라고 표현한다.

그렇기 때문에 코딩 테스트에서 출제 되는 그리디 문제는 탐욕법으로 풀었을 경우 최적의 해가 보장 되는 경우에 출제가 된다.

[문제] 거스름 돈

어느 가게에 계산을 도와주는 점원이 있다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 가게를 방문한 손님은 점원에게 N원의 돈을 지불 했을 경우에 교환 받는 동전의 최소 개수는 몇개 인가? 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

- 해법:

가장 큰 화폐부터 돈을 거슬러 준다. 

이 정당성이 검증이 되는 이유에는 거스름 돈중 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위들을 종합해 다른 해가 나올 수 없기 때문이다.

ex) 1000원을 600원,500원,100원으로 거슬러 줄 경우 :

탐욕법(600원 1개 ,100원 4개), 최적의 해 (500원 2개)

- 시간 복잡도:

화폐의 종류가 N개 이면, for문이 화폐의 종류만큼 반복되기 때문에 시간 복잡도는 O(N)

- 코드:

n = 1260
count = 0

# 큰 단위부터 교환
array = [500,100,50,10]

for money in array:
    # 거슬러준 동전 갯수
    count += n // money
    # 교환 하고 남은 잔액
    n %= money


print(count)

- 결과:

6

• 내장 함수: 기본 입출력, 정렬 등의 기본적인 함수
• itertools: 반복되는 데이터 처리 ex) 순열,조합
• heapq: 힙 자료구조 ex) 큐, 다익스트라 최단 경로
• bisect: 이진 탐색
• collections: 덱(deque), 카운터(Counter) 등 자료구조
• math: 수학적 기능 ex) 팩토리얼, 제곱근, 최대공약수, 삼각함수 관련함수 및 파이(pi)와 같은 수학적 상수

함수명	역할	결과
sum(iterable)	iterable안 변수 안에 수를 모두 더한 후 그 결과를 반환한다.
min(arg1, arg2, ... )	매개변수에 있는 변수들 중 가장 작은 값을 반환한다.
max(arg1, arg2, ... )	매개변수에 있는 변수들 중 가장 큰 값을 반환한다.
eval(expression, globals=None, locals=None)	문자열로 표현된 식을 수학적으로 계산한 후 그 결과를 반환한다. ※ 문자열을 그대로 실행하기 때문에 프로그램 개발 시에 나쁜 의도로 코드 내용을 삽입하여 보안이 취약할 수 있다.
sorted(iterable, *, reverse=False)	변수안에 원소들을 정렬하여 반환한다.
sorted(iterable, *, key=None, reverse=False)	key에 함수를 기준으로 정렬하여 반환한다.

# 순열과 조합

• 순열: 서로 다른 n개에서 서로 다른 r개를 선택
• 조합: 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택

# 순열 예시

from itertools import permutations

data = ['A', 'B', 'C']

result = list(permutations(data, 3))
print(result)

data에서 순서가 상관있게 서로 다른 3개를 선택한다.

- 결과 화면

# 조합 예시

from itertools import combinations

data = ['A', 'B', 'C']

result = list(combinations(data, 2))
print(result)

data에서 순서가 존재하는 순서에 상관없이 2개를 선택한다.

- 결과 화면

# 중복 순열

from itertools import product

data = ['A', 'B', 'C']

result = list(product(data, repeat=2))
print(result)

- 결과 화면

#중복 조합

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']

result = list(combinations_with_replacement(data, 2))
print(result)

- 결과화면

# Counter

• collections 라이브러리에 속한 함수로써 등장 횟수를 세는 기능
• 리스트와 같은 반복 가능한 객체가 주어졌을 때 내부의 원소가 몇 번 등장했는지를 반환

from collections import Counter

counter = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])

print(counter['blue'])
print(counter['green'])
print(dict(counter))

- 결과 화면

# 최대 공약수와 최소 공배수

math.gcd()를 이용해서 최대 공약수를 구할 수 있다. 이것을 이용하면 최소 공배수도 얻어낼 수 있다.

import math


# 최소 공배수(LCM)를 구하는 함수
def lcm(a, b):
    return a * b // math.gcd(a, b)


a = 21
b = 14

print(math.gcd(a, b))  # 최대 공약수(GCD) 계산
print(lcm(a, b))  # 최소 공배수(LCM) 계산

- 결과 화면