코딩하는 eroke

문제

피보나치 수 F(n) = F(n-1) + F(n-2)

input: 2<=n<=100,000 

return : n번째 피보나치 수 % 1234567

그냥 재귀함수로만 구현하면 틀리는 문제로 메모이제이션이 중요한 문제이다.

(실패이유 : 재귀함수 호출 수 초과)

메모이제이션 (memoization) :

한 번 계산한 결과는 저장, 이후 저장한 값으로 호출하여 재귀가 계속해서 호출되는 것을 방지

풀이

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int d[100001]; //전역=0초기화
int fibo(int n){
    if(n<=2) return 1;
    
    if(d[n]!=0) return d[n]%1234567; //메모이제이션
    else{
        d[n]=fibo(n-1)+fibo(n-2);
        return d[n]%1234567;
    }    
}

int solution(int n) {
    return fibo(n);
}

문제

input :

0과 1로 이루어진 어떤 문자열 x

1. x의 모든 0을 제거
2. x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 변환

return :
x가 "1"이 될 때까지 계속해서 x에 변환을 가했을 때의

[이진 변환의 횟수, 변환 과정에서 제거된 모든 0의 개수]

   ex)

x = "0111010"이라면,

x = "0111010" -> 0제거 -> "1111" -> 4("1111"의 길이) 이진변환 -> "100" 

[3,5] return

풀이

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> solution(string s) {
    vector<int> answer={0,0};
    int zero=0,ztotal=0,cnt=0,len=0;
    string cp=s;
    
    if(cp=="1") return answer;
    
    while(cp!="1"){
        cnt++; //이진변환 횟수
        zero=0;
        for(int i=0;i<cp.length();i++){
            if(cp[i]=='0')zero++;
        }
        ztotal+=zero; //제거한 0개수
        len = cp.length()-zero;

        string bin="";
        while(len){
            bin+=to_string(len%2);
            len/=2;
        }
        reverse(bin.begin(),bin.end());
        cp=bin;
    }
    answer[0]=cnt;
    answer[1]=ztotal;
    return answer;
}

요새 파이썬으로만 문제를 풀다가 오랜만에 C++ 로 문제를 풀려고하니 문법을 죄다 까먹었다;;

특히 STL, 문자열........... 당분간 C++ 문법 복기용 문제들을 풀어볼 예정이다..

문제

위의 입출력 예시 그대로인 간단한 문제이다. 뒤의 숫자 네개를 제외하고 마스킹(*)하면 된다.

(phone_number는 길이 4 이상, 20이하인 문자열)

풀이

#include <string>
#include <iostream>

using namespace std;

string solution(string phone_number) {
    string star = "****************";
    
    string subs = phone_number.substr(phone_number.size()-4, phone_number.size());
    int ln = phone_number.size()-4;
    string answer = star.substr(0,ln);
    answer+=subs;
    
    return answer;
}

전화번호의 뒤 숫자 4개를 substr로 끊고

4개를 제외한 길이만큼 * 문자열을 만들어 둘을 합쳐서 return 했다.

문제

FOOD_ORDER 테이블에서 5월 1일을 기준으로 주문 ID, 제품 ID, 출고일자, 출고여부를 조회하는 SQL작성

5월 1일까지 출고완료, 이 후 날짜는 출고 대기, 미정이면 출고미정

결과는 주문 ID를 기준으로 오름차순 정렬해주세요.

출력예시 (출처 : 프로그래머스)

위의 예시만 보고 OUT_DATE 포맷도 'YYYY/MM/DD' 로 맞췄더니 틀렸다고나왔다;

OUT_DATE는 그냥 출력하면된다. 출고여부는 CASE문으로 작성했다.

풀이

