ULISIA's Developer Life

출처:5567번 결혼식 문제해석 N=동기의 수 상근이는 1번이므로 결과에서 포함되지 않음 친구와 친구의친구까지만 포함 1번 노드(상근이)를 시작으로 너비 우선 탐색(BFS)를 진행하면서 거리(dist)가 2 이하인 노드들의 개수만 세주면 된다. 해답코드 # 결혼식 import sys from collections import defaultdict, deque def bfs(start): ans=0 isVisited = [0 for _ in range(n+1)] isVisited[start] = 1 q = deque([[start,0]]) while q: u, dist = q.popleft() if dist

출처:14002번 가장 긴 증가하는 부분 수열 4 문제해석 수열을 받으면 그중 길이가 제일 긴 증가하는 수열을 구하는 문제이다. 최장 증가 부분 수열(LIS, Longest Increasing Subsequence) 알고리즘이라는 알고리즘 문제에서 자주 볼 수 있는 것을 사용하여 길이를 구할 수 있다. 이 문제에서는 길이뿐만 아니라 해당 수열까지도 결과값으로 출력해야 한다. 해답코드 #가장 긴 증가하는 부분 수열 4 import sys input = sys.stdin.readline n = int(input()) array = list(map(int, input().split())) dp = [1] * n #최장 부분 증가 수열 길이를 구하는 for문 for current in range(n): for ..

출처:1748 수 이어 쓰기 1 문제해석 문제를 풀기 전에 딱 보기에도 가장 반복문으로 모든 수의 자릿수를 일일이 더하는 식으로 구현을 진행하면 시간초과가 나올 것 같은 문제였다. 일반적으로 파이썬 프로그램에서는 2,000만 번~1억 번의 연산을 1초의 수행 시간으로 예측할 수 있다. 코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다. 또한 연산 횟수는 1초에 2,000만 번 연산하는 것을 기준으로 계산하는 것이 좋다. 응시자가 작성한 프로그램으로 모든 케이스를 통과해야만 합격으로 판단하므로 "최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다. 그렇기에 이번 문제..

11559번: Puyo Puyo 문제해석 흔히 알고 있는 뿌요뿌요 게임이다. 필드를 배열에 초기화 시켜준다. 입력받은 필드를 탐색하다가 뿌요를 만나면 BFS 알고리즘을 시작한다. 뿌요의 근처에 같은색의 뿌요가 몇개인지 체크한다. 같은 색의 뿌요가 4개 이상일 경우 해당 뿌요들을 연쇄시켜 없앤다. 연쇄가 일어난 후에 뿌요들을 아래로 떨어뜨리고 연쇄수를 하나 늘려준다. 연쇄가 더 이상 없으면 탐색을 종료한다. package anystep; import java.io.*; import java.util.*; public class Java_11559 { //Puyo Puyo // 1. 필드를 배열에 초기화 시켜준다. // 2. 입력받은 필드를 탐색하다가 뿌요를 만나면 BFS 알고리즘을 시작한다. // 3. 뿌..

출처:16235번: 나무 재테크 문제해석 글이 길어서 그렇지 차근차근 따라가다 보면 어떤 순서로 구현을 해야하는지 알 수 있게 된다. 모든 배열의 인덱스의 초기결과값을 5로 초기화 M개의 나무리스트 전체를 탐색한다. 3~5 봄 페이즈 하나의 칸에 같은 나무가 동시에 존재한다면 나이가 어린순으로 동작한다. 나무의 나이만큼 해당칸의 양분을 빼고 나무의 나이+1 만일 나무의 나이>해당 칸의 양분 = 나무사망 6 여름 페이즈 봄에 죽은 나무리스트 탐색 나무 나이/2를 해당 나무 칸의 양분에 더한다. 소수점 아래 버림 7 가을 페이즈 나무리스트 탐색 나무의 나이가 5배수일 경우 인접 8칸 나이 1 나무 나무리스트 추가 8 겨울 페이즈 처음 입력받은 A배열의 각 인덱스 결과만큼 배열에 추가 K년이 지난 후 생존한 ..

출처:1652번: 누울 자리를 찾아라 문제 해석 가로 혹은 세로로 2칸 이상 연속으로 빈 공간이 나온다면 해당 가로줄 혹은 세로줄은 사용할 수 있는 공간이다. 한 번 누운 줄은 무조건 몸을 쭉 뻗기 때문에 해당 줄에서 짐으로 나누어진 공간이 없다면 더 이상 다른 공간을 사용할 수 없다. 즉 이 문제는 가로와 세로를 기준으로 2중 반복문을 돌면서 2칸 이상 연속으로 . 문자가 있는 줄을 탐색하는 문제이다. 해답코드 package anystep; import java.io.*; import java.util.StringTokenizer; public class Java_1652 { //누울 자리를 찾아라 static BufferedReader in = new BufferedReader(new InputStr..

출처:1244번: 스위치 켜고 끄기 문제 자체는 상세히 설명이 되어있으므로 별다른 해석이 필요하지는 않았다. 문제 해석 문제에서 중점적으로 다루어야 할 요소는 크게 세가지다. 스위치. 사람의 성별. 사람에게 주어진 수. 이 문제를 처음부터 풀어가는 진행과정을 차근차근 요약해 보겠다. 스위치의 개수 int N 입력받기 스위치의 개수만큼 스위치들을 저장할 수 있는 int[] Switch 초기화 사람의 수 int M 입력받기 사람의 수 M 만큼 반복하며 사람의 성별 gender와 주어진 수 num에 의한 조건문 4-1. 만일 성별이 남자라면 주어진 수의 배수만큼 Switch 배열의 수를 뒤집는다. 4-2. 만일 성별이 여자라면 기준점을 뒤집은 후 기준점+-k(k는 증감값)가 1혹은 N보다 작거나 클 경우 반복..

출처:10812번: 바구니 순서 바꾸기 문제 이해 바구니의 수(N = 10개) 회전 수(M = 5회) 1 2 3 4 5 6 7 8 9 10 시작 바구니 (i = 1) 끝 바구니 (j = 6) 기준 바구니 (k = 4) 1 2 3 4 5 6 7 8 9 10 i i+1 k-1 k k+1 j j+1 j+2 j+3 j+4 4 5 6 1 2 3 7 8 9 10 k k+1 j i i+1 k-1 j+1 j+2 j+3 j+4 시작 바구니 i와 끝 바구니 j 사이의 순서를 바꾼다. 시작 바구니 i가 기준 바구니 k가 되고 k+1부터 끝 바구니 j까지 바꾼다. 바꾼 이후의 j+1 부터의 바구니는 바꾸기 전의 i부터 k-1까지의 바구니를 담는다. 이 과정을 M번 반복해서 최종적으로 나온 결과 값을 출력한다. 한번의 회전 과..