Dalin's Archive

전에 한 코테에서 쓴 맛을 본 후로.. 백준에서 문제를 풀 때 분류를 안 보고 있다! 문제 풀이를 생각해낼 때 시간이 더 오래 걸리긴 하지만, 그래도 그만큼 더 생각하게 되는 것 같다!! 문제 보기 이 문제를 풀 때 한 생각들의 흐름, 풀이 한 위치에 여러 센서가 설치될 수 있다. 그렇지만 그럴 때 하나만 고려하면 된다. -> set을 이용해서 중복을 제거함. 각 센서의 번호 같은 건 중요하지 않다. 센서들을 정렬해서 봐야 겠다. -> sort 각 집중국의 수신 가능 영역의 거리 합이 최소가 되려면, 각 집중국 센서 수신 가능 영역의 시작점과 끝점은 센서 있는 곳인 게 좋겠다. 각 집중국 센서 수신 가능 영역이 조그마한 게 좋다 -> 센서 사이 간격이 큰 순서대로 K-1개 없애자!! 그리고 나머지 간격들..

문제로 가기 행의 번호와 열의 번호를 각각 등차수열로 봐주면서, 그 칸의 숫자를 이어 붙인다. 그랬을 때 만들 수 있는 정수 중 가장 큰 완전 제곱수!를 구하는 문제였다. 나는 기억이 안나는 수학적 개념이 하나 있어서 쓴다..ㅎㅎ 등차 수열: 연속하는 두 항의 차이가 일정한 수열 위키백과 (이미지 출처- 위키백과) 이러한 식이 나온다. 여기에서 d(두 항의 차이)를 '공차'라고 부른다. 예) 1-3-5-7-9 (2씩 차이), 4-10-16-24-30 (6씩 차이), 1-1-1-1-1 (0씩 차이), 100-99-98-97-96(-1씩 차이) 설명 🗝 a1 즉 첫째 항과 d, 즉 공차를 상황에 따라서 다 봐줬다. N, M이 9보다 작으니 브루트포스하게 쭉~ 봐줘도 되겠다고 생각했다. 그래서 4중 for문이..

문제 풀러 가기 행렬의 한 쪽 길이 N이 주어진다. 이 행렬에서 2X2 정사각형씩 보면서, 그 중에 2번째로 큰 수를 모아서 새로 행렬을 만든다. 그러다가 1X1 행렬이 되면 그때 남은 값을 출력해야 한다! 그러면 처음에는 행렬의 한 변은 처음에는 N이었다가 그 후에는 N//2가 된다. 그러다가 1이 되면 그때의 값을 리턴해야 하니까 그걸 종료 조건으로 생각했다. 또 2X2 정사각형들이 있을텐데, 그런 정사각형은 N//2 X N//2가 있다. 또 N//2 X N//2 사이즈의 새로운 리스트(tmp_arr)가 생기니 그 사이즈로 리스트를 만들어뒀다. 정사각형들의 가로 인덱스들은 0X2, 1X2, .... (N//2)X2에서 출발하게 된다. 세로 인덱스들도 마찬가지이다. 그 인덱스에서 시작해서 그 다음 인덱..

문제로 가기 길이가 3^N인 리스트를 만들었다. 칸토어 집합은 일단 -가 3^N개인 문자열에서 시작하니까~~ 그 후에 sol함수를 실행한다. 재귀함수인데, 몇 번 더 볼지, 시작점과 끝점을 받는다. 시작점과 끝점은 그 선 중에서 어느 부분을 보고 있는지를 뜻한다. 몇 번 더 볼지가 0이 되면, return한다. 그게 아니라면 시작점과 끝점을 가지고 3등분을 해서, 가운데 부분은 공백으로 바꾼다. 왼쪽과 오른쪽 부분은 또 sol 함수로 넣는다. 몇 번 더 볼지는 1 감소하고, 왼쪽과 오른쪽 부분의 시작점과 끝점을 구해서 그걸 넣는다. import sys input = sys.stdin.readline def sol(n, i, j): # 몇 번 더 볼지, 시작점, 끝점 if n == 0: return # 3..

재밌는 DP 문제였다!! https://www.acmicpc.net/problem/5535 날짜 별로 입을 수 있는 옷을 딕셔너리에 저장했다. 매일 날짜 별 온도를 쭉~ 보면서, 옷들도 쭉~ 보면서 그 날 그 옷을 입을 수 있는지 봐줬다. 위 정보를 활용해서 DP를 진행했다.(아래 그림 참고) 날짜 별로 쭉 ~ 보면서, 그날 입을 수 있는 옷들을 쭉~ 보는데, 그 전날 입을 수 있는 옷들을 쭉~ 봐줬다. 그러면서 dp[당일][당일 입을 수 있는 옷의 인덱스] = max(dp[당일][당일 입을 수 있는 옷의 인덱스], dp[전날][전날 입을 수 있는 옷의 인덱스] + abs(당일 입을 수 있는 옷의 화려함 - 전날 입을 수 있는 옷의 화려함))를 해주었다. 헷갈렸던 부분 👨🗝 첫날 말고 둘째날부터 시작한다..

