1월 4주차

#2745 진법 변환

N진법을 10진법으로 변환

 

*stoi : string to int

 

보통 첫번째 파라미터만 넣고 사용해서 원리를 몰랐는데,

디폴트인 10진법으로 알아서 변환해 주는 것이었다.

 

stoi(string,int ,int )

• 첫번째 파라미터: 변환해줄 문자열
• 두번째 파라미터: 실패 시 반환할 값
• 세번째 파라미터: 변환해줄 진법의 기수

#import <iostream>
using namespace std;

string a;
int b;

int main()
{
    cin >> a >> b;
    cout << stoi(a, 0, b);		// 1. string 2. 실패 시 반환할 값 3. 기수(진법)
}

---

#11005 진법 변환 2

10진법 수를 N진법으로 변환

string num;
reverse(num.begin(), num.end());	//배열 뒤집기

string K; int k;

K = 'A' + k - 10;

// int와 string의 연산: string >> int 로 형변환

// 10 = A, 11 = B ... 매핑해주는 식
// K = 'A' + k -10;A로 부터 몇 칸 떨어진 알파벳이니

 

My 풀이)

1) B으로 나눈 나머지를 빈 문자열에 +

2) N을 N을 B로 나눈 몫으로 갱신 

3) 1,2 과정 반복

4) 1의 자리부터 앞에 쌓이니 reverse해주기

 

남의 풀이)

로직 자체는 크게 다르지 않으나, 확실히 간결하다.

 

아직 삼항연산자가 익숙하지 않은데 자유자재로 쓸 수 있도록 연마.

 

z += k  >> z = z+k;

z = k +z;

순서 바꿔 이렇게 더해주니 내 코드에서 reverse과정이 필요가 없어졌다. 유연하게 생각하기.

---

#2292 벌집

 

 

규칙을 찾아내는 것은 그리 어렵지 않았다.

 

1로 부터 n 번째 원을 그려나가며 입력된 수가 위치한 n 번째 원을 찾아낸다.

n번째 원에 속한 수의 개수는 6n개로 등비수열이다.

n번째 원에 속한 모든 타일은 1번에서 n만큼의 이동으로 도달할 수 있다.

 

My 풀이)

또 재귀함수로 풀었는데, 재귀함수를 쓰면 항상 뭔가 어렵지 않은 것을 어렵게 구현하는 듯한 느낌이 든다..

재귀함수로 n번째 원에 위치한 수 중 가장 큰 값을 구하고 이를 입력된 값과 비교하도록 했다.

int bee(int n){
    if(n == 1 ) return 1;
    return (n-1) * 6 + bee(n-1);
}

 

한계점:

입력값 범위의 최댓값이 몇번째 원에 속하는지를 대강 구해둬야 했다.

즉, 또 n번째 원의 max값을 모두 구해두고 비교하는 식인 거다.

 

입력값이 들어오면 그때그때 늘려가며 비교해갈 순 없을까?

 

남의 풀이)

있다!

합을 빼주면 반대로 몇번째 원인지 구할 수 있다.

for(cin >>n ; n >1; i++) n-= 6*i;

---

#2869 달팽이는 올라가고 싶다

 

반복문을 쓰면 무조건 시간 초과가 발생하는 문제.

https://cryptosalamander.tistory.com/22 

[백준 / BOJ] - 2869번 달팽이는 올라가고 싶다 C++ 풀이

---

#5086 배수와 약수

 

기본 상식이지만 은근 헷갈려서 기록해둠.

• 12%4 = 0
• 4%12 = 4

남의풀이)

 

풀이들 보다보면 은근 true = 1, false = 0 값을 자유자재로 조건문에 활용한다거나,

비트연산자 AND(&), OR(|), XOR(^)를 머리 좋게 활용하는 경우를 마주하게 됌.

막상 쓰려면 은근히 헷갈리기 때문에 정리해 둔다. 

 

