live the life you love

www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 슬라이딩 윈도우를 활용하는 문제였다. 문제에서 K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 구하라고 했으므로 일단 어피치는 신경쓰지말고 라이언 인형이 딱 K개가 되는 구간만 확인해주면 된다. 항상 K개가 되는 것을 확인해야 하므로 슬라이딩 윈도우를 활용할 수 있는 것이다. 예제에서 라이언 인형의 위치는 0, 4, 6, 9 이다. 라이언 인형은 총 4개가 있으며 K가 3이기 ..

www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 누적 합을 구해놓으면 쉽게 풀리는 문제였다. 단, python의 경우 input( )이 아닌 sys.stdin.readline()을 써야 시간초과에 걸리지 않는다. 소스코드 import sys n, m = map(int, sys.stdin.readline().split()) _list = list(map(int, sys.stdin.readline().split())) _sum = [0 f..

www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제를 잘 읽자! 문제를 잘 못 읽어서 1시간을 고민하다가 질문검색을 통해 코드를 보고 문제를 잘못 읽은것을 깨달았다. 테트로미노 "하나"를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 주어진 종이에 여러 종류의 테트로미노를 놓고 그 중에 최대를 구하는 것이 아니다. 최대 500x500 크기의 종이에 테트로미노 1개를 놓고 놓인 부분의 합이 최대가 되는 것을 ..

www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기본적인 BFS에 방문했던 경로를 따로 저장하여 경로를 역순으로 탐색하는게 추가된 문제였다. 수빈이가 갈 수 있는 3가지 경로을 모두 큐에 같이 저장하고 해당 경로마다 탐색을하면 분명 시간초과 또는 메모리 초과가 발생할 것이다. 기본적으로 수빈이가 이미 갔던 경로는 파악하기 위해서는 bool 타입의 visited 배열로 단순히 방문체크만 해주는 것에 한가지를 더 추가해야한다. ..

www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 카테고리 분류에 BFS가 있어서 당황했던 문제이다. 이런류의 문제를 BFS에 접목시킨다는 발상을 하기가 어렵다. 실제 코테에 나왔다면 못풀었을 것이다. 어려웠고 놓쳤던 부분은 다음과 같다. '123' 을 R 연산하면 312가 아니라, '2031'이된다. 숫자는 무조건 4자리로 고정되어있기 때문이다. 숫자 하나당 4가지의 경우의 수가 발생해서 4^n 만큼의 경우의 수가 나올 거 같은데, 어떻게 시간 ..

www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 간단한 문제였지만 파이썬에서 람다를 활용하여 정렬하는 법을 알 수 있었다. 리스트에 들어오는 원소는 (Junkyu, 50, 60, 100)이다. 맨 앞에 문자가 있으므로 뒤에 숫자들도 문자로 인식된다. 그렇기 때문에 람다식에서 숫자들을 int로 형변환 해줘야 한다. 정렬순서는 문제에 나와있는 것과 동일하게 하면된다. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서..

www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹을 활용하는 문제였다. 스페셜 저지이므로, 답이 여러개 나올 수 있다. 3x3으로 처리된 부분을 어떤식으로 검사 해야할 지 아이디어가 잘 안떠올랐다. 구현 로직 입력받은 스도쿠에서 0이 들어간 곳의 좌표를 따로 저장한다 0이 있는 위치에 들어갈 수 있는 후보 숫자들을 리스트에 저장한다 1부터 9까지 저장된 리스트(numbers)를 생성한다. 스도쿠 전체를 탐색하며 행, 열, 3x3 배열에 있는 0이 아닌..

www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제의 구현 로직은 다음과 같다. 모든 치즈가 다 녹았는지 확인한다. 남은 치즈가 있다면 전부 녹을 때 까지 아래의 과정을 반복한다. 다른 치즈 내부 공간에 있지 않은 치즈들 중 외부 공기와 2개 변 이상 접촉한 치즈를 체크한다. 체크된 치즈를 녹인다. 1, 3번은 크게 어렵지 않은데 2번이 조금 까다로운 편이었다. 단순히 상,하,좌,우 중 공기인 칸이 2개 이상인지만 확인하면 안된다. 왜냐하면 상하좌..

https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 전형적인 BFS 탐색을 활용해서 푸는 문제였다. 상근이는 무조건 집 -> 편의점 -> 편의점 .. -> 페스티벌 로 움직이기 때문에 다음번 편의점에 가서 항상 맥주를 최대로 살 수 있다. 굳이, 이동할 때 마다 이동거리를 50m로 나누면서 이동 가능 여부를 판단하지 않고 맥주를 20개 먹었을 때 갈 수 있는 최대 거리인 1,000m를 기준으로 다음번 편의점 또는 페스티벌 장 까지의 거리가 1..

www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS를 활용해 사이클 여부를 판단하는 문제이다. 사이클 여부를 판단하는데 익숙하지 않아서 다른 사람들의 코드를 보고 풀었다. 꼭 복습해야한다, 소스코드 import sys sys.setrecursionlimit(111111) # 재귀 깊이 설정 sys.stdin = open("input.txt", "r") def dfs(cur): global cnt, visited, done visited[cur] = True n..