https://school.programmers.co.kr/learn/courses/30/lessons/81304 위 문제에 대한 해설입니다. 우선 문제를 풀기 전 내가 가장 고생했던 부분은 trap 노드의 개수가 10개가 최대라는 점이다. 처음에 trap 노드 개수의 제한이 없고, 즉 input n의 개수인 3000개까지 trap이 생길 수 있다고 생각하고 고생을 좀했다. 만약 trap의 개수가 10개라는 정보를 안다면, "trap 노드" 라고하는 매우 복잡한 노드를 따로 처리하는 방식을 어렵지 않게 생각할 수 있을 것이다. 하지만 그럼에도 이 문제가 어려웠던 점은, 기존에 우리가 알던 "최단 거리" 알고리즘의 전제를 바꾸어 놓는다는 것 이다. 이 문제의 경우, 특정 시작점에서 도착점으로 향하는 최단거..
https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 해설입니다. 우선 문제의 효율성 테스트를 통과하려면 꽤 큰 input에도 대처가 가능해야하는데, 이 때문에 문제 그대로 단순히 삽입, 삭제를 그때 그때 수행하는 것 만으론 시간복잡도가 오버된다. 따라서 삽입, 삭제를 실제로 행하지 않거나, 혹은 실제로 삽입, 삭제를 진행하되, 그 효율을 좋게 만들어야만 해결할 수 있다. 내 경우는 linked list 자료구조를 통해 해결했다. ..
https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 우선 문제를 보면 무식한 방식으로 풀어도 될거같다는 느낌이 옵니다. 제한사항을 보면 문자열 길이가 1000이하로 주어졌는데, 반복가능한 문자열 단위는 최대 500입니다. 그 이유는 전체 문자열 길이의 절반을 넘어가면 반복되는 문자열을 통한 압축이 불가능해지기 때문입니다 ex: aaaabb >> 길이 단위를 4로 해도 2aaaa 이런식으로 압축이 불가능합니다. 길이가 ..
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 이번엔 오답+ 정답 코드를 포스팅하는데, 우선 정답 먼저 보겠습니다. 택시합승이란 문제는 결국 어느지점까지 합승할지? 를 해결하면 풀 수 있습니다. 따라서 플로이드 와샬 알고리즘을 통하여 모든 노드들 간의 최단거리를 찾고, 어떤 합승지점에서 최소 값이 나오는지 linear 탐색을 통해 찾으면 해결됩니다. 아래는 해결 코드입니다. #include #include #in..
https://school.programmers.co.kr/learn/courses/30/lessons/72412 위의 문제에 대한 해설입니다. input으로 들어오는 2개의 vector 에서 각 벡터 안 1개의 string들은 총 5가지 유효한 string 정보를 가지고 있다. parser를 통해 유효한 5개의 string의 string을 추출한 뒤, 마지막에 위치한 점수에 대한 부분은 stoi() 함수를 통해 숫자로 바꾼다. map 자료구조를 통해 앞선 4개의 string들을 하나로 묶어 key 값으로써 사용하고, stoi()를 통해 정수형으로 바꾼 점수 정보를 value로써 추가한다. 이때 고려할 사항은 query에서는 '-' 라는 문자열이 특수성을 가진다는 것이다. '-'는 어떤 것이 와도 상관없..