* XOR(^)는 서로 다르면 1을 반환

0&0	0	0 | 0	0	0^0	0
0&1	0	0 | 1	1	0^1	1
1&0	0	1  | 0	1	1^0	1
1&1	1	1  | 1	1	1^1	0

 

마지막 테스트 케이스로 0 0이 주어지고, 나머지는 모두 다른 두 수가 입력되므로

XOR연산으로 두 수가 서로 같은지 다른지 판단 가능.

 

 

---

#9506 약수들의 합

 

벡터의 마지막 원소 접근하는 방법

vector<int> nn;

nn.back();
nn[nn.size()-1];	// nn.size()에 접근해서 자꾸 0이 나오는 바보 같은 실수

---

#1085 직사각형에서 탈출

 

최솟값 함수

min({x,w-x,h-y,y});

---

#0125 네 번째 점

 

3개 중 다른 하나를 골라내는 로직

int a,b;

a^=b; //b가 a와 다르면 a를 b로 갱신

---

#11653 소인수분해

 

while문의 조건부 내용을 ㅇㅇ일때까지 반복 수행으로 생각하게 됌. 살짝 바보인듯

 

N==1일 때까지 소인수 분해를 수행하라!

→ N!=1일때만 수행하라! 로 바꿔서 생각하기

남의 풀이)

 

• 배울 개념 1 - falsy값
  • Bool형변환은 일반적으로 true로 변환된다.
  • falsy값, 즉 false로 변환되는 경우만 기억하기!
    • 숫자형 : 0, NaN
    • 문자형 : "",'' 빈문자
• 배울 개념 2 - for문 동작 원리
  • for(① 초기화부분 ; ② 조건부분; ④ 추가 동작부분) {③ 동작부분}
  • 은근히 헷갈리는 기본기, 응용에도 능해지도록!
• 배울 개념 3 - 증가연산자
  • ++p (전위 증가연산자) : p + 1을 한 후에 p를 사용
  • p++ (후위 증가연산자) : p를 사용한 후 p+1을 해줌.

 

---

#2581 소수

 

벡터가 비었나요?

vector<int> k;

if(k.empty())	// 벡터가 비었는지 확인
if(k.size()==0)

 

Flag 현명하게 사용하기

• true 디폴트로 설정해두고 false로 갱신

    for(int i = M ; i <= N ; i++){

        isPrime = true;

        for(int j = 2; j <M; j++){
            if(i % j == 0){
                isPrime = false;
                break;                
            }      
        }

        if(isPrime)
        {
            k.push_back(i);
            sum += i;
        }
    }

---

#9063 대지

최대,최소 구하기

//min : value 반환
min(a,b);
min({1,3,5,7});

//min_element : iterator 반환
int minx = *min_element(x, x + N);
int maxx = *max_element(x, x + N);

int minx = *min_element(x.begin(),x.end());
int maxx = *max_element(x.begin(),x.end());

INT_MAX , 1e4

 

My 풀이)

x 배열에 모든 원소 다 넣어두고,

y 배열에 모든 원소 다 넣어두고 최대 최소 구하는 또 멍청한 풀이를 구현.

 

남의 풀이)

입력값 받아 기존 값보다 작거나 크면 바로 바로 갱신하는 식으로!

이건 터득했다고 생각했는데 또 후퇴했니

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N, x, y, minY = 10000, minX = 10000, maxY = -10000, maxX = -10000;
    cin >> N;

    while (N--)
    {
        cin >> x >> y;
        
        minY = min(minY, y);
        minX = min(minX, x);
        maxY = max(maxY, y);
        maxX = max(maxX, x);
    }
    cout << (maxX - minX) * (maxY - minY);
}

---

#24262 - 알고리즘 수업 - 알고리즘의 수행 시간 1 

 

처음 풀어본 시간복잡도 문제.

문제 파악 자체를 못해서 구글링을 해보았다.

 

