기계는 정직하다

거리를 기록해놓자 접근 node와 link의 수가 꽤 많다. 그래서 그런가 그냥 BFS 적용하면 시간초과가 발생한다. 나처럼 쉬운문제부터 올라온 사람은 시간초과 문제를 겪을 것이다. 이 경우 기존에 방문했던 node들의 거리를 기록해놓고 다른 경로를 탐색할 때 활용해야 한다. 이러한 접근 방법은 동적계획법과 같다. A->B->C의 경로는 A->B와 B->C의 경로라는 부분문제로 나눌 수 있고 B까지의 경로를 사전에 계산해놓았다면 B->C만 계산하면 된다. 의사코드 주어진 배열을 인접리스트로 바꾼다. 노드의 수를 길이로 하는 costs배열을 만들고 모든 원소를 -1로 초기화한다. 출발점이 될 costs[destination]에 0을 대입한다. destination에서 출발해 인접한 노드의 거리를 +1씩 추..

알면 풀고 모르면 못 풂 조건파악 부분수열의 합에 추가로 펄스라는 조건이 추가되었다. 다행스럽게도 펄스는 1과-1뿐이며 어떤 수가 1 또는 -1로 정해지면 이웃한 원소의 펄스는 서로 반대의 펄스로 정해지게 된다. 즉 연속 부분수열의 길이와 별개로 펄스는 두 가지의 경우만 있다. 홀수 인덱스의 원소가 1이고 짝수 인덱스의 원소가 -1이거나 그 반대의 경우이다. 접근 해당 문제는 두 개의 부분 문제로 나눌 수 있다. 1. 홀수 인덱스 혹은 짝수 인덱스의 원소에 -1을 곱한 배열을 구하라 2. 부분수열의 합이 최대가 될 때 그 값을 구하라 1번의 경우 입력으로 주어진 배열을 통해 두 개의 배열을 만들어낼 수 있다. 그리고 나면 부분수열의 합이 최대가 될 때 그 값을 구하면 된다. 연속 부분 수열의 합의 최대값..

Programmers Lv.3 파괴되지 않은 건물 파이썬 문제풀이 조건파악 board의 크기 최대 (1,000 x 1,000) skill의 길이 최대 (250,000) 얼핏 보면 상당히 쉬운 문제이지만 효율성 테스트를 통과하기 어렵다. 단순한 알고리즘을 이용할 경우 최악의 경우 board에 있는 모든 원소인 1,000,000개에 대해 250,000번 연산을 수행해야 한다. 따라서 N은 최대 250,000,000,000이므로 O(N*M)의 방법으로는 도저히 풀 수 없게 된다. 접근 스킬들에 따른 영향을 사전에 모두 계산해놓은 뒤, board에 한 번에 합산한다. board의 원소 수를 N, skill의 길이를 M이라 하자. 이 경우 수행되는 연산의 수는 대략 k*M + N이다.(k는 임의의 가중치) 즉 시..

Programmers Lv.2 '두 원 사이의 정수 쌍' 파이썬 조건파악 1. 닫힌구간 2. N이 최대 1,000,000이고 내부적으로 sqrt연산이 필요할 것 같다. 따라서 시간복잡도는 최대 O(NlogN)정도 되겠다. 접근 사분면으로 나누어서 하나의 사분면만 생각하자. x또는 y축 하나를 정해서 1부터 r2까지 축이동하며 스캔하면 편하겠다. 피타고라스 정리를 활용 그러고 나서 축 위의 두 원 사이에 위치한 정수의 개수를 세자. 축의 x또는 y좌표가 r1을 넘을 경우 대응되는 치역이 무리수이기 때문에 유효성 검사 장치를 마련하자. 의사코드 i를 1부터 r2까지 1씩 증가시키며 반복 sqrt(r1^2 - i^2)에서 sqrt(r2^2-i^2)까지 정수의 개수를 셈 i가 r1보다 커서 r1^2 - i^2가..

