hyerong's Dev_world🎡

1. 문제를 읽고 상수조건을 확인하고 접근 방법을 먼저 생각한다.

2. 30분~1시간 내에 접근 방식이 생각나지 않으면 모르는 지식이므로 정답을 보고 공부해서 흡수한다.

+ 구현이 복잡한 문제도 2시간을 오버한다면 정답을 보고 다시 푼다.

3. 코드를 다 작성했다면 바로 제출하지말고 복잡도 분석을 한다.

4. 풀고 나서 다른 사람들의 다양한 풀이와 깔끔한 코드를 꼭 공부한다. 

5. 풀었던 문제는 한달 안에 와서 푼다. 15분 내로 풀 수 있을 때까지 반복한다. 

이 글은 달팽이 문제를 풀다가 내가 틀렸던 부분을 점검하는 글이다. 

다음에 다시 풀기전에 이 글만 읽고도 문제와 구현을 다시 생각할 수 있도록, 

해당 문제는 grid와 같이 2차원 배열로 생겼지만, 어떻게 풀이하냐에 따라 grid에 접근해야하는 방법이 다르다. 

0. 변수 설정 

    1) 달팽이 집 초기화 

-> 달팽이 집이 되는 2차원 배열 초기화 

grid = [[0]*n for _ in range(n)]

어차피 num으로 원소 값을 채워줄거니까 0으로 초기화 해도 됨 

    2) 4가지 방향 설정 top, left = 0 , 0 / bottom, right = 0,0 

    3) for문 안에서 인덱스 변수로 사용할 row, col은 따로 초기화 해줄 필요가 없다. for문 안에서 바로 사용해주면 됨 

1. 만약 4가지 방향 (윗줄 좌-> 우, 오른쪽 상->하, 하강 오른쪽 열, 아랫줄 우->좌, 상승 좌측 열) 으로 설정했다면 반복문 while 을 먼저 설정하고 그 안에서 4가지 방향으로 이동하는 for문을 4개 만들어준다. 

2. 이후로 고려할 것은 while문 안에 있는 for문의 범위를 설정해주는 것, 

1) 윗줄 행 좌-> 우,

for col in range(left, right+1) 

2) 가장 오른쪽 열 상->하,

3) 아랫줄 행 우->좌,

4) 상승 좌측 열

여기서 이 문제의 진가가 나타난다고 생각한다!!!

나같이 코테 연습양이 아직 적은 사람은 여기서 헷갈리기 쉽다. 

바로, 행 row 을 채우는 것인데 왜 for문 안에서 변수는 col이 나오는지 => 그 이유는 행을 채운다는 의미는 이미 그 행이 top임을 우리가 고정시켜놨고 행을 고정시켰다면 우리가 한칸씩 움직이면서 채워야하는건 columns이기 때문이다. 

이를 코드로 작성하면, for col in range(left, right+1) 

다시, 그 아래 2번케이스를 보면서 설명하자면, 

가장 우측 열을 채우는 것이기 때문에 우리는 열을 이미 right 로 고정을 시켜놨으니 for문에서 한칸씩 전진하며 채워야하는 건 top이 bottom으로 한칸씩 가는 것, 즉 row인 것이다. 이를 코드로 작성하면 for row in range(top, bottom+1) 이때, bottom은 n-1이기 때문에 번째로는 n번째, 값으로는 n-1까지 가려면 bottom+1을 해줘야 한다. 

세번째 반복문은 방향이 역방향으로 바뀐다는 것이 차이점이다. 

right에서 left로 이동하는 것, 이걸 for문 표현법으로 right, left-1, -1이 되는데 이미 우리가 첫 for문을 시작으로 left의 열 한줄을 사용했기 때문에 -1을 해주는 것이다. 

