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..
https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위의 문제에 대한 풀이입니다. 우선 처음 단순히 생각하면 1명 처리 -> 처리 시간 입력, ...... n명 처리 -> 처리 시간 입력으로 입국 심사 횟수 N을 기준으로 O(N) 짜리 풀이를 생각했다. 하지만 이럴 경우, 10억회의 연산 발생으로 시간초과가 난다. (이 오답 풀이는 맨 아래에 첨부하겠다.) 따라서 O(N) 보다 빠른 풀이, 혹은 심사위원의 수 ( 10만 ) 으로 문제를 굴려야 하는..
https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위 문제에 대한 풀이 입니다. 결국 각 입력값들은 하나의 "덩어리" 이다. ex) 402, 40 -> 402 // 40 은 각각 덩어리. 따라서 각 숫자간의 관계에서 어느 숫자가 앞에오는가? 만 정하면 된다. ex1) 402, 432 432,402 > 402,432 -> 432가 먼저와야한다. ex2) 6, 543 6,543 >543,6 -> 6이 먼저와야한다. ex3) 4,43 4,43 > 43..
https://school.programmers.co.kr/learn/courses/30/lessons/86971 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제는 완전탐색 카테고리의 문제로 분류되었지만, 저는 분리집합(disjoint set) 을 통한 풀이가 더 효율적일 것 같아 Union-Find 알고리즘과 Path Compression을 통한 풀이로 제출하였습니다. 입력으로 주어진 간선들 중 임의로 1개의 간선을 제거한 뒤, 나눠진 2개의 그룹의 구성원 수를 계산하고, 가장 차이가 적은 경우의 수를 출력하도록 구현하였습니다. #include..
프로그래머스 고득점 kit를 푸는데, 알고리즘 분류가 전부 나와있어서 따로 정리해봅니다. 혹시 들어가있는 알고리즘 분류들이 알고 싶으시다면, 비밀 댓글 달아주시면 답장 드리겠습니다! https://school.programmers.co.kr/learn/challenges?tab=algorithm_practice_kit 위 링크의 문제들을 알고리즘 분류를 섞어서 정리한 자료입니다. 왼쪽 위에 분류가 적혀있으니, 힌트 없이 풀고 싶으신 분들은 왼쪽 위의 분류 화면을 보지 않고 코드를 작성하시길 추천드립니다! 혹시 화면 가리개를 사용하고 싶으시다면 https://mungkhs.tistory.com/8 (유틸) 화면 가리개 프로그램(ver1.0) 1. 프로그램 설명 원격수업용 동영상 및 이번에 NEIS 관련 유..
** 시작하기에 앞서 이번 문제는 문제의 해결보단, Greedy로 오인한 저의 오답에 대한 Trouble Shooting에 가깝습니다. 조이스틱 https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위 문제에 대한 해설입니다. 우선, 각 문자(' A') 를 지정한 문자로 변환하는 것은 아스키 코드로 변환하면 쉽게 횟수를 찾을 수 있습니다. 저의 경우는 각 문자에 대해 일일이 아스키값을 구해서 계산한 뒤, 변환해야하는 횟수를 구했지만,단순히 [1,2,..
이번엔 해시, 혹은 c++ 헤더에 정의되어있는 "map" 자료구조를 통해 해결할 수 있는 문제들에 대하여 이야기해보겠다. map은 기본적으로 {key,value} 의 데이터쌍을 가진다. 사용하기 위해선 #include using namespace std; 위 헤더파일을 include해야한다. 정의는 map 으로 이루어지며, string형 key 값을 가지고, int형 value 값을 가지는 map의 경우 map ma; 와 같이 정의하면 된다. https://school.programmers.co.kr/learn/courses/30/parts/12077 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭..
dp는 상황을 나누고, 그 간의 관계를 파악하여 점화식 혹은 a=b와 같은 고정된 수식으로 표현하여 문제를 효율적으로 해결하는 방식이다. 예를 들어 동전이 연속으로 앞면이 나올 확률을 구한다고 생각해보자. 모든 상황은 결국 나누면 앞면, 뒷면 으로 나뉜다. 이를 수식으로 표현해보자. n-1 째까지 앞면 나올 확률 * 앞면 나올 확률 = n 째까지 앞면 나올 확률 즉 f(n-1)* 1/2 = f(n) 이라는 점화식을 구할 수 있다. dp는 이런 특정 행동 (동전을 던짐) 에 따른 관계의 변화를 수식으로 표현해서 구할 수 있다. (특정행동 n-1번 = 특정행동 n번 이런식으로 생각하면 쉽다.) 전에 knapsack 알고리즘에 대해서도 정리했었는데, dp라고 생각하고 식을 구해도 해결할 수 있다. 추가로 in..
