시나위

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 모든 값을 탐색하면서 이전보다 큰 값인 경우에만 백트래킹하는 방법으로 풀었다. desc_nums = [] visit = [False for _ in range(10)] def make_number(visit): ret = 0 for i in range(9, -1, -1): if visit[i]: ret = ret * 10 + i return ret def backtrack(ind=-..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션을 요구하는 삼성 느낌의 기출이다. 주어진 조건대로 만들어주기만하면 되는데 그게 너무 오래걸리는 문제여서 구현이 오래걸렸다. 완전탐색으로 맵에 그렸다가 지웠다를 반복하면 값이 나온다. import sys; input = sys.stdin.readline answer = None N, M = None, None cctv_list, d_map, r_map = None, None, ..

https://www.acmicpc.net/problem/11811 11811번: 데스스타 젊은 제다이 이반의 임무는 데스스타에 침투하여 파괴하는 일이다. 데스스타를 파괴하기 위해서는 길이 N의 음이 아닌 정수 수열 ai가 필요하다. 그러나 이반은 이 수열을 가지고 있지 않다. 대 www.acmicpc.net 손 푸는 문제 n_ij는 a_i와 a_j가 겹치는 비트를 보여주므로 bitwise 연산자 or로 모두 합치면 쉽게 풀수 있다. import sys; input = sys.stdin.readline def main(): N = int(input()) ans = [0 for _ in range(N)] for i in range(N): for nij in map(int, input().split()): ..

https://www.acmicpc.net/problem/1942 1942번: 디지털시계 디지털시계는 일반적으로 시각을 “hh:mm:ss”의 형태로 표현한다. hh는 00 이상 23 이하의 값을, mm과 ss는 00 이상 59 이하의 값을 가질 수 있다. 이러한 형태의 시각에서 콜론(“:”)을 제거하면 “hhm www.acmicpc.net 손 풀려다가 방향을 잘못잡아 어렵게 푼 문제이다. 시간이 주어졌을때 각 구간에서 3의 배수인 시계 정수의 개수를 구하는 문제이다. 이걸 어떻게 풀지 고민하다가 DP 처럼 딕셔너리 자료형을 사용해서 모든값을 구하는 방향으로 했다. 반복문으로 00:00:00 부터 23:59:59 까지 다 구하면 될줄 알았으나 time_dict[num1-1]에서 key error가 떠서 마..

https://www.acmicpc.net/problem/15644 15644번: 구슬 탈출 3 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 구슬탈출 2와 같은 문제이고 최소 거리일때의 경로까지 같이 출력해야한다. 구현한 알고리즘은 다음과 같다. 1) 입력을 받으면서 R, B, O의 위치를 저장한다. 2) BFS를 사용해서 시뮬레이션을 돌린다. 2-1) 먼저 움직이는 구슬을 찾는다. 2-2) 움직인다. 2-3) 파란 구슬이 빠진 경우 다음 방향을 탐색한다.(continue) 2-4) 빨..

https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 특정 노드를 정점으로 하는 서브 트리의 정점의 개수를 구해야한다. 무방향 그래프를 받아서 연결시켜주고, 루트 노드에서 시작해서 후위 순회로 자식 노드의 개수를 더해주면 된다. 이때 visit 로 방문했는지도 체크하고 해당 노드에서 자식 노드의 개수를 저장한다. 순회가 끝나면 visit에 자식 노드의 개수가 저장되어있으므로 특정 노드를 ..

https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 민트초코가 있는 곳을 방문하고 다시 돌아올수 있는지 사이클을 확인하는 문제이다. 이때 집과 민트초코 혹은 민트 초코끼리의 거리가 현재 진우의 체력보다 같거나 높아야 다음 단계로 넘어갈수 있다. 민트초코가 있는 점을 저장하고 방문하는 순서를 완전 탐색으로 돌려서 찾으면 된다. import sys; input = sys.stdin.readline answer = 0 visit = ..

https://www.acmicpc.net/problem/1718 1718번: 암호 Vigenere cipher이라는 암호화 방법은 암호화하려는 문장 (평문)의 단어와 암호화 키를 숫자로 바꾼 다음, 평문의 단어에 해당하는 숫자에 암호 키에 해당하는 숫자를 더하는 방식이다. 이 방법을 변 www.acmicpc.net 손풀겸 푸는 브론즈 문제 평문과 암호키의 아스키코드를 사용해서 암호문 또한 a-z 사이의 값이 나오도록 만들었다. C나 C++이라면 조금더 빠르게 풀었을듯 하다. def main(): p = input() k = input() answer = '' for i in range(len(p)): ch = p[i] if ch == ' ': answer += ch continue k_ch = k[i ..

https://www.acmicpc.net/problem/9489 9489번: 사촌 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 노드의 수 n과 사촌의 수를 구해야 하는 노드의 번호 k가 주어진다. (1 ≤ n ≤ 1,000, 1 ≤ k ≤ 1,000,000) 다음 줄 www.acmicpc.net 각 노드들의 son, parent를 딕셔너리로 기록하고 사촌의 수를 찾았다. import sys; input = sys.stdin.readline def find_sibling(me, son, parent): p, grand_p = None, None if parent.get(me): p = parent[me] if parent.get(p): grand_p = parent[..

https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 손풀겸 푸는 문제 2 가장 넓게 색을 입히는 방법으로 리스트의 앞 뒤를 인덱스로 접근해서 풀었다. 가리키는게 다른 색이면 앞에서만, 같은 색이면 양쪽에서 인덱스를 이동한다. def main(): N = int(input()) s = input() f, b = 0, N - 1 cnt = 0 while f = 0: init_f = s[f] init_b = s[b] cnt += 1 # 순방향 순회 w..