매일 매일 성장하는 섭섭군

이번에 풀어볼 문제는 백준 9020번인 골드바흐의 추측이라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수 www.acmicpc.net 문제를 보면 일단 소수를 구할 수 있어야 한다. 여러가지 테스트케이스가 주어짐으로 필자는 10000까지의 소수를 전부 구한 후에 문제를 풀었다.(사실 이과정만 잘 한다면 문제는 쉽다.) 소수를 구하는 방법으로는 에라토스테네스의 체 라는 방법을 사용했다. 에라토스테네스의 체는 2부터..

이번에 풀어볼 문제는 백준 2504번인 '괄호의 값' 이라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net Python으로 푸는경우 +, * () 문자열을 추가시켜서 풀 수 있는 방법도 있지만 저는 스택을 사용하여 풀었습니다. 문제풀이 IDEA - 소괄호, 대괄호 스택을 만들어줍니다. - 문자열의 길이만큼의 0 배열을 만들어줍니다.(total 배열) - "(" 일 때 소괄호 스택에 해당 인덱스를 추가해주..

이번에 풀어볼 문제는 백준 6416번 '트리인가?'라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/6416 6416번: 트리인가? 문제 트리는 굉장히 잘 알려진 자료 구조이다. 트리를 만족하는 자료 구조는 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이고 방향 간선이 존재하며 다음과 같은 조건을 만족해야 �� www.acmicpc.net 이번 문제는 문제에서 제시한 트리를 만족하는 조건을 잘 구현해 주면 된다. 편의상 들어오는 간선은 부모 노드, 나가는 간선은 자식 노드라고 하겠습니다. (위의 제일 왼쪽 트리에서 5의 자식 노드 : 3,6,2 , 6의 부모노드 : 5 ) 1. 단 하나의 루트만 존재한다. -> 루트노드가 2개 이상 있으면 ..

이번에 풀어볼 문제는 백준 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 - 왼쪽..