매일 매일 성장하는 섭섭군

이번에 풀어볼 문제는 백준 3649번 '로봇 프로젝트'라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 문제 상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다. 구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길 www.acmicpc.net 제한시간이 5초나 되는만큼 시간복잡도를 고려하지 않는다면 시간초과가 날 문제입니다. 저는 최대한 시간을 줄이기 위해 딕셔너리를 사용했습니다. 딕셔너리를 사용한 이유는 특정 값을 찾고자 할때 key in dict 형식을 사용할 경우 O(1)이기 때문입니다. 2개의 딕셔너리를 활용하였는데 내부의 구조는 다..

이번에 풀어볼 문제는 백준 2667번 '단지번호붙이기'라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 필자는 BFS를 활용해서 문제를 해결하고자 하였다. 그래서 다음과 같은 방법으로 코드를 작성했다. 1. 모든 값이 0인 N*N 배열을 생성한다. (BFS를 수행하기 위해 내가 방문한 곳을 기록하기 위해서이다.) 2. 집이 있는 위치('1')를 따로 저장한다.( x, y 형태로 저장하여 바로 접근 할 수..

이번에 풀어볼 문제는 백준 2493번 '탑'이라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net 단순하게 생각해서 문제를 풀어보면 다음과 같은 풀이법이 있을 수 있습니다. 1. 주어진 배열을 뒤에서 부터 읽습니다. 2. 읽은 배열부터 다시 뒤에서 부터 읽어 자신보다 큰 수가 나오면 정답 배열에 해당 인덱스를 저장합니다. 참 간단하죠? 하지만 이러한 방법은 굉장히 많은 시간이 소요되게 됩니다. 그래서..

이번에 풀어볼 문제는 백준 2688번 문제인 '줄어들지 않아' 라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 문제 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다. 예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, www.acmicpc.net 줄어들지 않는 수를 각각 구하게 된다면 시간초과가 발생할 것입니다. 64자리까지 있으니까 말이죠 그렇다면 각 자릿수의 경우들간의 관계를 살펴보면 좀 더 쉽게 풀 수 있을 것 같습니다.(다이나믹 프로그래밍을 사용했습니다.) 먼저 자리수에 따른 경우의 수를 살펴보면 다음과 같습니다...

이번에 풀어볼 문제는 백준 4889번 안정적인 문자열이라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 문제 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다. 빈 문자열은 www.acmicpc.net 알고리즘 문제를 몇번 풀어보신 분이라면 올바른 괄호를 구성하는 문제는 한번쯤을 풀어보셨을 것이라 생각이듭니다. 하지만 이 문제는 올바를 괄호를 체크하는 것 뿐만 아니라 바르게 만들어 주어야 합니다. 그리고 바르게 만들기 위해 괄호를 뒤집어야 하는 최소 횟수를 정답으로 요구합니다. 문제해결 IDEA - 왼쪽..

이번에 풀어볼 문제는 백준 5567번 결혼식 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/5567 5567번: 결혼식 문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. www.acmicpc.net 처음에 접근할 때에는 트리를 이용해서 풀어볼까 생각했지만 다른 간단한 방법도 생각나서 풀이를 진행했습니다. 접근 아이디어 - 1번(나)를 포함하여 모든 동기의 번호를 dict에 저장한다. - 1번(나)이 가지고 있는 Value를 Set(집합, 중복을 허용하지 않는다.)로 저장시킨다. - 1번(나)이 가지고 있는 각각의 값..

이번에 풀어볼 문제는 백준 9237번 문제은 이장님의 초대 라는 문제입니다. 문제는 다음과 같습니다 https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 문제 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 �� www.acmicpc.net 알고리즘 분류에는 트리로 분류되어 있지만 필자는 약간 다른 방식으로 풀이를 진행하였습니다. 1. 묘목들을 오름차순으로 정렬합니다. 2. 묘목의 0번째 순서는 0 을빼고 i 번째 순서에는 i 를 빼는 연산을 진행해 줍니다. 3. 전체 묘목의 수와 2번을 거친 후 묘목들 중 최댓값을 더해주면 가장 짧..

이번에 풀어볼 문제는 백준 1068번 트리 라는 문제이다. 문제는 다음과 같다. https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 필자는 본문제를 트리를 직접 만들어서 풀었다. Node Class 와 Tree Class 를 정의하고 이를 사용하였다. 다음과 같이 작성하였다. class Node: # 노드 클래스에는 노드의 이름(data)와 자식으로 구성되어 있다. # 자식이 없으면 None이며 있다면 배열에 저장되도록 구현하였다. def _..