네번째 반복문은 아랫줄에서 이동하니까 bottom에서 시작하고 top기준으로 이미 한줄 채웠으니 top-1까지 역방향 이동이니까 -1하면서 for문을 만들어주고 col은 고정이니까 row를 변수로 받는다. for row in range(bottom, top-1,-1) 

항상 row가 첫번째 인덱스, col이 두번째 인덱스라 생각하고 grid[][]는 각 반복문에서 고정된 값을 그대로 넣어준다. 

grid[r][right] = num 이렇게 

3. 이제 for문 안에서 어떠한 연산이 이루어져야하는지 살펴보자. 

grid[r][right] = num 이렇게 num값을 원소로 대입해주면, num+=1을 통해 변수값을 갱신해주고, 

for문을 나와서 right 값을 - 1 해준다. 

왜 for문에서 나와서 갱신해주냐? 조금만 생각해보자. for문 에서 인덱스 상수로 right를 사용하고 있는데 동일한 반복문안에서 그 값을 변수로 계속 바꾸려고 시도하면 인덱스 에러가 날 것이다. 

이부분을 인지하면 오히려 그 if문과 그 다음 for문 작성하기가 쉬워진다. 

right가 인덱스에 들어가는 변수니까 if문으로 while의 종료 조건은 right가 상대편인 left보다 작을 경우로 break문을 설정해주면 된다.

남은 내용도 동일 

4. 출력 이슈 

출력을 때론 for문을 두개 사용해서 맞춰줘야한다는 것을 잊지 말기. 

테스트 케이스에 따른 for문은 그냥 예시일뿐, 우리가 맞춰야하는건 출력되는 모습이다. 쫄 ㄴㄴ

파리 퇴치 문제를 보면 2차원 배열이 우리를 반기고 있다. 

완전 탐색이나 구현/시뮬레이션 문제는 2차원 배열이 많이 나와서 이제 grid가 보이면 반가울 지경.

그래도 파리퇴치 문제는 찬찬히 보면 그렇게 답답한 문제는 아닌것 같다. 

최대 sum을 구하는 부분에서 조금 막막하다고 느낄 수 있지만, 이 문제에서 N과 M은 그렇게 크지 않아서 for 반복문으로도 구할 수 있다. 

문제는 N by N으로 채워진 grid에 M by M의 파리채로 가장 많은 파리를 잡아야 하는 내용이다. 

근데 이제 입력으로 grid의 원소들을 받아야 하는 것. 

먼저 배열을 초기화 해주는데 난 Mgrid까지 만들었지만, 사실 필요는 없다고 한다. 

입력에서 Ngrid의 원소를 받을땐 for 문을 사용해서 받아주는데, Ngrid를 먼저 1차원 배열로 만들었는데, 

그 이유가 바로 반복문 안에서 row로 한줄씩 입력을 받아서 그 row를 원소들로 받으면 그게 2차원 배열이 되기 때문. 

이후 append로 Ngrid를 완성하면된다. 

그리고 이제 row와 col을 N-M+1만큼 반복하면서 최댓값을 찾아야하는데, 

current 변수를 사용하는게 포인트. 

처음 풀때 sum만 생각하고 current를 놓쳤는데 항상 이렇게 기준이 되는 변수를 생각하는게 중요하다. 

current 변수를 0으로 설정하고, 다시 반복문을 돌면서, 이때!! 반복문은 기준이되는 r, c부터 그 기준에서부터 종료되는 부분r+M, c+M까지로 반복하면서 그 부분에 해당하는 Ngrid 원소 값을 current에 더해준다. 박스 모양을 걱정할 필요는 없는게 각 열과 행의 +M을 한게 박스 모양이 구상이 된다. 

그리고 i와 j로 돈 반복문 밖으로 나와 if 문으로 current와 Gsum의 대소를 비교해서 최댓값으로 할당해준다. 

2중 for문 안에서 반복해줘야하는 것을 기억하기. 

풀이 코드) 

