https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 효율성 테스트가 존재하고, 투포인트로 풀어야 시간초과가 발생하지 않는다. 우선, 투포인트를 사용하지 않아 틀린 풀이를 확인해보자. 오답 풀이(시간 초과) #include #include #include #include #include using namespace std; map ma; pair getLen(){ int min=987654321,max=-987654321; for(aut..
[ n개의 숫자를 전부 사용해서 만들 수 있는 모든 순열의 갯수] ex) 1,2,2 가 input으로 들어오면 1,2,2 2,1,2 2,2,1 3가지가 나온다. 여기서 중요한 점은 "중복된 순열은 제거" 된다는 점이다. 1,2( 1th ) , 2( 2th ) 1, 2( 2th ) , 2( 1th ) 이런식으로 사실 상 같은 순열이 2번 추출되면 안된다는 뜻이다. 이때 사용하는게 바로 C++ 헤더 중 #include 으로 사용할 수 있는 next_permutation이다. 우리가 원하는 결과 값은 1,2,2 2,1,2 2,2,1 이렇게 3개인데, next_permuation( vec.begin(),vec.end() ) 이 메소드가 하는 역할은 vec를 중복되지 않은 다음 순열 값으로 변경해주는 것이다. 처..
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/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 이번엔 오답+ 정답 코드를 포스팅하는데, 우선 정답 먼저 보겠습니다. 택시합승이란 문제는 결국 어느지점까지 합승할지? 를 해결하면 풀 수 있습니다. 따라서 플로이드 와샬 알고리즘을 통하여 모든 노드들 간의 최단거리를 찾고, 어떤 합승지점에서 최소 값이 나오는지 linear 탐색을 통해 찾으면 해결됩니다. 아래는 해결 코드입니다. #include #include #in..
dp는 상황을 나누고, 그 간의 관계를 파악하여 점화식 혹은 a=b와 같은 고정된 수식으로 표현하여 문제를 효율적으로 해결하는 방식이다. 예를 들어 동전이 연속으로 앞면이 나올 확률을 구한다고 생각해보자. 모든 상황은 결국 나누면 앞면, 뒷면 으로 나뉜다. 이를 수식으로 표현해보자. n-1 째까지 앞면 나올 확률 * 앞면 나올 확률 = n 째까지 앞면 나올 확률 즉 f(n-1)* 1/2 = f(n) 이라는 점화식을 구할 수 있다. dp는 이런 특정 행동 (동전을 던짐) 에 따른 관계의 변화를 수식으로 표현해서 구할 수 있다. (특정행동 n-1번 = 특정행동 n번 이런식으로 생각하면 쉽다.) 전에 knapsack 알고리즘에 대해서도 정리했었는데, dp라고 생각하고 식을 구해도 해결할 수 있다. 추가로 in..
이 문제가 삼성 코테에 기출 되어서 풀어봤는데, 여러가지 알고리즘이 한 문제에 누적 되어 있어, 풀어보면 좋을 것 같아 자잘한 설명과 함께 코드를 공유하려합니다! 코드에 대한 설명은 주석으로 상세하게 적어놨습니다~ 문제를 처음보면, 딱 "그룹" 이라는 단어가 떠오르면서 자연스럽게 mst(최소 스패닝 트리) 에 관한 문제인 것을 캐치하고 풀어 나갔다. MST에 대해 잘 모른다면, 아래의 글을 참고하자. https://codenme.tistory.com/manage/posts/ Tistory 좀 아는 블로거들의 유용한 이야기 www.tistory.com 문제는 크게 3파트로 나눌 수 있는데 1) 각 섬에 번호를 붙여 저장하기 (섬간의 구분을 위해) 이건 bfs를 통해 구현했다.. 2)섬간의 거리를 구한다. ..
많은 문제들이 최소 비용, 최단거리 등에 집착한다. 하지만 막상 수많은 최단거리, 최소 비용에 대한 문제들을 보면 어떤 알고리즘을 써서 풀어야하지...? 하는 생각이 들고 생각나는대로 문제를 풀면 시간초과 혹은 오답이 나오면 멘붕이 오곤한다.. 이번 글에선 "최단 거리" 에 대해서와, 언제, 어떤걸 써야하는지에 대해 간략하게 정리해 보겠다. 디테일한 설명전 간단한 요약을 먼저 하자면 bfs: 간선에 가중치가 없다(단위길이) , 즉 비용이 아닌 거치는 횟수가 요구될 때. 다익스트라: 특정 시작점 모든 지점 간의 최단거리 플로이드와샬: 모든 시작점 모든 지점 간의 최단거리 벨만포드: 최단거리에서 음수 간선, 등으로 인하여 계속해서 최단거리를 줄여나가는지 "감지" 해야하는 경우 정도로 요약할 수있다. 1)가중..
시작하기에 앞서, 기초적인 구현 방식, 정보들은 최대한 글에서 다루지 않을 예정이고, 혼동되거나 헷갈리는 부분들, 놓치고 넘어가기 쉬운부분들만 설명할 것임을 유의해주세요..! 그래프 탐색이 필요한 이유는 바로 선형적인 탐색 (for문을 통한 i:1~n) 으로 탐색하지 못하는 문제들을 탐색하기 위해서이다. 예를들어 그래프 탐색이 필요한 문제중 하나인 백준 2178 "미로 탐색" 을 보자. 우리는 점차 증가하는 인덱스를 통한 탐색이 아닌, 갈 수 있는 위치로 향하는 탐색을 해야하는데, 이는 for문과 적합하지 않다. 그렇기에 우린 이러한 갈 수 있는 방향을 "그래프" 로 만들어나가며 탐색을 해나가는 것이다. 그래프의 대략적인 정의는 정점, 그리고 간선으로 이루어진 대충 아래 그림 같은 친구들을 말한다. 그래..