Programmers Lv.2 '무인도 여행' 파이썬 영역 탐색 -> BFS 조건파악 1. 영역 탐색 2. 탐색하면서 수를 누산해야 함 접근 recursive BFS를 이용. 의사코드 bfs()를 선언 bfs()는 재귀적으로 호출되며, 특정 지점에서 네 방향을 탐색하고 방문처리 유효한 탐색 방향에 대해 다시 bfs() 수행 후 결과들을 합산 bfs를 시작한 지점에서의 결과와 다시 합산하여 return 방문하지 않은 지점을 우선으로 전부 탐색하여 결과를 리스트에 저장 리스트를 정렬. 리스트가 비어있으면 [-1] 구현 import sys sys.setrecursionlimit(10**6) def solution(maps): answer = [] rows = len(maps) cols = len(maps[0]..

Programmers 파이썬 당구 연습 그냥 계산하는 게 빠른 문제 조건파악 1. 공은 절대 겹치지 않는다. 2. 모서리에 부딪히는 경로는 절대 최단 거리가 될 수 없다. (계산해보면 앎) 3. 공이 수직 또는 수평으로 나란히 있는 경우 원쿠션을 성공할 수 없는 경우의 수가 생긴다. 접근 상하좌우로 경우의 수는 네 개. 그냥 네 방향 다 계산해서 제일 작은 거 찾으면 된다. 거리를 계산하기 전에 좌표만 가지고 어떤 벽에 부딪힐 건지 선택할 수 있으면 좋겠는데, 방법을 모르겠다. 그걸 모르고 단순 계산으로 풀어도 시간초과가 나지 않으니 Lv.2이겠지. 의사코드 1. balls배열에 대해 반복 2. 두 공이 나란한지 확인 3. 원쿠션이 발생하도록 네 방향(또는 세 방향)에 부딪혀서 공을 맞추는 거리를 계산 ..

Programmers Lv.2 연속된 부분 수열의 합 / 파이썬 접근 두 개의 포인터를 놓고 부분 수열의 합을 반복해서 비교하며 위치를 옮기거나 확장한다. 가장 짧은 길이의 부분 수열을 찾기 위해, 더 큰 수가 위치한 뒤쪽 인덱스부터 탐색한다. sequence의 길이가 길기 때문에 sum()함수를 반복해서 사용하면 시간초과가 발생할 수 있으므로 부분합 변수를 만들어 갱신하도록 한다. 의사코드 i와 j를 마지막 인덱스 번호로 초기화 sub_total을 마지막 원소의 값으로 초기화 sub_total이 k와 같아질 때까지 i, j 조정하면서 sub_total을 갱신 sub_total이 k와 같을 때 더 앞쪽에 있는 동일한 부분 수열을 가리키도록 i와 j를 감소 코드 def solution(sequence, k..

maven 프로젝트가 빌드되어 실행될 java 런타임 버전을 직접 설정하고 싶다면 다음과 같은 방법을 이용하면 된다. pom.xml 다음 태그 추가하기 .. .. {version} {version} .. .. {version} 대신 원하는 버전을 기입하면 된다. 아래는 jdk 1.8을 사용하고자 하는 상황의 예시이다. 1.8 1.8 VS Code에서 java runtime path가 설정이 안 되거나 혹은 프로젝트가 동작할 java 런타임 환경과 현재 개발환경이 다르다면 위 방법을 통해 해결할 수 있다.

Programmers Lv.2 파이썬 '과제 진행하기' 풀이 및 코드그냥 제때제때 하라. 조건파악중요한 조건들 1. plans의 길이는 1,000이며 O(N^2)으로 풀 수 있다. 2. 시간이 hh:mm과 같은 str으로 되어있다. 3. 시작시각은 모두 다르다. 따라서 정렬할 수 있다. 4. 나중에 미뤄진 것부터 다시 처리한다. 따라서 미뤄지면 처리 순서가 뒤집힌다. 5. 24시가 경과됨에 상관 없이 모든 과제는 끝낸다. - 문제에 명시되지 않음 접근마치 pipeline을 설계하는 듯한 문제이다. plans는 FIFO 즉 queue, 중간에 멈춘 과제들은 미뤄놨다가 LIFO(FILO) 즉 stack처럼 처리하면 되겠다. 두 개의 자료를 만들어 놓고 다음으로 처리할 과제는 queue이냐 stack이냐를 정..

Programmers Lv.2 파이썬 '광물 캐기' 풀이 및 코드마인크래프트..? 게임 설정 상 광물로 곡괭이를 만들 수 있으며, 더 좋은 재료로 만들어진 곡괭이일 수록 광물을 더 쉽게 채굴할 수 있다. 조건파악이 문제는 조건이 매우 중요하다. 1. 광물은 무조건 5개씩 연속으로 캔다. 2. 5개를 채굴할 때마다 곡괭이를 고른다. 어떤 곡괭이를 먼저 쓸 것인가? 순서대로 채굴해야 하기 때문에 minerals를 재정렬하는 것은 불가능하다. 하지만 5개 채굴시마다 곡괭이를 바꾸기 때문에 크기가 5인 청크로 묶는다면 서로 다른 청크는 서로 독립적이기 때문에 정렬을 수행해도 결과에 영향을 주지 않는다! picks는 원소가 3개 뿐이며, dia,iron,stone은 각각 해당 재료로 만들어진 곡괭이의 수를 의미한..