목록SWEA (3)
체뚱로그
풀이 시간: 1h48m46s 시간 복잡도: O(N^2) 공간 복잡도: O(N^2) 참고 자료: https://coooding.tistory.com/32 문제 2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다. 전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다. 그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다. 전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다. 공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다. 도로가 파여진 깊이에 비례해서 복구 시간은 증가한다. 출발지에서 도착지까지 가는 경로 중에 복구 시간이 ..
풀이 시간: 1h06m20s 시간 복잡도: O(nC2^M) -> n: 문자열 길이, M: 교환 횟수 공간 복잡도: O(1) -> 상수 값에 의존 참고 자료: https://eunchanee.tistory.com/149 문제 퀴즈 대회에 참가해서 우승을 하게 되면 보너스 상금을 획득할 수 있는 기회를 부여받는다. 우승자는 주어진 숫자판들 중에 두 개를 선택에서 정해진 횟수만큼 서로의 자리를 위치를 교환할 수 있다. 예를 들어, 다음 그림과 3, 2, 8, 8, 8 의 5개의 숫자판들이 주어지고 교환 횟수는 2회라고 하자. 교환전> 처음에는 첫번째 숫자판의 3과 네 번째 숫자판의 8을 교환해서 8, 2, 8, 3, 8이 되었다. 다음으로, 두 번째 숫자판 2와 마지막에 있는 8을 교환해서 8, 8, 8, 3..
풀이 시간: 1시간 - 처음에 bit 값을 그대로 받으려다가 string 라이브러리로 바꾸는 과정에서 시간 소요 시간 복잡도: O(T*N) - N은 str 문자열의 길이 공간 복잡도: O(1) - 전부 상수 값이므로 문제 원재가 컴퓨터를 만지다가 실수를 저지르고 말았다. 메모리가 초기화된 것이다. 다행히 원래 메모리가 무슨 값이었는지 알고 있었던 원재는 바로 원래 값으로 되돌리려고 했으나 메모리 값을 바꿀 때 또 문제가 생겼다. 메모리 bit중 하나를 골라 0인지 1인지 결정하면 해당 값이 메모리의 끝까지 덮어씌우는 것이다. 예를 들어 지금 메모리 값이 0100이고, 3번째 bit를 골라 1로 설정하면 0111이 된다. 원래 상태가 주어질 때 초기화 상태 (모든 bit가 0) 에서 원래 상태로 돌아가는데..