코드를 실행하여 계산해내는 문제가 아니라, 직접 코드의 시간 복잡도를 구해 출력만 하면 되는 거였다.

단순히 배열의 n 번째 요소에 접근하는 코드이므로

수행횟수는 1, 시간 복잡도는 수행횟수가 상수이므로 무시되어서 0이다.

 

내 코드의 시간복잡도도 구해서 최적화시킬 줄 알아야 하는구나~

깨달음과 성장.

 

* 시간 복잡도 계산법 참고

https://machineboy0.tistory.com/57

시간복잡도(Time-Complexity), 빅오표기법(Big-O)

---

#24263 - 알고리즘 수업 - 알고리즘의 수행 시간 2

 

의사코드(Pseudocode)란!

 

의사코드(Pseudocode)는 실제 프로그래밍 언어가 아니며, 특정한 문법이나 규칙을 갖지 않습니다. 그 대신에, 알고리즘이나 프로그램의 논리를 사람이 이해하기 쉽도록 표현하는 데 사용됩니다. 목적은 구체적인 프로그래밍 언어에 종속되지 않고 프로그램의 개략적인 동작을 설명하는 것입니다.

 

지피티 똑똑한 놈.

 

sum <- 0 == sum = 0; 같은 뜻

의사코드 (Pseudocode)

 

단순히 1부터 n 까지의 합을 구하는 코드로,

수행횟수는 n이 되고, 시간복잡도는 n의 차수인 1이된다.

---

#15894 수학은 체육과목입니다

 

성원이는 수학을 정말 못 하는 고등학생이다. 수학을 못하는 대신 근성과 팔 힘이 뛰어난 성원이는 수학 시험에서 수학 지식을 사용하지 않고 근성과 체력을 사용해 문제를 푼다.

 

문제 읽다가 뼈맞고 시작.

 

규칙은 쉬웠으나, 입력값 범위를 고려하지 않고 int형으로 풀어 틀렸다.

놓친 규칙이 있나 싶어 그림만 5분 그리다, 아차 

 

int형 최대 = 2147483647 = 21억 2천7백4십8만 3천 6백 4십7

10^9 또는 10의 9승은 1,000,000,000, 즉 10억.

 

문제의 답인 4n은 최대가 40억이므로 int가 담을 수 있는 범위를 벗어남.

정수형		실수형
int	long	float	double
4byte	8byte	4byte	8byte
2,147,483,647 (약 21억)	9,223,372,036,854,775,807 (922경 3372조 36억 8547만 75807)	소수점 아래 7자리	소수점 아래 16자리

---

#14215 세 막대

배열 정렬하기

int s[] = {a,b,c};
sort(s,s+3);

 

  //min의 현명한 활용
  cout << a[0] + a[1] + min(a[0] + a[1] - 1, a[2]);

---

#10101 삼각형 외우기

 

늘 이런 문제를 풀 때마다 모든 경우의 수를 다 나열해야 하나.

놓친 예외 케이스는 없을지 고민하게 되는데..

숏코딩을 살펴봐도 이 문제는 케이스를 모두 조건화해줘야하는 것이 맞는듯 하다.

다만 나의 코드 보다 훨씬 간결하니 기록.

// 3개 모두 같다
a == b && b == c

// 2개가 같다
a == b || b == c || a == c

// 모두 다르다

---

#5073 삼각형과 세 변

//같은 표현
if(a==0) break;
if(!a)break;

---

#24264 - 알고리즘 수업 - 알고리즘의 수행 시간 3

불안하면 long 형 쓰기.

 

n번 반복 수행하는 2중 for문의 시간 복잡도 = n^2

 

---

#1436 - 영화감독 숌

구글링..

 

남의 풀이 1)

1부터 전수 검사

string.find로 666 있으면 cnt ++

 

남의 풀이 2)

1부터 전수 검사

6 cnt가 3이 되면 true