코딩묻은 디자이너

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

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.

풀이

가장 앞의 카드를 출력하고 빼주면 되는거라 pop을 사용했다.

앞의 카드를 뒤로 돌릴때도 append와 pop 사용.

순서에 주의하자

코드

# 2161 카드

n = int(input())
card = []

for i in range(1, n+1):
    card.append(i)
while len(card) > 1:
    print(card[0],end=' ')
    card.pop(0)
    card.append(card[0])
    card.pop(0)
print(card[0])

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

문제

다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다.

다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. (6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.)

입력

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 필요한 세트의 개수를 출력한다.

풀이

딕셔너리를 통해서 풀이 하였다.

6과 9는 서로 공유할 수 있기 때문에 입력된 수 안에 있는 경우 둘 다 더해준 후 나중에 2로 나눠 나눠진 값을 ceil로 올림 해줬다

코드

# 1475 방 번호
import math

num = list(input())
sets = {}

for n in num:
    if n in sets:
        if n == '9' or n == '6':
            sets['6'] += 1
            sets['9'] += 1
        else:
            sets[n] += 1
    else:
        if n == '9' or n == '6':
            sets['9'] = 1
            sets['6'] = 1
        else:
            sets[n] = 1

if '6' in sets:
    sets['6'] = math.ceil(sets['6']/2)
if '9' in sets:
    sets['9'] = math.ceil(sets['9']/2)

print(max(sets.values()))
# print(sets)

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

문제

평행사변형은 평행한 두 변을 가진 사각형이다. 세 개의 서로 다른 점이 주어진다. A(xA,yA), B(xB,yB), C(xC,yC)

이때, 적절히 점 D를 찾아서 네 점으로 평행사변형을 만들면 된다. 이때, D가 여러 개 나올 수도 있다.

만들어진 모든 사각형 중 가장 큰 둘레 길이와 가장 작은 둘레 길이의 차이를 출력하는 프로그램을 작성하시오. 만약 만들 수 있는 평행사변형이 없다면 -1을 출력한다.

입력

첫째 줄에 xA yA xB yB xC yC가 주어진다. 모두 절댓값이 5000보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다. 절대/상대 오차는 10-9까지 허용한다.

풀이

평행사변형을 만들수 있는 경우의 수는

다음과 같이 3개의 경우가 있다

그래서 D 좌표를 미리 구한 후

해당 삼각형의 넓이를 모두 구해준 후 3개의 경우의 수 중 가장 큰 수에서 적은 수를 빼주었다!

수학 넘 오랜만인지 D 좌표를 찾는게 생각보다 오래 걸렸다

2개의 D 좌표를 찾을 수 있지만 둘레를 구하기 위해서는 2변의 길이만 알면 되기 때문에 2개중 하나의 좌표만 사용해서 둘레를 구해줄 수 있었다!

코드

# 1064 평행사변형

xa, ya, xb, yb, xc, yc = map(int,input().split())


if ((xa - xb) * (ya - yc) == (ya - yb) * (xa - xc)):
    print(-1.0)
else:
    xd2 = (xa + xc) - xb
    yd2 = (ya + yc) - yb

    cir_1 = (abs(xa - xb) ** 2 + abs(ya - yb) ** 2) ** 0.5 + (abs(xa - xc) ** 2 + abs(ya - yc) ** 2) ** 0.5
    cir_2 = (abs(xa - xb) ** 2 + abs(ya - yb) ** 2) ** 0.5 + (abs(xa - xd2) ** 2 + abs(ya - yd2) ** 2) ** 0.5
    cir_3 = (abs(xa - xc) ** 2 + abs(ya - yc) ** 2) ** 0.5 + (abs(xa - xd2) ** 2 + abs(ya - yd2) ** 2) ** 0.5

    ans = max(cir_1, cir_2, cir_3) - min(cir_1, cir_2, cir_3)

    print(ans*2)

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

문제

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이

상하좌우 뿐만 아니라 대각선을 생각해줘야 하는 문제다!

상하좌우만 생각하면 벡터의 범위가

