Dalin's Archive

문제 보러 가기! 가지치기 없이 그냥 DFS로 풀었다~ N의 범위가 작아서, 그냥 해도 되는 것 같다! 시간 복잡도는 3^9 * 10 인데, 계산하면 196,830. 1초 내에 충분히 계산될 수 있다. DFS로 하고 DFS에 history와 idx를 만들었다. idx는 1부터 N까지 어떤 숫자를 볼 차례인지 담당한다. idx가 N+1이 되면 숫자를 다 본 것이다. 이때 수식의 결과가 0이 되는지 체크하면 된다! idx가 N+1 미만일 때는, 매번 +, -, 공백(숫자 이어지는 것) 의 경우로 재귀를 돈다. 헷갈렸던 부분! 바로 바로 idx가 N+1될 때 출력하면 안되어서(ASCII 순서에 따라서 출력하라고 함), 되는 경우를 리스트에 넣었다가 정렬한 후에 출력했다. ㅠㅠㅠ 계속 '출력 형식이 잘못되었습니..

문제 풀러 가기! 재미있는.. 그리디 문제였다.. ^^ 일단 입력을 받는다. 0, 0 이 나올 때까지 받으니까 while을 이용했다. 혹시 몰라서 출발점과 끝점이 같으면 받지 않았고, 출발점이 음수이고 끝나는 점이 0 이하이면 받지 않았다. 그리고 정렬~ 출발점 빠른 순 -> 출발점이 같으면 끝나는 점이 빠른 순으로 정렬했다. 그 후에 그 상황에서 끝나는 점의 좌표(finish_idx)와 사용한 선의 개수를 0으로 초기화했다. 그리고 쭉~~ 봤다. 그러면서 finish_idx보다 일찍 시작하는 선분을 후보에 넣었다. 그리고 그 중에 끝나는 좌표가 제일 큰 선분을 사용하는 게 이득이니까! 제을 큰 끝나는 좌표를 finish_idx에 대입하고, 사용한 선의 개수를 1 더했다. 만약에 finish_idx가 M..

흑흑.. 스터디에서 누군가 비트 마스크 문제를 넣었는데, 전--혀 못 풀겠다. 하긴 나는 지금까지 백준에서 비트 마스크 문제를 단 하나밖에 안 풀었다..;; 그래서 쉬운 문제부터 풀려고 한다! (미완성입니다.ㅠ) 1094. 막대기 https://www.acmicpc.net/problem/1094 이건 비트 연산을 바로 쓴다기 보다는 비트를 이해하고 있나? 그런 문제 같다! 좀 생각해보면 이 숫자에서 2의 제곱수가 몇개 들어있나를 구하는 문제라는 걸 알 수 있다. bin()을 이용해서 풀었다. import sys input = sys.stdin.readline X = int(input()) binary_X = bin(X) print(binary_X.count('1')) 14936. 엘리베이터 장난 1052..

문제로 ~ 스터디에서 다른 분이 0-1 BFS를 설명해주셔서, 그걸 듣고 나서 구현했다~ !! 신기하다 ~!! 나는 큐에서 꺼낸 후에, 더 적은 거울 수로 이미 방문했으면 continue 하고 그 다음에 방문 체크(거울 수 업데이트)하는 부분에서 좀 헤맸다..! import collections import sys input = sys.stdin.readline direct = [(0, 1), (1, 0), (0, -1), (-1, 0)] W, H = map(int, input().rstrip().split()) INF = H * W + 1 arr = list(input().rstrip() for _ in range(H)) visited = [[INF] * W for _ in range(H)] # C 위..

문제 보러 가기! 항상 궁금했던 세그먼트 트리..! solved.ac에 태그를 보면, 다른 건 뭔지는 알겠는데 '세그먼트 트리'만 전혀 몰라서 궁금했다..!! 공부하고 싶어서 스터디 문제에 추가했고, 오늘 공부해봤다 ~~ 단순 배열에서 구간 합을 구하려면 O(N) 걸리는데, 세그먼트 트리를 사용하면 O(logN)으로 시간을 줄여준다 ! (꼭 구간 합을 구할 때만 사용하는 것은 아니고, 구간에서 최댓값이나 최솟값을 찾을 때도 사용한다고 한다.) 내가 세그먼트 트리에 관해서 쓰면 정말 좋겠지만,, 그건 미뤄두고 일단 뭘 참고했는지만 쓰겠다. 먼저 관련된 유튜브를 2개 정도 열심히 봤다! 그리고 아래 쪽 유튜브를 보면서 구현했다. 유튜브에서는 파이썬은 아니고 C?로 쓰신 것 같은데 설명을 듣고 주석을 달면서 ..

