전체 글

[Python] 1058 - 친구 (실버3)

1. 문제 설명 https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net 2. 아이디어 당시에 이 문제를 풀 아이디어를 떠올리지 못해서 구글링을 통해 찾아낸 방법이 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)이었는데 애초에 다이나믹 알고리즘도 모르던 내가 이걸 100% 이해할 수 있었을리가 없다. 근데 난 왜 이걸로 문제를 풀어놨을까..? 분명한 건 구글링의 도움을 받아 문제를 풀었었다. 알고리즘에 대한 포스팅은 이후에 한 번에 정..

[Python] 1850 - 최대공약수 (실버1) : 유클리드 호제법

1. 문제 설명 https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 사실 나도 잊고 있었던 풀이법인데 다시 보니까 기억났다. 이래서 사람이 복습을 해야 돼 2. 아이디어 가장 처음에 떠오르는 무식한 방법은 a와 b값을 입력받고, 진짜 1111(4), 111(3)의 값을 저장하여 연산과정을 거치는 방법일 것이다. 문제를 어느정도 풀어보면 알겠지만, 이 방법은 절대 통과가 안 될 거라는 것을 짐작할 수 있다. (지금 생각해보니까 ..

[Python] 1051 - 숫자 정사각형 (실버4)

1. 문제 설명 https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 2. 아이디어 brute-force(전탐색)으로 해결했었다. 행과 열을 모두 옮겨다니면서 가로와 세로 중에 더 짧은 쪽을 기준(정사각형을 찾아야 하니까)으로 현재 지점(vertex)과 나머지 꼭짓점의 값이 같은 지점을 찾고, 현재 좌표에서 찾은 최대 넓이를 square 리스트에 저장시켜 둔다. 만약 값이 있다고 하더라도 현재 위치에서 찾은 더 큰 값이 있다면 if문에 걸리지 않는다..

[Python] 1018 - 체스판 다시 칠하기 (실버4)

1. 문제 설명 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 기억은 안 나지만 당시에 나름 어려웠던 것 같다. 실버 단계가 어려운 이유는 내가 너무 문제를 복잡하게 이해하려 하기 때문이지 싶다. 때론 단순무식한 방법들이 효율적인 해결책이 될 수 있다. 특히 실버 단계에선 대부분 그렇다. 물론 그 중에서 종종 특출난 아이디어를 필요로 하는 함정 문제들이 있긴 하지만 :) 2. 아이디어 어디나 상관없이 새로 칠해야 하는 경우가 가장 작은..