dr = [-1, 1, 0, 0]

dc = [0, 0, -1, 1]

이렇게 나오지만

상좌, 상우, 하좌, 하우

dr = [-1, 1, -1, 1]

dc = [-1, -1, 1, 1]

이 추가로 나오게 된다!

그래서 처음에 벡터를 

dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]

로 정의 해둔 후 문제를 풀었다.

def dfs(매개변수1, 매개변수2) <- 처음에 매개변수의 이름을 처음 받은 넓이 높이와 같은 값인 w 와 h로 받아버리는 바람에 고생했다ㅠ

python코드

#4963 섬의 개수
import sys
sys.setrecursionlimit(10**6)

dr = [-1, -1, -1, 0, 0, 1, 1, 1]
dc = [-1, 0, 1, -1, 1, -1, 0, 1]

def dfs(a, b):
    global island, visited
    visited[a][b] = 1
    for dir in range(8):
        nr = dr[dir] + a
        nc = dc[dir] + b
        if nr >= 0 and nr < h and nc >= 0 and nc < w:
            if arr[nr][nc] == 1 and visited[nr][nc] == 0:
                dfs(nr,nc)



while True:
    island = 0
    w, h = map(int,input().split())
    if w == 0 and h == 0 :
        break
    arr = []
    visited = [[0] * w for _ in range(h)]
    for i in range(h):
        arr.append(list(map(int,input().split())))
    for i in range(h):
        for j in range(w):
            if arr[i][j] == 1 and visited[i][j] == 0:
                dfs(i,j)
                island += 1
    print(island)

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

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이

dfs로 풀었다!

python에서 vector는 방향과 크기를 가지는 단위라고 하는데 C++ 에서 정의해서 쓰는 Vector랑 뭔가 다른 느낌이라 헷갈린다.

전에는 상,하,좌,우를 분명하게 인지하고 가는게 중요하다고 생각했는데 그냥 사방을 검사하는거라면 굳이 상하좌우를 명확히 할 필요는 없는 것 같다

dfs로 탐색하고, 탐색이 끝나면 ans 에 1을 더한다.

각각의 크기는 hap을 통해 더하고 리스트에 넣어줬다. 그 이후 sort로 정렬 후 출력!

python 코드

# 2667 단지번호붙이기
dr = [0, 0, -1, 1]
dc = [-1, 1, 0, 0]

def dfs(i,j):
    global ans, hap
    visited[i][j] = 1
    for d in range(4):
        nr = i +dr[d]
        nc = j +dc[d]
        if nr >= 0 and nr < N and nc >= 0 and nc < N:
            if arr[nr][nc] == '1' and visited[nr][nc] == 0:
                hap += 1
                dfs(nr,nc)
    return

N = int(input())
arr = []
visited = [[0] * N for _ in range(N)]
ans = 0
ans_arr = []
for n in range(N):
    arr.append(list(input()))

for i in range(N):
    for j in range(N):
        hap = 0
        if arr[i][j] == '1' and visited[i][j] == 0:
            dfs(i,j)
            ans += 1
            ans_arr.append(hap)
print(ans)
ans_arr.sort()
for i in ans_arr:
    print(i+1)

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

문제

N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력

첫째 줄에 정답 정사각형의 크기를 출력한다.

풀이

배열에서 벗어나서 오류가 나지 않게 i+a  < N, j+a < M 조건을 걸어줬다

그리고 1씩 늘려가면서 정사각형이 있나 탐색한 후 정 사각형이 있다면 넓이를 계산해서 받아줬다!

python코드

# 1051 숫자 정사각형

N, M = map(int,input().split())

arr = [list(input()) for _ in range(N)]
if N > M:
    k = M
else:
    k = N
ans = 0
max_ans = 0
for i in range(N):
    for j in range(M):
        for a in range(k):
            if i+a < N and j+a < M and arr[i][j] == arr[i + a][j] == arr[i][j+a] == arr[i+a][j+a]:
                ans = (a + 1) * (a + 1)
                if ans > max_ans:
                    max_ans = ans