def solve():
    #정수 입력받아서 생성     
    N, M= map(int,input().split())
    Gsum = 0 
    Ngrid = []
    Mgrid = [[0] * N for _ in range(M)] #파리채 생성 
    # print(Mgrid)
    #정수 입력받아서 그리드에 저장 ->각 row를 받아서 1차원 리스트의 원소로 넣기 
    for _ in range(N): 
        row = list(map(int, input().split()))
        Ngrid.append(row)
    # print(Ngrid)

    #Ngrid를 row와 col로 완전 탐색하면서 M grid만큼 sum을 항상 구하기 
    for r in range(N-M+1): 
        for c in range(N-M+1):
            current = 0 #여기가 문제 
            for i in range(r, r+M):
                for j in range(c, c+M):
                    current += Ngrid[i][j] #i,j번째 있는 것들의 합 
            if current > Gsum:
                Gsum = current
            
    #print(Gsum) #디버깅용 출력문
    return Gsum 
            
            # if(r and c == N-M+1): #잘못 생각한 부분
                # Gsum = sum(Mgrid)
        
solve()

1. Brute Force: 완전 탐색이란 
완전 다 탐색한다는 말로, 모든 경우를 다 생각해서 전부 시도하는 것이다. 

직접 다 구현해서 모든 경우를 다 거치며 확인하는 경우 

2. DP: Dynamic Programming 동적 계획법 

이건 이론적으로 있는 개념은 아니지만, 코테와 같이 문제풀이에서 사용하는 단어. 

예를들어 중복되는 계산이나 재귀적인 계산 같은 경우 해당 식을 일반식으로 표준화해서 따로 저장해서 중복 계산을 없애는 효율 추구 방식

완전탐색의 효율적인 방법 중 하나라고 볼수있다.

-> 겹치는 문제 (큰 문제를 풀다보니 같은 작은 문제를 여러번 풀 경우) 

-> 최적 부분 구조(전체 문제의 최적해가 부분 문제들의 최적해로 결정되는 경우) 

이 두가지 패턴이 보이면 DP 라고 생각하자

Dp의 형태로는 

1) Top-down + 재귀 

2) Bottom-up ; 반복문으로 테이블 채우기 

두가지가 있음 

3. BFS: Breadth-First Search 너비 우선 탐색

현재 위치에서 "한 칸 거리"에 있는 애들을 전부 먼저 방문하고, 그 다음 두칸 거리에 있는 애들을 방문하는 방식 

like 퍼져나가는 파동/물결 느낌, 동시에 한단계씩 퍼져나간다. 

-> 보통 queue를 사용해서 구현한다. 큐가 빌때까지, 큐에서 하나 꺼내서 인접한 노드를 큐에 넣기 

-> 주로 미로와 2단 grid 최단거리(가중치 동일시) 문제와 트리의 level 별 탐색에서 사용 

4. DFS: Depth-First Search 깊이 우선 탐색 

한 방향으로 끝까지 갔다가 막히면 한단계씩 뒤로 돌아오면서 다른 길로 다시 들어가기 

like 일단 끝까지 가 방식 

-> 보통 stack / 재귀 함수로 구현 

-> 현재 노드 방문하고, 인접한 노드중 아직 안 간 애들을 하나씩 스택/재귀 방식으로 방문 

-> 주로 연결된 영역 개수 세기, 트리 순회, 백트래킹(완전탐색) 에서 사용한다. 

그래프 문제에서의 목표는 다음과 같다.

- 출발점에서 갈 수 있는 칸/노드가 몇개인지

- 서로 연결된 덩어리가 몇개인지

- 미로에서 출구까지 갈 수 있는지 + 최단거리 

D2에 있는 간단한 369게임 

로직은 간단하지만, 입출력을 주의해서 풀어야한다.

테스트케이스를 입력받지않고 바로 정수 N을 입력받아 해당 N 사이 정수에 3,6,9 에 해당하는 수를 -로 바꿔줘야 한다. 