문제 보러 가기 풀이 ❄ "엄청난 알고리즘!! 을 알아야 해!!"라기 보다는 조건을 꼼꼼히 반영해서 푸는 문제였다. 나는 미생물 군집의 인덱스, 수, 이동 방향들을 리스트로 저장하고 풀었다. M 시간 동안 아래 과정을 반복했다. 1. 이동 시키기 - 이동 방향에 맞춰서 이동시키기(이동 결과를 리스트에 반영) 2. 약품 부분으로 간 미생물 군집 처리 - 수를 절반으로 - 만약 수가 0이 되면 군집 없애기 - 방향은 반대로 - 처음에는 원래 쓰던 리스트에서 del을 해서, 수가 0이 된 미생물 군집을 처리했다. 그런데 틀렸다.. 잠깐 슬퍼하다가 생각해보니, 원래 리스트에서 del을 하면 리스트 길이가 짧아져서 끝까지 볼 수 없게 된다. 그래서 새로운 리스트(new_microbes)를 만들어서 사용했고, 과정..

문제 풀러 가기! 주어진 예제 1을 풀이하면 아래 그림처럼 된다. ! dp - 모든 위치를 보면서 그 위치일 때 가장 큰 값을 저장했다. 일단 h가 0일 때는 tiles 값 그대로가 그 위치일 때 가장 큰 값이다. y좌표 1 이상이 될 때부터는.. 1) x좌표가 0이거나 w-1이면, y좌표가 현재 지점보다 1 적을 때 바로 위, 한쪽 대각선 중에(그림의 파란색 화살표들 참고) 큰 값을 택한다. 그 값과 tiles 자기 위치 값(그림에서 초록색 값)을 더한다. 2) x좌표가 1~ w-2라면, y좌표가 현재 지점보다 1적을 때 바로 위, 좌측 대각선 위, 우측 대각선 위 중(그림의 노란색 화살표 참고) 큰 값을 택한다. 그 값과 tiles 자기 위치 값(그림에서 초록색 값)을 더한다. y좌표가 h-1까지 오..

문제 풀러 가기 while을 열심히 써서 풀었다 ! while 안에 while을 써서 문제 푼 것은 오랜만인 것 같다~ 1.봐야할 챕터가 없을 때까지 쭉~ 본다. 2.30분 동안 볼 수 있는 챕터를 본다! 1) 남은 시간 미만으로 그 챕터를 다 볼 수 있는 경우 => 정답을 1 더하고, 남은 시간을 업데이트한다.(남은 시간 - 그 챕터 볼 때 걸리는 시간) 챕터 수도 1 늘려주고! 2) 남은 시간으로 그 챕터 절반 이상을 볼 수 있는데, 그렇다고 시간이 남지는 않는 경우 => 정답을 1 더하고, 봐야 할 챕터 수도 1 늘린다. 그리고 이제 다시 '2.30분 동안 볼 수 있는 챕터를 본다!'를 시작해야 하니까 break. 3) 남은 시간으로 그 챕터 절반 이상 볼 수 없는 경우. => 정답은..

문제로 가기 정렬하고 쭉 ~ 한번 보면 되는 스위핑 문제!! 정렬한 후에 (출발지가 앞쪽인 순서, 출발지가 같으면 도착지가 앞쪽일 수록 앞에) 쭉~ 보면서 두 노선씩 비교한다. a_route는 처음 노선으로 초기화하고 시작하고, b_route는 그 다음 노선부터 끝까지 쭉 본다. 만약 a, b 노선이 겹친다면 합쳐서 새로운 노선으로 만든다! 이때 요금은 더 낮은 쪽을 따른다. 출발점이 더 나중에어도, 도착점이 더 이른 노선이 있을 수도 있다. 노란 색 노선, 빨간 색 노선을 비교할 때는.. 일단 겹치니까 a_route를 업데이트하는데, 'a_route = (a_route[0], max(a_route[1], b_route[1]), min(a_route[2], b_route[2]))'에서 'max(a_rou..

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