print(max_ans)

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

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다.

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

풀이

드디어 푼 셀프 넘버 문제

처음에는 문제 자체를 이해 못했는데 알고보니 어렵지 않은 문제다

지금 현재수 + 수를 쪼갠 수가 list 안에 속하면 지워준다. 그리고 남아있는 list를 출력해준다.

효율적이라고는 할 수 없지만 모든 수를 탐색하는 방법으로 풀었다.

python코드

# 4673 셀프 넘버

arr = []
for i in range(1,10001):
    arr.append(i)

for i in range(1, 10001):
    nums=list(str(i))
    num = i
    for j in range(len(nums)):
        num += int(nums[j])
    if num in arr:
        arr.remove(num)

for i in arr:
    print(i)

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

문제

동혁이는 오래된 창고를 뒤지다가 낡은 체스판과 피스를 발견했다.

체스판의 먼지를 털어내고 걸레로 닦으니 그럭저럭 쓸만한 체스판이 되었다. 하지만, 검정색 피스는 모두 있었으나, 흰색 피스는 개수가 올바르지 않았다.

체스는 총 16개의 피스를 사용하며, 킹 1개, 퀸 1개, 룩 2개, 비숍 2개, 나이트 2개, 폰 8개로 구성되어 있다.

동혁이가 발견한 흰색 피스의 개수가 주어졌을 때, 몇 개를 더하거나 빼야 올바른 세트가 되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 동혁이가 찾은 흰색 킹, 퀸, 룩, 비숍, 나이트, 폰의 개수가 주어진다. 이 값은 0보다 크거나 같고 10보다 작거나 같은 정수이다.

출력

첫째 줄에 입력에서 주어진 순서대로 몇 개의 피스를 더하거나 빼야 되는지를 출력한다. 만약 수가 양수라면 동혁이는 그 개수 만큼 피스를 더해야 하는 것이고, 음수라면 제거해야 하는 것이다.

풀이

자신감 키우는 날~!

list로 받아서 인덱스 순서대로 접근했다.

개수가 정해져 있기 때문에 그 갯수에서 인덱스에 해당하는 것을 뺐다!

python코드

#3003 킹, 퀸, 룩, 비숍, 나이트, 폰

chess = list(map(int,input().split()))

print(1-chess[0], 1-chess[1], 2-chess[2], 2-chess[3], 2-chess[4], 8-chess[5])

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

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

풀이

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

동적 계획법으로 풀어내는 문제

python 코드

#11722 가장 긴 감소하는 부분 수열

N = int(input())
arr = list(map(int,input().split()))

dp = [1] * N

for i in range(1,N):
    for j in range(0,i):
        if arr[i] < arr[j]:
            dp[i] = max(dp[i], dp[j]+1)
ans = max(dp)
print(ans)

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

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

풀이

트리 문제를 풀 때 가장 고민이 저것을 어떻게 코드로 표현하느냐 인데

노드의 연결상태를 이런식으로 생각하니깐 쉬웠다!

형태는

[A,B,C]

[B,D,.]

.

.

.

이런 식으로 표현해서 0번 인덱스 1번 인덱스, 2번 인덱스로 접근했다

전위 순회 규칙을 찾아내면 중위와 후위는 비슷하게 풀이할 수 있다

python 코드

# 1991 트리 순회
def preorder(n):
    print(arr[n][0],end='')
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                preorder(i)
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][2]:
                preorder(i)
def inorder(n):
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                inorder(i)
    print(arr[n][0],end='')
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if(arr[i][0]) == arr[n][2]:
                inorder(i)
def postorder(n):
    if arr[n][1] != '.':
        for i in range(len(arr)):
            if arr[i][0] == arr[n][1]:
                postorder(i)
    if arr[n][2] != '.':
        for i in range(len(arr)):
            if(arr[i][0]) == arr[n][2]:
                postorder(i)
    print(arr[n][0],end='')

N = int(input())
arr = []

for t in range(N):
    arr.append(list(map(str,input().split())))

preorder(0)
print()
inorder(0)
print()
postorder(0)