문제 https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 전형적인 BFS 문제이다. BFS 문제에서의 난이도는 방문배열을 3차원배열로 해야 하는지, 2차원 배열로 해야 하는지에 따라 나뉜다고 생각한다. 해당 문제는 좌표로 들어왔던 도로의 방향을 기억해줘야 한다. 그래야 코너를 만들 때 계산을 해 줄 수 있기 때문이다. 그리고 도착지점에 도착할 경우 그때 경주로 건설에 사용한 비용의 최소값을 반환해야 한다. 따라서 나는 우선순위큐를 이용해..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 초기에는 N*N으로 탐색을 해서 요구사항에 맞는 짧은 구간, 길이가 같으면 시작 구간이 더 작은 구간을 함수를 통해서 반환했다. 정확성 테스트는 쉽게 통과했지만, 효율성 테스트에서 시간초과를 만날 수 있었다. 어쩐지 LV3 치고 문제가 너무 쉬웠는데, 아마 배열을 탐색하는 과정에서 N*N 알고리즘을 사용해서 그런 것 같다. 1차원이고, 완전 탐색을 피하기 위한 알고리즘으로 투포인터..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 개인적으로 풀었던 LV3 문제보다 어려웠다. 정확성과 효율성을 모두 검사하는 문제인데, 효율성을 통과하는 과정이 정말 어려웠다. 실제로 효율성을 통과하는 방법을 몰라서 구글링을 했다. 아마도 쿼리에 해당되는 사람을 찾는 과정에서 배열의 전체를 탐색하기에 시간이 초과된다고 예상은 했지만, 그 해결방안으로 이분탐색을 사용할 줄은 상상도 못 했다.. 정말 대단한 사람들이다. 그 외적으로..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 전형적인 백트래킹 문제이다. 우선 응모자아이디를 이용해서 조합을 만들고, 만들어진 조합의 크기가 불량 사용자 아이디 목록의 크기와 동일해질 경우 매핑을 시작한다. 매핑은 다음과 같은 과정으로 이루어진다. 후보 아이디 목록과 불량 사용자 아이디 목록은 1:1로 매칭한다. 만약 길이가 다를 경우 매핑은 실패한다. *을 제외한 글자가 다를 경우 매핑은 실패한다. 매핑이 성공했다면, 결과..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 전형적인 백트래킹 문제이다. 2차원 배열을 사용해서 풀기보다는 조금 특별하게 풀고 싶었다. 따라서 Queen이라는 데이터클래스를 가지는 배열을 통해서 각자의 위치에 따라 공격할 수 있는 여부를 따지고 싶었다. 그래서 n만큼의 depth를 탐색하는 재귀함수를 작성해서, Queen의 column위치를 계속해서 조정했다. 배열에 Queen을 넣고, 해당 퀸의 추가가 적절한 추가인지 검사..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=kotlin 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제가 굉장히 길고 복잡해 보이지만 문제에서 원하는 것은 간단합니다. 이모티콘에 대한 할인율을 10,20,30,40중 적절하게 적용해서 가장 많은 이모티콘 서비스 구독자를 확보. 구독자가 동일하다면 가장 많은 판매액을 확보 따라서 우리는 이모티콘에 대해서 확률을 모든 경우의 수에 대해 적용해 보고 위의 조건들을 검사해 주면 됩니다. 이모티콘에 대한 모..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=kotlin 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 굉장히 고생했던 문제이다.. 프로그래머스 특성상 디버깅이 쉽지가 않아, 재귀 함수를 사용하는데 항상 어려움을 겪고 있다. 출력을 통해서 디버깅을 하려고 해도, 재귀 함수의 깊이가 깊다면 출력내용 초과로 쉽지도 않다. 해당 문제를 푸는데 재귀를 어떤식으로 호출하는지가 중요하다. 재귀함수는 다음과 같은 흐름이다. 재귀함수는 깊이와 남은화살의 수를 가진다. ..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 보자마자 떠올랐던 생각은 다익스트라..? 를 사용하는 것이라고 생각했다. S에서 출발해서 A와 B가 가장 적게 낼 수 있는 택시비의 요금을 구해야 한다. 하지만 까다로운 점은 A와 B가 따로따로 타는 경우고 고려해서 정말 어려웠던 문제였던 거 같다. 우선 나는 다익스트라 알고리즘을 통해서 정점마다 최소 거리를 구하려고 했다. 우선 A와 B가 따로따로 택시를 타는 경우는 S에..
문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 문제 풀이 앞에서 풀었던 1197 최소 스패닝 트리에서 입력형식만 바뀐 거지 문제 풀이는 똑같다. 앞선 문제에서 주어졌던 입력 형식인 from->to->value가 배열 형식으로 i -> j -> input값으로 바뀐것이다. 따라서 해당 입력형식에 따라 노드를 생성하고, 크루스칼 알고리즘을 사용하면 쉽게 풀 수 있다. 전체 코드 package MST.`16398_행성_연결`.LJH impor..
