[백준, 프로그래머스] 문제풀이

백준 15650

from itertools import combinations

a ,b = map(int, input().split())
nlist = [i for i in range(1,a+1)]
for i in list(combinations(nlist, b)):
  print(*i)

백준 15651

a ,b = map(int, input().split())
nlist = []


def back(n):
  if(n-1 == b):
    print(*nlist)
    return
  for i in range(1,a+1):
    nlist.append(i)
    back(n+1)
    nlist.pop()
  
back(1)

 

백준 4771 칸토어

def cantor(dash):
  if(dash==1):
    return "-"
  thislen = dash//3
  return cantor(thislen)+" "*thislen+cantor(thislen)

while(True):
  try:
    n = input()
    if n == '':
      break
    else:
      n=int(n)
      length = 3**n
      
      print(cantor(length))
  except EOFError:
    break

 

프로그래머스

• 성격 유형 검사하기

https://school.programmers.co.kr/learn/courses/30/lessons/118666

 

def solution(survey, choices):
    mbti ={"RT": [0,0], "CF" : [0,0], "JM": [0,0], "AN": [0,0]}
    for s, ch in zip(survey, choices):
        if(s[::-1] in list(mbti.keys())):
            s=s[::-1]
            if(ch>3):
                mbti[s][0]+=ch-4#TR
            elif(ch<4):
                mbti[s][1]+=abs(ch-4)
        elif(s in list(mbti.keys())):
            if(ch>3):
                mbti[s][1]+=ch-4
            elif(ch<4):
                mbti[s][0]+=abs(ch-4)
    answer = ""
    for k, value in mbti.items():
        if(value[0]<value[1]):
            answer+=str(k)[1]
            print(str(k)[1])
        elif(value[0]==value[1]):
            answer+=str(k)[0]
        else:
            answer+=str(k)[0]
    return answer

 

개인공부

 

0으로 이루어진 영역의 개수 찾기 문제

dfs

# [DFS]

graph = [
    [0,0,1,1,0],
    [0,0,0,1,1],
    [1,1,1,1,1],
    [0,0,0,0,0]
]

n, m = map(int, input().split())

def dfs(x, y):

    if x <= -1 or x >= n or y <= -1 or y >= m:
        return False

    if graph[x][y] == 0:

        graph[x][y] = 1

        dfs(x - 1, y)
        dfs(x, y - 1)
        dfs(x + 1, y)
        dfs(x, y + 1)
        print("TRUE",x,y)
        return True
    print("False",x,y)
    return False


result = 0
for i in range(n):
    for j in range(m):

        if dfs(i, j) == True:
            print("*****",i,j,"*****")
            result += 1

print(result)

 

핵심은 dfs에서 뭘 반환했느냐는 중요하지 않다.

재귀하는 과정은 하나의 영역을 모두 1로 메꾸면 단 하나의 1만 반환될테니까

 

모든 영역을 메꾸면 그 메꾸는 횟수를 더한 것이다.

 

다음번에는 dfs에 대한 문제를 더 풀어보고 deque를 공부하며 bfs에 대한 개념을 공부해보겠다.