친절한 도현씨 친절한 도현씨

★ 접근 N의 최대 크기를 이십만으로 제한했기 때문에 모든 경우를 다 탐색할 경우 시간초과가 나올 것이라 생각했다. 그래서 그리디로 접근해보자고 생각을 했다. ★ 풀이 처음에는 모든 집에 대해서 안테나 거리들의 합이 최소일라면 가운데에 있으면 되는 것이 아닌가 했다. 너무 간단하다고 생각을 했고 코드도 너무 짧을 것 같아 확신이 없었다. 결국 다른 방법으로 해봤는데 틀렸다. 설마하고 첫 생각대로 해봤는데 통과돼서 허무했다. import sys input = sys.stdin.readline N = int(input()) house = list(map(int,input().split())) house.sort() print(house[(N-1) // 2])

★ 접근 방식 - 입력에서 n,m의 최대 크기가 50이라고 했을 때 모든 경우의 수를 다 보아도 시간측면에서 크게 무리가 안 갈 것이라고 생각했다. 처음에는 이분탐색, 그리디라고 생각했다. 이분탐색을 쓰기에는 기준이 될 만한 값이 없어서 그리디라고 결정지었다. ★ 풀이 - 마지막에는 원 점으로 돌아오지 않아도 되기에 절댓값이 맨 왼 쪽이 클지, 맨 오른쪽이 클 지 생각하는 두 가지 경우가 있다. 여러 조건문을 써가면서 절댓값이 어느 쪽이 더 클 지, -의 부호로만 이루어져 있을 지, +로만 이루어져 있을 지로 풀어 볼 수 있지만 너무 난잡해질 것 같애서 맨 왼쪽이 더 크다고 가정한 함수, 맨 오른쪽이 더 크다고 가정한 함수 두개를 비교해서 더 작은 값을 리턴한 것을 출력해줬다. n,m = map(int,..

예전에 한 번 풀었었는데 스터디로 인해 한번 더 풀게 됐다. 한번 풀어보기도 했고 간단한 탐색 문제였기에 자신있게 풀었지만 92%에서 틀렸다고 나왔다. 알고리즘적으로 틀릴 이유가 없다고 생각해서 많이 헤맸다. 풀이 익은 토마토들을 한 번에 영향력을 주기 때문에 처음에 1이 어디있었는지 다 찾아서 deque에다가 넣는다. 그 다음에 순서대로 하나씩 꺼내어 주변 익지 않은 토마토가 있다면 현재 좌표에서 +1을 해서 토마토를 익게 해주고 이제 이 토마토도 deque에 넣는다. 헤맸던 지점 if flag == 1:이라는 조건을 한번 더 체크해줬어야 했는데 누락시켰다. 옜날이었으면 이런데서 실수하지 않고 오히려 구현을 못했을 텐데 반대가 됐다. 세세한 부분도 신경을 쓰는 습관을 들여야겠다. from collect..

# 문제에서 예를 든 것이 꼬리에 꼬리를 물고 있는 것이 4개 있었기에 예제 2번을 봤을 때 왜 1인지 몰랐다. # 혹시 친구의 친구가 나와도 친구인 건가라는 생각이 들었지만 예제 3에서 아니라고 말을 해주었다. # 그렇다면 왜 예제2는 1인거지? 여기서 한 번 반례를 생각을 하고 아니었으면 문제에서 이해한 것이 맞다고 생각을 하고 다시 처음으로 돌아와서 생각을 했어야 됐는데 뇌가 비벼져서 혼자 예제를 만들기 시작했다. # 결국 예제2만 이해하는데 약 1시간을 쏟았다. # 문제에서 이해한 것이 최대한 맞다고 생각을 하고 이해되지 않는 예제가 보이면 한 번 반례를 생각하고 아니면 다시 원래 대로 돌아오는게 맞는 것 같다. n,m = map(int,input().split()) data = [[] for _..

몇 달전에 톱니바퀴 문제를 풀었었는데 무슨 차이가 있는지 싶었다. 당시 틀린 부분이 없다고 생각하는데 계속 틀려서 헤매다가 겨우 맞췄던 기억이 있다. 톱니바퀴(2)도 똑같이 틀린부분이 없다고 생각이 들었고 2시간 정도를 다시 짜보고, 주석 다 달아보고, 손으로 하나하나 써보고 다 해봤다. 그러다가 헤맨 지점을 발견했는데 생각해보니 톱니바퀴에서도 똑같은 부분으로 헤맸었다. ※ 헤맸던 지점 처음에 입력받는 회전시킬 톱니바퀴는 맞닿은 부분들이 서로 같더라도 무조건 회전시켜줘야 한다는 것이다. from collections import deque T = int(input()) data = [] for _ in range(T): data.append(deque(input())) K = int(input()) # ..

처음에 코드를 봤을 때 떠올렸던 알고리즘은 완전탐색이었고 조합을 생각했었지만 시간초과가 나올 것 같아서 바로 이분탐색으로 생각을 전환했다. mid 값을 무엇으로 정해야하며 mid가 정해진 기준으로 무엇이 left,right를 어떻게 움직여야 할지 많이 고민했다. 고민을 2일 정도 한 결과 블루레이의 길이를 기준으로 하자하고 코드를 작성했지만 53%로에서 계속 틀렸다고 나왔다. 더 이상 고칠 게 없을 것 같아서 다른 사람들의 코드를 보았지만 별반 차이가 없는 것 같아서 반례를 찾아보았다. 7 6 100 400 300 100 500 101 400 이라는 반례를 찾았다. 글쓴이는 left를 테스트케이스만 보고 리스트의 끝 값을 넣어뒀다. 여기서 문제를 잘 읽어야한다. 문제에서 강의 순서별로 길이를 제공한다 했..

이 문제는 다익스트라알고리즘과, 0-1 너비 우선 탐색을 이용하여 풀 수 있다. 여기서는 처음 들어본 0-1 너비 우선 탐색을 다뤄보겠습니다. 0-1 너비 우선 탐색이 무엇인지 구글링을 열심히 해보고 많은 블로그들을 읽어보았지만 이해가 되지 않거나 그냥 0은 appendleft 1은 append하세요라고 언급만 하는 글들이 많아서 어려움을 겪었다. 결국 0-1bfs 코드를 하나 가지고 여러가지 예시들을 만들어 놓고 한줄한줄 손으로 실행하면서 노트에 적어봤다. 손코딩을 해보니 0일 경우 appendleft를 해왔으니 0이 었던 좌표아거나 0인 좌표와 붙어있던 상,하,좌,우 좌표들을 우선적으로 만나게 된다. 그러다가 최종 좌표 m-1,n-1에 도착한다. (당연한 것 아니냐고 생각이 드실 수 있겠지만 저는 이..