Dalin's Archive

문제로 GO !! 처음에 어떻게 풀까 하다가, 아래 '이분탐색'이라는 알고리즘 분류를 보고 힌트를 얻어서 풀었다. '블루레이 크기'를 기준으로 삼아서 이분 탐색을 했다. 블루레이 크기의 최소는 1이고(강의 수가 1개 이상이고, 기타 강의도 자연수로 주어진다고 해서) 최대는 sum(lectures)이다. 만약에 M이 1이라고 생각하면, 하나의 블루레이에 모든 강의를 담아야 하니까 그때 크기가 sum(lectures)이다. 그래서 left =1, right= sum(lectures)를 시작으로 해서, 계속 이분 탐색을 했다. mid를 구해서, 그 크기의 블루레이 M개로 강의를 모두 잘 담을 수 있는지 체크했다. (check 함수) 잘 담을 수 있으면, 일단 ans을 업데이트하고 ..

문제 보러 가기 정말 브루트포스하게 풀었다. 하나 하나 따지면서!! 도시 정보를 다 보면서 치킨집 위치 찾기. 찾는 김에 개수도 세기 치킨집이 M개보다 크면, 치킨집 중 M개 뽑기(순서 상관 없으니 조합) - 치킨집이 M개 이하이면, 따로 뽑을 필요 없음. 각각의 경우를 보면서, 도시의 치킨 거리 계산하기. (도시 정보를 쭉 보면서 집을 만나면, 집마다 '치킨 거리' 찾기. 집마다 치킨 거리 찾을 때는, 그 경우에 남겨두기로 한 치킨집들을 다 돌아보면서 젤 가까운 거리를 찾음.) 가장 도시의 치킨 거리 작을 때가 정답! import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) N, M = MIIS() cit..

문제 보러 가기 접근 BFS로 풀었다. 큐에서 단어를 꺼내면 -> 그 단어에서 토 달기 규칙을 지키면서 사전에 등재된 단어들을 큐 안에 넣어줬다. 이게 check 함수이다. 어떤 단어(target_word)가 들어오면, 사전을 쭉 ~ 본다. 그러면서 target_word에서 토달기를 했을 때 사전의 해당 단어가 될 수 있다면, 리스트에 넣었다. 일단 토달기는 한 글자만 더할 수 있으니까, 사전의 단어 길이가 target_word+1인지 봤다. 아니라면 continue. 그 다음에 토달기 방식 중에 맨 앞이나 맨 뒤에 한 글자 넣는 경우를 봤다. 단순하게 in으로 체크했다. 마지막으로는 토달기 방식 중 중간에 한 글자 넣은 경우인지 봤다. 이 부분이 젤 까다로운 것 같다. 나는 while을 이용해서 사전에..

