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와 ..
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 점수가 큰 과제를 많이 먹어야하는데, 마감 기간을 잘 고려해서 스켸쥴을 짜면 된다. 우선 점수가 큰 순으로 정렬한 뒤, 이제 스켸쥴 표를 하나씩 채워나가면 된다. 해당 위치에 이미 값이 있으면 (= 그날 할 과제, 즉 계획이 있으면) 앞으로 날짜를 당기면서 빈 곳에 계획을 채워넣는다. 결국, 1 ~ m일차까지의 스켸쥴 표를 작성한다고 생각하면 쉽다! (여기서 m은 과제 마감일 중 제일 큰 값, 코드에서 cnt값) import sys sys...
