https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백트래킹을 이용한 브루트 포싱이다. 단어의 앞뒤가 항상 anti, tica로 이루어져 있으므로 최소 5개의 글자 (a,c,i,n,t) 는 알고 있어야 한다. 그리고 이제 남은 알파벳 21개 중에서 추가로 학습을 진행한다. 이 때 알고 있는 글자의 수가 k개가 될 때 까지만 진행한다. 만약 depth가 k에 도달한다면, 입력으로 주어진 단어를 탐색하면서 모르는 글자가 나올 경우 탐색을 종료하..
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net dfs 연습하기 좋은 문제이다. 우선 양방향 그래프이므로 입력을 양쪽에 모두 넣어주어야 한다는 것을 잊지말자! 그리고 숫자 하나씩 dfs를 돌려보며, 재귀의 depth가 4 (=> A-B, B-C, C-D, D-E 의 친구 관계) 에 도달할 경우 True 값을 주고 반환하면 된다. 단 한번이라도 도달하면 1을 출력해주면 된다. 주의할 점은, dfs에 들어가기 전 해당 숫자에 대해 방문 체크를 해주고 시작해야한다! import sys sys.setrecursionlimit(10**6) input = sy..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net for문을 두번 돌면서 각 숫자로 하여금 생성될 수 있는 "셀프 넘버가 아닌 것" 들을 구해서 저장한다. 2개의 for문을 통해, 셀프 넘버가 아닌 것들을 True로 바꿔서 False인 것들(=셀프 넘버)만 출력해주면 된다. set을 이용한 깔끔한 코드도 있다고 하니, 문제를 다 풀고 나서 찾아보시길! import sys import math fr..
https://www.acmicpc.net/problem/27211 27211번: 도넛 행성 준겸이는 $N \times M$칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 www.acmicpc.net 조금 지저분하게 푼 것 양해바랍니다,, 우선, 보드의 크기와 입력은 고정되어있으므로 선언해준 뒤 시작한다. 이때 10x10 이라고 무조건 2차원 배열로 만들 필요는 없다! 주사위는 +1 ~ +6까지 무조건 양의 방향으로만 증가하므로 1차원 배열로 선언해주어야 더 쉽게 풀 수 있다. 사다리와 뱀의 정보도 구별 지을 필요 없다. 어찌됐건 둘 다 만나면 다른 곳으로 이동하므로 하나의 리스트에..
https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048게임을 구현하는 문제이다. 실제 2048과 다른 점은, 움직일 때 새로운 블럭이 생성되지 않는다는 점이고 이동횟수가 5번으로 제한되어있다는 것이다. 전체적인 구성은 기본적인 dfs방식을 이용한 백트래킹+브루트포스와 동일하다. 다만 상,하,좌,우 이동 시 블럭들을 처리하는 것이 조금 까다롭다. 키포인트는 다음과 같다. 1. 합쳐지는 방향대로 각 열 또는 행들을 배..
https://school.programmers.co.kr/learn/courses/30/lessons/147355 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 입력의 최대 크기가 작아 N^2의 시간 복잡도를 이용해서 풀 수 있지 않을까 고민하다가, 분명 더 쉬운 방법이 있을 것 같은데..? 고민하던 중 팍 떠올랐다! 우선, Index out of range를 방지해주기 위해 p-1까지만 돌려준다. 그리고 만약 p가 3자릿수라면, 3개씩 잘라 배열에 담아준다. (이때 굳이 배열에 담지 않고 바로 비교해도 된다) 그리고 배열에 있는 걸 하나씩 꺼내 p와 ..