문제 풀러 가기 풀이 🍅 | 한 마디로 하면 벽 부수고 이동하기 문제와 비슷하게 풀었다! 일단 최단 거리를 알아내는 문제니까 BFS로 풀어야 겠다고 생각했다. 그런데 특이한 것은 K번까지 말의 움직임처럼 움직일 수 있다는 것이다. 벽도 있으니까,, 무조건 K번 말의 움직임을 다 쓴다고 최소 동작으로 목적지까지 가는 것도 아니고.. 어쩌면 0번 말처럼 움직였을 때가 최소 동작일 수도 있을 것이다. 그래서 몇 번 말처럼 움직였는지를 고려해서 visit 체크를 3차원 리스트로 만들었다. K는 최대 30이니까 괜찮다 ! 나머지는 일반적인 BFS처럼 하면 된다. 코드 🖥 import sys from collections import deque input = sys.stdin.readline dx, dy = [0,..

문제 보러 가기 N개 정수로 이뤄진 수열이 있다. 크기가 양수인 부분 수열(원소가 1개 이상인 부분 수열이라는 뜻 같다) 중에서 원소들을 다 더한 값이 S가 되는 경우의 수 구하기!! dfs에서 몇번째 인덱스를 볼건지(depth), 그때까지 부분 수열에 포함한 원소의 인덱스들(history), 그때까지 부분 수열 원소들의 합(total)을 가지고 다녔다. 크기가 양수이고(=history가 빈 문자열이 아니고), 그 수열 원소를 다 더한 값이 S면 그때까지의 history(몇 번 몇 번 인덱스를 포함했는지)를 set에 넣어줬다. depth번째 수를 포함하는 부분 수열을 만드는 경우, 포함하지 않는 부분 수열을 만드는 경우를 따져주었다. 처음에는 런타임에러(RecursionError)가 떴다..ㅠㅠ N이 최..

문제 풀러 가기~ 풀이 일단은 공기 청정기 위치를 찾았다. 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기 청정기의 위쪽 행을 찾았다! 그리고 미세먼지가 확산되는 일, 공기 청정기가 작동할 때 일어나는 일을 함수로 만들었다. 미세먼지가 확산될 때는, 미리 어떤 곳에 미세먼지가 있고, 얼마나 있는지 파악해서 리스트에 넣은 후에, 그 리스트를 돌면서 인접한 네 방향으로 확산되게 했다. 또 그 위치의 미세먼지 양도 바꿔주었다. 사실 처음에는 미리 미세먼지의 위치, 양을 저장하지 않고 그냥 for문 두개로 미세먼지 있는 곳을 만나면 확산되게 했다. 그러면 원래는 미세먼지가 없었는데, 미세먼지 확산으로 이제 미세먼지가 있는 곳도 원래 미세먼지가 있던 곳처럼 처리된다. 미세먼지의 양도 원래 양만큼이..

문제로 ~ 스택을 구현하는 문제이다! 파이썬 list의 메서드들(append, pop, len, S[-1] 등)로 풀면, 시간 초과가 나온다ㅠ import sys input = sys.stdin.readline N = int(input()) S = [0] * (10001) idx = -1 for i in range(N): command = input().strip() if command == "pop": if idx == -1: print(-1) else: print(S[idx]) idx -= 1 elif command == "size": print(idx + 1) elif command == "empty": if idx == -1: print(1) else: print(0) elif command ==..

문제 보러 가기 접근 🔥 자기보다 높은 블록이 좌우에 있어야 빗물이 고인다! 높이 별로 쭉~ 돌면서, 그 높이보다 낮게 쌓인 지점이 있는지 보았다. 그 지점이 있으면, 그 지점에서 왼쪽과 오른쪽에 그 높이보다 높게 블록이 쌓였는지 보았다. 양쪽에 그 지점보다 높게 블록이 쌓인 지점이 있으면, 그 지점에는 물이 고일 수 있다. 그림에서처럼 1번 동그라미들에서 각각 좌우에 본인보다 높은 지점이 있는지 봐주고, 2번 동그라미 친 부분에서도 그렇게 하고.. 이렇게 다 봐줬다.. 최악의 경우를 생각해봤는데, 500(높이) X 500(너비) X 500(좌우 봐주는 것) 정도니까 시간 내에 통과할 것 같아서, 이렇게 코드를 짰다.. 좀 비효율적인 것 같긴 하지만 시간 내에 통과는 했다. 다른 분들의 코드도 봐야겠다~..

[문제 보러 가기](https://www.acmicpc.net/problem/14940 평범한 BFS 문제였다. visited를 만들어서 방문 체크 겸, 거리 체크를 했다. 처음에는 '원래 갈 수 없는 땅인 위치는 0으로 출력'해야 하는데, 원래 갈 수 없는 땅이고 도달할 수 없는 위치면 -1로 출력해서 틀렸다. 그리고 i, j 오타가 나서 틀리다가 맞았다..! i, j.. 비슷하게 생겨서 주의해야 겠다. import collections import sys input = sys.stdin.readline MIIS = lambda: map(int, input().split()) directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] n, m = MIIS() a..

문제로~ RGB거리 1을 풀고, RGB 거리 2도 있길래 스터디 문제에 넣었다. RGB 거리 1은 괜찮았는데,,, 이 문제는 좀 더 생각을 해야 한다. 달라진 거라고는 1번 집 색깔과 마지막 집 색깔이 달라야 한다는 것 뿐이다. 그런데 훨씬 어렵다..ㅠ 아이디어가 잘 안떠올랐다.. 1번 집의 색깔을 기억(?)하고 있어야 한다는 거니까, R, G, B 각각에서 출발해 보면 된다. 또 첫번째 집과 마지막 집 색깔이 달라야 하니까, 정답(ans)을 구할 때 마지막 집을 R, G, B로 색칠한 결과(첫번째~마지막 집 색칠한 최소 비용) 중 첫번째 집과 색깔이 같은 건 고려하지 않아야 한다. R, G, B 각각에서 출발하는 것을 구현하려면.. => 다른 곳의 값은 크게 두고, 해당 색깔으로 칠하는 경우만 그 때 ..