정수를 입력받고 해당 정수까지의 수들을 반복을 사용해서 str을 활용하고 list안에 문자열을 만드는 것이다. 

그리고 출력할땐 list를 주의해서 원소들을 공백 기준으로 일렬로 출력해야한다. 

풀이 코드 

def solve(n):
    result = []  # 최종 출력용 문자열들을 모을 리스트

    for i in range(1, n+1):
        s = str(i)
        cnt = 0

        # 이번 숫자 i에서 3/6/9 개수 세기
        for ch in s:
            if ch in '369':
                cnt += 1

        if cnt == 0:
            result.append(s)         # 숫자 그대로
        else:
            result.append('-' * cnt) # 3/6/9 개수만큼 '-'

    return result


n = int(input())
ans = solve(n)
print(*ans)

문제를 풀면서 주의해야할 점. 

1. 숫자에서 어느 자리가(일/십/백...) 3/6/9인지가 중요한게 아니라 해당 숫자에 3,6,9가 몇번 들어가는지가 중요하다. 

-> 몇번이라고 정의 내리기 때문에 횟수가 나올 수 있는 count 변수를 만들어주자. 

36이면 -가 두번 --, 35이면 -가 한번이어서 - 으로 출력한다. 

-> 처음 생각했던 방법은 3,6,9를 -로 replace하려고 했는데 그럴 필요 없이 그냥 3,6,9만 있으면 -을 출력한다고 생각하면 된다. 

2.  -을 출력할땐 '-'*count로 출력한다. 

문자에 횟수를 곱해서 그만큼을 새로운 정답 배열에 append로 끼워넣는다. (expend와 주의) 

3. 마지막 출력 형식으로 내가 print(*ans)와 같은 형식을 사용했는데 이 이유는, 정답인 배열의 원소를 하나하나 원소끼리 띄어쓰기를 해서 출력하고자 했기 때문

4. 파이썬 문법에서의 if문 주의

-> if s='3' or '6' or '9':는 틀렸고 if s = '3' or s='6' or s = '9':로 주의 

왜인지 알아야하는데, 문자인 '6'이나 '9'는 항상 True이기 때문에 

혹은 문자"열"에서 369가 있는지를 확인하고 싶다면 if s in '369':를 통해 하나의 식으로 표현할 수 있다. 

5. Index range 에러 주의 

for i in range(n+1):
    digits = list(str(i))

for j in range(n):           # j는 0 ~ n-1
    if digits[j] in '369':   # ❌ 여기서 IndexError
        ...

위와 같이 작성을 주의한다. 

i가 0부터 n까지 돈다고 할때, j는 0부터 n-1까지만 돈다.  -> IndexError 발생 

* 반복 범위는 항상 리스트 길이에 맞춰야한다. 

그런데 파이썬에서는 len으로 리스트 길이 표현보다 더 간단하게 for ch in s:을 통해 뒤에 range범위를 문자열을 바로 적어줌으로,

더욱 파이써닉해질 수 있다. 

6. 함수 구조/호출 방식 주의 부분 

for i in range(n+1): 와 같은 반복문을 만약 정답 출력문과 def 함수(n)을 매개변수로 받는에서 둘다 사용하고 있다면 중첩될 수 있음을 주의한다. 

-> 보통 1~n까지 도는 반복은 보통 한 곳에서 한 번만 있으면 충분하다. 

예시) 

def solve(n):
    result = []
    for i in range(1, n+1):
        ...  # result에 채우기
    return result

n = int(input())
ans = solve(n)
print(*ans)

7. input()으로 받는것은 이미 문자열 

8. 리스트에 값을 넣을때: append, extend 차이 

append(x)의 경우, list안에 원소 x를 집어넣음 

arr = []
arr.append('ab')   # ['ab']

extend(iterable)의 경우, 리스트에 iterable원소들을 풀어서 여러개 넣음 