SELECT ORDER_ID
     , PRODUCT_ID
     , OUT_DATE
     , CASE WHEN TO_CHAR(OUT_DATE,'YYYYMMDD') <= '20220501' THEN '출고완료'
            WHEN TO_CHAR(OUT_DATE,'YYYYMMDD') > '20220501' THEN '출고대기'
            ELSE '출고미정' END AS 출고여부
FROM FOOD_ORDER 
ORDER BY ORDER_ID

문제

M,N,K (행, 열, 직사각형 개수)를 입력받고

K개의 직사각형 왼쪽 아래 좌표와 오른쪽 위 좌표를 입력받아 색칠한다.

<그림1> 같이 색칠이 끝나면 <그림2>처럼 직사각형 외부에 분리된 영역들이 생기는데

이 영역들의 넓이를 각각 구하고 영역의 개수를 첫째 줄에 출력,

영역의 넓이를 오름차순으로 각각 출력해주면 되는 문제이다.

풀이 (python, BFS)

from collections import deque

dx=[1,-1,0,0]
dy=[0,0,1,-1]

m,n,k = map(int,input().split())
sq=[[0]*(n) for _ in range(m)] #n*m 맵

#직사각형 좌표 입력 및 색칠
for tc in range(k):
    a,b,c,d = map(int,input().split()) #0 2 4 4
    for x in range(b,d): #2~4
        for y in range(a,c): #0~4
            sq[x][y]=1

#BFS
dq=deque()
answer=[]
for i in range(m):
    for j in range(n):
        if sq[i][j]==0:
            dq.append((i,j))
            cnt=0
            while dq:
                cx,cy=dq.popleft()
                for i in range(4):
                    nx=cx+dx[i]
                    ny=cy+dy[i]
                    if 0<=nx<m and 0<=ny<n and sq[nx][ny]==0:
                        cnt+=1
                        sq[nx][ny]=2 #visit
                        dq.append((nx,ny))
            if cnt==0: answer.append(1)
            else: answer.append(cnt)

answer.sort()
print(len(answer))
for a in answer:
    print(a,end=' ')

좌표를 입력받고 색칠한 뒤 (1로 표기)

맵에서 0인 영역이 존재하면 해당위치를 큐에 넣고 BFS를 돌려서 풀었다.

백준의 단지번호 붙이기와 매우 유사한 문제였다.

사실 오늘 냅색 알고리즘을 복습했는데 머리 빠개지는줄 알았다..

흑흑스 갈길이 넘멀다

파이팅..

문제

그림과 같이 N*M 맵에서좌측 맨 상단에서 우측 맨 하단까지 갈 수 있는 최단거리를 출력하는 문제이다.

맵에서 0인 구간은 못가고 1인 구간만 갈 수 있으며 목적지까지 도달할 수 없으면 -1을 출력한다.

주의할 점은 N,M은 같을 수도 다를 수도 있다.

큐를 사용해 BFS로 풀었고 이동한 거리는 현재 지점+1로 계산했다.

BFS 개념 복습하기 좋은 문제인 것 같다.

입출력 예

풀이

from collections import deque

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def solution(maps):

    n = len(maps)
    m = len(maps[0])
    
    dq=deque()
    dq.append((0,0))
    
    while dq:
        cx, cy = dq.popleft()
        
        if cx==n-1 and cy==m-1: 
            #for m in maps: print(m)
            return maps[cx][cy]
        
        for i in range(4):
            nx = cx+dx[i]
            ny = cy+dy[i]
            if 0<=nx<n and 0<=ny<m and maps[nx][ny]==1:
                dq.append((nx,ny))
                maps[nx][ny] = maps[cx][cy]+1

    return -1

문제

문제 설명

제한 조건

• s는 길이 1 이상 200 이하인 문자열입니다.
• s는 알파벳과 숫자, 공백문자(" ")로 이루어져 있습니다.
  • 숫자는 단어의 첫 문자로만 나옵니다.
  • 숫자로만 이루어진 단어는 없습니다.
  • 공백문자가 연속해서 나올 수 있습니다.

