hyeeoni

https://www.acmicpc.net/problem/2941

내 코드

import sys
cro = ['dz=','c=','c-','d-','lj','nj','s=','z=']
user = sys.stdin.readline()

for i in cro:
    if user.find(i) != -1:
        user = user.replace(i,'?')

print(len(user)-1)

• -1 을 해준 이유는 readline이기 때문에 \n 값이 들어있기 때문이다.
• dz= 이 z= 보다 앞에 나와 있어야 한다.
• user.replace(i,"?") 는 user를 바꾸는게 아닌 '?'로 변경된 값을 반환하기 때문에 user = user.replace로 사용해 준다.

• https://www.acmicpc.net/problem/5622

내 코드

import sys
user = list(sys.stdin.readline())
dial = [list('ABC'),list('DEF'),list('GHI'),list('JKL'),list('MNO'),list('PQRS'),list('TUV'),list('WXYZ')]
dict_dial = {}
result = 0
for idx, val in enumerate(dial):
    dict_dial[idx] = val

for i in user:
    for j in dict_dial.items():
        if i in j[1]:
            result += (int(j[0])+3)
            break
print(result)

• 정말 이상하게 풀었고 다음부턴 이렇게 풀지 말아야겠다.

다른 코드

import sys
dial = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']

user = sys.stdin.readline().lower()
res = 0
for i in range(len(user)):
    for j in dial:
        if user[i] in j:
            res += dial.index(j) + 3
print(res)

https://www.acmicpc.net/problem/1157

내 코드

import sys

word = str.upper(sys.stdin.readline())

temp = set(word[:-1])
dict_word = {}
for i in temp:
    dict_word[i] = word.count(i)
max_word = max(dict_word.values())
chr_a = ''
count = 0
for key, val in dict_word.items():
    if val == max_word:
        chr_a = key
        count += 1
        if count ==2:
            chr_a = '?'
            break
    
print(chr_a)

• 중복된 문자 검색을 막기 위해 set을 사용
• dict에 문자와 해당 문자 count 값을 key와 value에 넣음
• value값의 최대값을 찾고 value값이 2개 이상일 때 ?를 출력 아니면 해당 문자 출력

내 코드

a = input()
result = [-1] * 26

for i in range(len(a)):
    if result[ord(a[i])- 97] == -1:
        result[ord(a[i])- 97] = a.index(a[i])
result = list(map(str, result))
print(' '.join(result))

• a부터 z까지 알파벳은 총 26개
• a의 아스키코드 값은 97을 이용하여 계산

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예

pricesreturn

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

출처

내 코드

def solution(prices):
    answer = []
    
    for i in range(len(prices)):
        cnt = 0
        if i == len(prices)-1: 
            answer.append(0)
            break
        for j in range(i+1,len(prices)):
            cnt += 1
            if prices[i] > prices[j]:
                break
        answer.append(cnt)
        
    return answer

• 다음 인덱스를 탐색할 경우 cnt가 어떠한 상황이라도 +1이 된다.
• i번째 value값이 i+1번째 value값보다 크면 break를 통해 j 반복문을 빠져나오고 cnt를 answer 리스트에 추가한다.

출처

내 코드

n, m = map(int, input().split())
visited = [False] * n
out = []
def solve(depth, m, idx):
    if depth == m:
        print(' '.join(map(str, out)))
        return

    for i in range(idx, n):
        if not visited[i]:
            visited[i] = True
            out.append(i+1)
            solve(depth+1, m, i+1)
            visited[i] = False
            out.pop()

solve(0, m,0)

• solve(0, m, 0) -> v = [t,f,f,f] out = [1]
• solve(1,m,1)-> v = [t,t,f,f] pit = [1,2]
• solve(1

백트랙킹

-알고리즘은 노드의 유망성 점검 후, 유망하지 않으면 그 노드의 부모로 되돌아간 후 다른 자식 노드를 검색하는 알고리즘이다.

출처

내 코드

n, m = map(int, input().split())
visited = [-1] * n
out = []
def solve(depth, m):
    if depth == m:
        print(' '.join(map(str, out)))
        return

    for i in range(n):
        if i+1 not in visited:
            visited[i] = i+1
            out.append(i+1)
            solve(depth+1, m)
            visited[i] = -1
            out.pop()

solve(0, m)

• i가 0번째부터 시작하므로 visited의 값을 -1로 리스트를 만들어준다.
• 방문하지 않은 정수에 대해서 dfs 작업을 해준다.

그래프

• 정점(vertex)과 간선(edge)으로 표현한 것
• 간선의 방향 유무에 따라 단방향 무방향(양방향) 그래프로 나뉨

그래프 표현 방법

1. 인접행렬

• 모든 정보를 저장.
• 불필요한 정보 저장이 많고, 그래프 크기가 커지면 메모리 초과가 발생할 수 있음.
• 갱신이나 삽입, 삭제 등 작업처리 할 때 많이 사용됨. 플로이드 워샬

2. 인접 리스트

• 필요한 정보만 저장하여 메모리 절약 가능
• 각 정점에서 이동가능한 정점들을 저장.
• 특정노드에서부터 탐색일 때 많이 사용 됨.

그래프와 트리의 차이점

그래프 탐색 기법

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.
• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.
• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

입출력 예

ncomputersreturn

입출력 예 설명

예제 #1
아래와 같이 2개의 네트워크가 있습니다.

예제 #2
아래와 같이 1개의 네트워크가 있습니다.

출처

def solution(n, computers):
    answer = 0
    visited = [0] * n
    bfs = []

    while 0 in visited:
        bfs.append(visited.index(0))
        while bfs:
            node = bfs.pop(0)
            visited[node] = 1
            for i in range(n):
                if visited[i] == 0 and computers[node][i] == 1:
                    vissited[i] = 1
                    bfs.append(i)

        answer += 1
    
    return answer

• 방문 리스트와 queue bfs리스트를 생성.
• visited가 0이 없을 때까지 반복
• bfs에 방문하지 않은 컴퓨터 저장
• 방문한 해당 컴퓨터를 1로 바꾸고, 방문한 적 없고, 해당 컴퓨터와 연결되어 있는 컴퓨터에 1값 저장
• 모두가 연결되어 있다면 첫번째 while문은 한번만 돌기 때문에 answer 값은 1이 될 것임.
• 모두 연결되어 있지 않다면 모든 컴퓨터를 돌기 때문에 answer는 n번 만큼 돌게 됨.

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

triangleresult

출처

코드

def solution(triangle):
    for i in range(1, len(triangle)):
        for j in range(i+1):
            if j == 0:
                triangle[i][j] += triangle[i-1][j]
            elif j == i:
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1],triangle[i-1][j])
                
    return max(triangle[-1])

• 루트 노드의 자식 노드부터 시작하여 리프노드까지 탐색하기 위해 1,len(triangle)을 해준다.
• 좌측 맨 끝 노드는 부모 노드와 좌측 끝 노드 더한 값을 넣는다. if j == 0
• 우측 맨 끝 노드도 같이 해준다. if j == i
• 사이에 있는 값들은 부모가 두개이므로 더 큰 값을 구한뒤 더해준 값을 넣어준다.
• 반복한다.