arr = []
arr.extend('ab')   # ['a', 'b']

이 문제에 extend가 더 적합할 수 있겠다고 생각할 수 있지만, 한 숫자당 -를 출력하는 것이기 때문에 35를 쪼개서 3,5로 저장하면 '-','5'로 출력이 됨으로 틀린 생각이다. 

오히려 append()을 사용해서 35가 - 한개로 출력되는 것을 생각해야한다. 

이 문제는 palindrome을 찾는 문제다. 

처음엔 가운데 글자를 기준으로 양옆으로 이동하면서 비교 하는 것을 생각했다. 

그러나, 이 방법이면 글자수가 짝수인 경우를 나눠서 고려해야해서 if문을 처음부터 두개를 쓰고 시작한다. 

그러나 입력받은 문자를 홀수/짝수로 나누지않고 푸는 효율적인 방법은 우선 문자를 입력받고 

첫번째 시작 인덱스와 끝나는 인덱스 둘로 나눠서 한칸씩 전진하며 비교하는 것이다. 

문자열을 일렬로 두고 첫 시작을 Left, 마지막 문자를 right라고 생각하고 푼다. 

(방향을 설정하는 부분에서 달팽이 문제와 비슷 )

#1989. 초심자의 회문 검사
# 단어 가운데 숫자 기준 
# 양옆으로 가면서 똑같은지 아닌지 확인 -> 홀수일때만 적용 가능 

#짝수 홀수 상관없이 할수 있는 경우로 풀이 
def solve():
    st = str(input())
    left = 0
    right = len(st) - 1 
    ans = 0
    for _ in range(len(st)//2):
        if st[left] == st[right]:
            left += 1
            right -= 1
            ans = 1
        else:
            ans = 0
    return ans 

T = int(input())
for tc in range(1,T+1):
    ans = solve()
    print(f"#{tc} {ans}")

이 문제를 풀면서 주의해야할 점은 바로 for문 안에 범위를 문자열의 길이의 1/2값으로 설정해줘야하는 것이다. 

그런데, 반복문 안에서 /2가 아니라 //2를 한 이유는 파이썬에서 /2의 결과는 float, //2의 결과는 int이기 때문이다. 

이 문제는 문제만 보면 난이도가 어렵지 않은 D2다.

입력받은 정수를 최대값일때 1부터 홀수는 더하고 짝수는 빼서 최종 합을 구하는 문제다. 

파이썬 풀이로도 풀이가 다양하게 가능해서 댓글을 통해 다른 사람들의 풀이 중 공부할 것들을 가져왔다. 

1. 람다 풀이 

람다 함수를 사용한 풀이인데 C언어에서 오래전 조건문을 배울때 삼항 연산자 ? 을 본 기억이 있을 것이다. 

람다 함수도 이와 비슷하다. 

lambda의 의미는 의미가 없다라는 함수로 '그냥 지금 바로 쓰고 말거니까 일단 람다라고 불러' 와 비슷한 의미다. 

argument 는 함수에서 사용할 변수를 작성 

: 로 구분해주고 나면 

expression은 이 함수에서 어떤걸 작성하고 싶은지 작성한다. 

이 문제를 풀 땐, 파이썬의 삼항 연산자를 기억하자. 

-x if x%2==0 else x

와 같은 식에서는 삼항 연산자 해석을 아래와 같이 한다. 

조건이 참이면 이 값, 거짓이면 저 값 → A if condition else B

그래서 if면 -짝수, else면 홀수 그대로 가 된다. 

#1986 지그재그 

T = int(input())

for tc in range(1,T+1):
    n = int(input())
    ans = sum(
            map(
                lambda x: -x if x%2==0 else x, 
                range(1,n+1)
            )
              )
    
    print(f"#{tc} {ans}")

풀이 식은 다음과 같고 map으로 sum의 반복을 1부터 n번 까지 하는것을 이해할 수 있다.