입출력 예

유의해야 할 점은 공백문자가 여러 개일 수 있어 단순 split()을 하면 안된다.

풀이 (python)

def solution(s):
    answer = ''
    lspace = list()
    is_space = False
    
    space = ''
    for x in s:
        if x==' ':
            is_space = True
            space+=' '
        elif x!=' ' and is_space==True:
            is_space = False
            lspace.append(space)
            space=''
    if space!='': lspace.append(space)
            
    sp = 0            
    tmp = s.split()
    for t in tmp:
        y = t.lower().capitalize() #문자열 전체 소문자 치환 후 첫글자만 대문자화
        answer+=y
        if sp<len(lspace):
            answer+=lspace[sp]
        sp+=1
        
    return answer

첫번째 반복문에서 공백이 등장할때마다 공백 문자열을 리스트에 추가 했다.

두번째 반복문에서 공백이 아닌 문자열들을 소문자화, 첫 문자만 대문자화한 뒤 

결과 문자열에 재처리한 문자열들과 공백 문자열들을 더해 리턴해주었다.

공백 문자열이 마지막까지 있는 경우도 고려해주어야 모든 케이스가 통과된다.

문제

1칸, 2칸을 갈 수 있을때 n칸 까지 도달하기 위한 경우의 수를 리턴하는 문제이다.

 n=1일때, (1칸) = return 1

n=2일때, (1칸, 1칸), (2칸) = return 2

n=3, n=4 는 그림을참고하면 된다.

결국 피보나치 문제였다.

주의할 점은 n이 1 또는 2일때 어떠한 메모리 할당도 하지 않고 바로 리턴해야 테스트1번이 통과된다.

풀이

def solution(n):
    if n<3: return n
    
    dp=[0]*(n+1)
    dp[1]=1
    dp[2]=2
    
    for i in range(3,n+1):
        dp[i]=dp[i-1]+dp[i-2]
    
    return dp[n]%1234567

문제

시키는 대로 하면 되는 문제이고 파이썬 문자열 연습하는데 좋은 문제인 것 같다.

풀이 (python)

def solution(new_id):
	#1단계
    new_id1 = new_id.lower()
    
    #2단계
    new_id2=''
    for x in new_id1:
        if x.isalpha() or x.isdigit() or x=='-' or x=='_' or x=='.':
            new_id2+=x
    
    #3단계
    while '..' in new_id2:
        new_id2 = new_id2.replace('..','.')
    
    #4단계
    new_id3=list(new_id2)
    if new_id3 and new_id3[0]=='.': del new_id3[0]
    if new_id3 and new_id3[-1]=='.':del new_id3[-1]
    
    new_id4 = ''.join(new_id3)
    
    #5단계
    if new_id4=='': return 'aaa'
    #6단계
    if len(new_id4)>=16: new_id4 = new_id4[:15]
    if new_id4[-1]=='.': new_id4 = new_id4[:14]
    #7단계
    if len(new_id4)<3:
        while len(new_id4)!=3:
            new_id4+=new_id4[-1]
            
    return new_id4

문자열 함수들과 리스트변환, 슬라이스를 사용해 풀이했다.

문제

풀이 (Python)

from collections import deque

def getThird(dq, n):
    a=n//3
    p=n%3
    if n==0: return dq
    else: 
        dq.appendleft(p)
        return getThird(dq,a)

def solution(n):
    answer = 0
    
    dq=deque()
    t = getThird(dq,n)
    
    for i in range(len(dq)):
        answer+=((3**i)*dq[i])

    return answer

위 소스로 풀긴 했지만 찾아보니 아래처럼 풀이할 수도 있다고 한다.

deque를 안쓰고 리스트로 푼담에 바로 return(answer, 3) 하면 좀더 간단할 것 같다.

int(answer, n) # n진법으로 구성된 str형의 answer를 10진수로 반환

레벨2 언제풀지..............