매일 매일 성장하는 섭섭군

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

이번에 풀어볼 문제는 백준 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번(나)이 가지고 있는 각각의 값..

이번에 풀어볼 문제는 백준 7453번인 합이 0인 네 정수라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주�� www.acmicpc.net 문제를 살펴보면 4개의 배열이 있고 각 배열의 원소를 하나씩 적출해내어 합을 0으로 만들면 되는 문제입니다. 필자는 처음 시도할때 조합을 이용하여 풀고자 했습니다. itertools 의 product 을 활용하면 각각의 배열에 있..

이번에 풀어볼 문제는 백준 2910번인 빈도 정렬 문제이다. 문제는 다음과 같다. https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 문제 위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다. 창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 �� www.acmicpc.net 들어온 순서와 빈도를 고려하기 때문에 요전에 풀었던 1713번과 매우 유사한 방법으로 해결 할 수 있다. 하나의 딕셔너리를 생성 한 후 다음과 같이 적재한다면 어렵지 않게 해결 할 수 있다. Key : 메세지 Value : [빈도, 들어온 순서] 딕셔너리에 전부 적재 했다면 정렬을 통해 진행 답을 도출해 내면 끝이다. ..

이번에 풀어볼 문제는 백준 10546번인 배부른 마라토너 라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 문제 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, www.acmicpc.net 본 문제에서 가장 주의깊게 살펴 봐야 하는 것은 동명이인이 존재 할 수 있다는 것 입니다. 만약 모든 사람의 이름이 다르다면 배열이나 딕셔너리에 없다면 그 이름이 정답일 것 입니다. 저는 동명이인 문제를 다음과 같이 해결했습니다. 1. 참가한 사람들의 dict를 생성하고 적재한다. 적재하는 ..

이번에 풀어볼 문제는 백준 9933번인 민균이의 전화번호라는 문제입니다. 문제는 다음과 같습니다. https://www.acmicpc.net/problem/9933 9933번: 민균이의 비밀번호 문제 창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다. 파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다. 예를 들어, 민균이의 비밀번호가 www.acmicpc.net 문제를 요약해보자면 다음과 같습..