날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/43238.py at main · Junroot/Algorithm 풀이 기다리는 사람의 수가 최대 1000000000명 이었기 때문에 O(1) 또는 O(logn)의 형태가 될 것이라고 추측했다. O(1)의 방식은 아이디어가 떠오르지 않아 O(logn) 방식인 이분 탐색을 사용하기로 했다. 소요되는 시간의 범위는 [0, n * (가장 오래걸리는 심사원의 시간)]으로 지정했다. 최소값을 찾아야되기 때문에 해당 인원을 처리할 수 있을 때는 answer에 기억을 해두면서 범위를 점차 줄이는 방법으로 해결했다.
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/43236.py at main · Junroot/Algorithm 풀이 처음에 접근한 방법은 모든 경우의 수를 구하는 것이다. 하지만 이 방법은 바위가 최대 50000개이고, 제거할 바위의 수가 1개에서 바위의 수만큼이므로, ${50000}C{25000}$ 도 계산해야되기 때문에 이 방식은 불가능하다. 두 번째로 생각한 방법은 가장 짧은 거리를 우선적으로 지우면서 탐욕적으로 계산하는 방법이다. 하지만 이 방법에는 문제가 있다. 거리 합치기 선택 가장 짧은 거리를 선택해서 다른 거리와 합칠 때, 왼쪽과 오른쪽 중에 어디에 합쳐야 될 지 알 수 없다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/43165.py at main · Junroot/Algorithm 풀이 리스트의 앞부터 순서대로 덧셈과 뺼셈을 적용하면서 리스트 끝까지 적용했을 때 등호가 성립하면 1을 리턴하고 성립하지 않으면 0을 리턴하는 재귀함수를 구현했다. 이러면 현재 선택한 숫자가 덧셈인 경우와 뺄셈인 경우를 나누어 결과값을 더하면된다. (n개의 리스트의 결과값) = (첫 번째 요소가 덧셈일 때 n-1개의 결과값) + (첫 번째 요소가 뺄셈일 때 n-1개의 결과값)
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/43164.py at main · Junroot/Algorithm 풀이 현재 위치에서 탈 수 있는 티켓을 계속 고르면서, 모든 티켓을 사용할 수 있는 경우를 찾으면 반환하는 함수를 만들었다. dfs이기 때문에 재귀함수를 이용했고, 현재 반환한 값이 성공적으로 찾았는지 판별하기위해 (성공여부, 경로) 튜플 형태로 반환했다. 그리고 알파벳 순서가 앞서는 경로를 우선으로 해야됐기때문에 탐색 시작전에 tickets를 한 번 정렬시켰다. 다른 사람 풀이를 봤는데, python의 경우 리턴값을 따로 쓰지 않으면 None이 리턴되는 것을 이용할 수 있었다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/43163.py at main · Junroot/Algorithm 풀이 두 단어에 글자 차이 개수 구하기 차이가 1인 단어들끼리 딕셔너리로 표현하기 bfs를 이용하여 최소 변환 단계 구하기 이렇게 3가지 문제로 나뉘었다. 1, 2번은 구현 문제이므로 따로 풀이를 적지는 않는다. bfs는 너비 우선 탐색이기 때문에 출발지로부터 거리가 짧은 노드를 우선적으로 탐색한다는 것을 인지한다면 3단계를 캐치할 수 있게된다. 큐에 단어를 넣을 때 현재까지 변환한 횟수도 함께 저장하면 쉽게 최소 변환 단계를 구할 수 있다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/43162.py at main · Junroot/Algorithm 풀이 컴퓨터 리스트를 순서대로 확인하면서 방문한 컴퓨터들을 체크하는 리스트를 별도로 만들었다. 이 때, 방문하지 않은 컴퓨터가 있다면 그 컴퓨터와 연결된 모든 컴퓨터를 먼저 방문처리하게되면 네트워크의 개수를 알수 있게된다. 연결된 컴퓨터들을 방문처리할 때는 bfs, dfs 상관이 없기때문에 조금이나마 빠른 bfs를 사용했다.
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/43105.py at main · Junroot/Algorithm 풀이 각 위치별로 이동할 때 나올 수 잇는 최대값을 저장하는 삼각형을 만들었다. 이 삼각형을 만들기위한 점화식은 간단했다. $a_{x,y}$를 y번 째줄의 x번 째 숫자로 정의를 하면 다음과 같은 점화식이 나온다. $$ a_{x,y} = max(a_{x-1, y-1}, a_{x, y-1}) $$ 삼각형이 완성이 되면 가장 아래줄의 수 중에서 가장 큰 값을 찾으면된다.
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42898.py at main · Junroot/Algorithm 풀이 일단 해당 위치가 물에 잠긴 지역인지 매번 루프를 돌며 확인하는 것은 비효율 적이라고 생각해서 2차배열로 미니맵을 만들었다. 물에 잠긴 지역은 -1 아닌 곳은 0으로 저장을 했다. 그 후, 경우의 수를 계산했다. (x, y)위치는 (x - 1, y)의 경우의 수 + (x, y - 1)의 경우의 수가 될 것이다. (1, 1)의 위치는 경우의 수가 1이고, 점차적으로 이동할 수 있는 경우의 수를 계산하면 됐다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42897.py at main · Junroot/Algorithm 풀이 원이 아니라 일직선일 경우는 DP로 쉽게 풀 수 있다는 사실을 알고 있었다. 그럼 이 문제를 일직선으로 변형할 수 있다면 쉽게 해결이 가능하다. 이를 하는 방법은 특정 한 집을 기준으로 털었을 경우아 털지 않은 경우로 나누어서 DP문제를 풀면된다. 털었을 경우에는 그 집의 좌우를 제외하고 DP문제로 풀면되고, 털지 않은경우는 이웃한 집을 포함해서 풀면된다. 그렇게 나온 결과 중 더 큰 값이 문제의 정답이 된다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42895.py at main · Junroot/Algorithm 풀이 DP로 문제를 해결할 때, 어떤 값을 기준으로 점화식을 만들지 정하는 것에 어려움이 있었다. 고민 끝에 내린 결론은 $a_n$을 (N을 n번 사용해서 만들 수 있는 수의 집합)이라고 정의했다. 그렇데되면 점화식은 다음과 같다. 여기서 *연산은 (좌변의 원소와 우변의 원소가 사칙연산을 해서 나올 수 있는 값들의 집합)이다. 사칙 연산은 어차피 좌변과 우변의 연산으로 이루어지기 때문에 점화식은 성립 가능하다. 이 때, 한 가지 예외가 있으니 주의해야된다....
날짜: 2022년 7월 5일 오후 11:26 오답: o 코드 Algorithm/42894.py at main · Junroot/Algorithm 풀이 단순 구현 문제다. 쌓을 수 있는 모든 영억에 검은 블록을 쌓아두고 지워지는 블록이 있을 때까지 계속 지우면서 반복한다. 구현하면서 실수가 많이 발생하므로 구현연습이 필요할 때, 다시 풀어보는 것을 권장한다.
날짜: 2022년 6월 29일 오후 1:44 코드 Algorithm/42890.py at main · Junroot/Algorithm 풀이 가능한 모든 컬럼의 조합을 구한 뒤, 유일성을 체크하고, 최소성을 체크하면된다. 이 때 컬럼의 조합은 개수가 적은 조합부터 처리한다. 유일성: 해당 컬럼 조합에 중복이 없는지 확인하고, 없다면 유일하다. 최소성: 이미 존재하는 후보키의 조합을 부분 집합으로 가지는 경우가 없다면 최소성을 만족한다.
날짜: 2022년 6월 29일 오후 1:41 코드 Algorithm/42889.py at main · Junroot/Algorithm 풀이 각 스테이지 별 유저 수를 세고나서, 누적합을 통해 각 스테이지를 지나간 유저들을 구하면 실패율을 구할 수 있다.
날짜: 2022년 6월 29일 오후 1:40 코드 Algorithm/42888.py at main · Junroot/Algorithm 풀이 기록을 두 번읽어서 해결할 수 있다. 첫번째로 읽을 때는 각 유저의 최종 닉네임을 찾고, 두번째에서는 채팅방에 출력될 내용을 처리하면된다.
날짜: 2022년 1월 31일 오후 5:51 코드 https://github.com/Junroot/Algorithm/blob/main/programmers/42885.py 풀이 가장 무거운 사람부터 처리한다는 생각으로 접근했다. 무인도에 남은 사람 중 가장 무거운 사람과 가장 가벼운 사람이 같이 배에 탈 수 있는지를 반복해서 비교해봤다. 왜 가장 가벼운 사람과 타는게 문제가 없는지 의문이 생길 수 있다. 예를들어 A>B>C>D 순으로 무겁다고 가정했을 때, (A, C)가 함께 탈 수 있는데 (A, D)가 함께 타면 문제가 생기지 않냐고 생각할 수도 있다. (B, D)는 함께 탈 수 있는데 (B, C)는 함께 못 타는경우가 있을 수 있기 때문이다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42884.py at main · Junroot/Algorithm 풀이 도착 지점이 빠른 구간 순으로 접근하면 풀이가 쉬워진다. 자신보다 먼저 끝나는 구간이 존재하지 않기 때문에 해당 구간의 마지막 위치에 카메라를 두고, 해당 위치를 지나는 모든 구간은 새로 카메라를 둘 필요가 없어진다. 따라서 이 방법이 최소의 카메라 수를 가지게 된다는 것을 보장할 수 있다.
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42883.py at main · Junroot/Algorithm 풀이 가장 앞 자리수가 큰 것이 중요하다는 점을 파악하면 해결하기 쉽다. k개를 지운다는 뜻은 (number의 길이) - k 개의 숫자를 선택해서 수를 만든다고 접근하는 것이 나에게는 더 쉬웠다. n개의 숫자 중 k개의 숫자를 선택해야될 때, 제일 앞 자리 숫자는 [0, n - k) 범위의 인덱스 중에 선택해야된다. 따라서 이 범위 중에 가장 큰 수를 선택하면 된다. 사실, 풀이법은 금방 생각했는데 처음에 재귀 함수를 이용하여 구현을 했다가 계속해서 시간 초과가 발생했다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42862.py at main · Junroot/Algorithm 풀이 가능하면 자신의 앞 사람의 옷을 빌리도록 시도하게 구현했다. 이렇게하면, 서로 빌리려는 사람이 겹치는 경우가 사라진다. 주의해야될 점은 lost와 reserve의 정보가 번호 순서대로 들어오지 않을 수 있기 때문에 정렬을 해야된다.
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42861.py at main · Junroot/Algorithm 풀이 최소의 비용으로 연결하기 위해서는 n - 1개의 다리만 있으면 된다는 점을 파악해야된다. 나는 가장 짧은 간선부터 선택해보면서 사이클이 발생하지 않도록만 하면 최소 비용으로 연결이 될 것이라고 생각했다. 이를 위해서 최소 값을 찾아서 꺼내기 쉬운 우선순위 큐를 사용해봤다. 사이클이 발생하는지 확인하는 방법에 대해서 고민을 좀 했었다. 내가 사용한 방법은 서로 연결되어 있는 섬들의 집합을 ‘그룹’이라고 정의하고, 그 그룹을 대표하는 섬 하나를 ‘부모(parent)‘라고 정의했다....
날짜: 2022년 1월 31일 오후 5:50 코드 Algorithm/42860.py at main · Junroot/Algorithm 풀이 문제를 수평 이동과 수직 이동으로 크게 나눌 수 있다. 수직 이동 수직 이동에 대한 처리는 그렇게 어렵지 않다. 알파벳이 26개인것만 알고 있다면. 수평 이동 수평 이동에 대한 처리에서 놓쳐서는 안되는 경우가 있다. 오른쪽으로 이동했다가 왼쪽으로 쭉 이동하는 경우가 더 짧을 수도 있다 라는 점이다. 나는 이를 해결하기 위해 2가지 문제로 나눠서 풀었다. 그림으로 표현하면 다음과 같다. 모든 연속된 ‘A’ 구간 찾기 이 부분은 리스트를 처음부터 끝까지 한 번만 스캔해서 찾아냈다....