https://www.acmicpc.net/problem/10282 컴퓨터 간 의존성이 주어진다. a가 b를 의존하면, b가 감염되면 a도 감염된다는 뜻이다. b가 감염된 후 a가 감염될 때까지의 시간도 알려준다. 해킹 당한 컴퓨터를 알려주면, 그 컴퓨터를 포함해서 총 몇 대가 감염되는지, 얼마나 시간이 걸리는지 구해야 한다. 처음에는 서로 연결되었는지 봐야 하니까 유니온 파인드가 잠깐 떠올랐다가, 얼마나 시간 걸리는지도 체크해야 하니까 접었다. 고민하다 보니 플로이드 워샬이 떠올랐다. 한 컴퓨터에서 다른 컴퓨터로 연결되는지, 해킹될 때까지 얼마나 시간이 걸리는지를 구할 수 있으니까 !! (플로이드 워샬로 해도 답은 나오잖아요 ? 메모리, 시간이 문제지..) 풀이 생각난 게 신나서 풀었다.. 예제는 풀리..

ㅠㅠ 분할 정복....5개월 전에 스터디 문제였는데 그때 뭔가 이해는 된 것 같은데 못 풀었다.. 분할 정복 문제들은 어떻게 쪼개지는지 까지는 대충 아는 것 같은데, 그걸 어떻게 코드로 구현할지 막막하다.ㅠㅠ 그래도 풀면 나아지겠지 !?! 친구의 도움을 받아서 푼 Moo 게임 !! 문제 보러 가기 풀이 🌸 1. moo() 함수 부분!! 일단 미리 각 k일 때 moo 수열의 길이를 구해서 m_list에 저장했다. N이 10의 9승까지 된다고 했는데, 그걸 포함하는 moo 수열의 k는 30이다. (S(30)이 10의 9승보다 길게 된다.) 그래서 moo(30)을 구하면 된다. 2. N과 같거나 큰 S(k)의 길이를 찾아준다. 그럼 moo 수열의 N번째 알파벳을 찾기 위해서는 Moo수열에서 S(k)를 봐주면 ..

TMI 🤸‍♀️ 싸피 자치회 회의 - 스터디를 하고 나니 좀 피곤했다. 스터디의 문제는 좀 어렵고 잘 이해가 안돼서ㅠㅠ 풀 문제를 찾다가 이 문제(2580)를 찾았다. 문제 보러 가기 문제를 읽다 보니 전에 비슷한 문제를 푼 생각이 났다. 바로 이 문제(2239)였다. 반 년 전에, 내가 세네 번째로 푼 백준 골드 문제였던 걸로 기억한다..! 추억의 문제 >

문제로 가기! 플로이드 워샬 문제인데, 사이클 부분을 판단하는 게 새로웠다. 사이클인지 판단하는 방법은 i에서 j로 가는 길이 있고, j에서 i로 가는 길이 있는지 봐주는 것이다. 같은 곳으로 가는 건 봐주면 안되므로 i==j인 경우는 continue했다. 처음에 INF를 401로 설정해서 틀렸다. V는 400까지 있고, 거리는 10000까지이므로 401X 10000를 INF로 잡으니 맞았다. ''' 운동 https://www.acmicpc.net/problem/1956 ''' import sys input = sys.stdin.readline INF = 401 * 10000 V, E = map(int, input().split()) board = [[INF] * (V + 1) for _ in range..

문제 풀러 가기! ㅠㅠ 많이 틀리다가 맞았다... 풀이 1초) 처음 설치된 것과 같음 2초) 모든 칸에 폭탄 설치됨. 3초) 처음에 설치되었던 폭탄이 폭발함. 4초) 모든 칸에 폭탄이 설치됨. 5초) 2초 대에 설치되었던 폭탄들 중 남은 폭탄들이 폭발함. 6초) 모든 칸에 폭탄이 설치됨. 7초) 4초 대에 설치되었던 폭탄들 중 남은 폭탄들이 폭발함. 예제의 그림을 보면 이해할 수 있을 것이다! 이렇게 해서 짝수 초일 때는 무조건 모든 칸에 폭탄이 설치되어있다는 걸 알 수 있다. 또 홀수 초의 경우에도 4초 주기로 돌아가는 걸 볼 수 있다. 그래서 %4를 이용해서 경우를 구해서 풀었다. N==1일 때 경우는 따로 빼둬야 한다. 그건 이 게시물을 보고 알았다.. 틀렸던 부분.... 진짜 모르겠어서, 친구한테..