본문 바로가기

알고리즘/프로그래머스

(13)
[프로그래머스 LV3/C++] 알고리즘 - 등산 코스 정하기 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘  등산 코스 정하기를 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/118669 [문제 접근]휴식 없이 이동해야 하는 시간 중 가장 긴 시간인 intensity를 숙지하는 게 제일 중요합니다. 저는 이를 잘못이해하면 풀이를 하는데 시간을 많이 잡아먹었습니다. 여러 출입구 와 산봉우리가 있는데, 출입구에서 산봉우리까지 이동하면 intensity들을 파악하고 이 intensity들 중에서 가장 최소인 intensity를 경로 중에 가지고 있는 산봉우리의 번호를 찾아야 합니다. 이때 intensity가 같다면 산봉우리번호가 작은 것이 정답입니다. intensity의 정의..
[프로그래머스/C++] 알고리즘 - 표현 가능한 이진 트리. 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 - 표현 가능한 이진 트리를 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/150367 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근처음에는 삽질을 했습니다. 중위 순회를 파악해서 중위 순회한 트리를 원래 트리로 복원하는 방법도 고려해보았습니다.하지만 이 문제의 핵심은 루트노드, 서브 루트 노드의 값을 살펴보는 것입니다.리프노드를 제외한 서브 루트 노드들의 값이 1일 때 참입니다. 이때 루트 노드를 체크하고,..
[프로그래머스/C++] 알고리즘 - 오픈 채팅방 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 오픈 채팅방을  풀어보도록 하겠습니다.  https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr[문제 접근]이 문제는 문자열을 활용한 구현문제입니다. 유저아이디값이 있고, 이에 매칭되는 닉네임이 변경되는 문제이기 때문에 unorded_map을 활용하여 풀었습니다. [풀이 전략]1. c++은 split함수가 없기 때문에 직접 구현합니다.2. for문을 돌면서- Enter와 Change에 해당되면 ..
[프로그래머스/C++] 알고리즘 - 문자열 압축 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 문자열 압축을 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  [문제 접근]문자열을 활용한 단순 구현문제입니다. [풀이 전략]중복이 되지 않는 경우는 중복개수 1을 추가할 필요가 없다는 부분에 유의하여 구현을 하면 됩니다.주의할 점은 문자열이 한 개 인경우에는 answer초기값이 출력되기 때문에 이에 대한 예외처리가 필요합니다. [코드]#include #inclu..
[프로그래머스/C++] 알고리즘 - 괄호 변환 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 - 괄호 변환을 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  [문제 접근]문제가 길어서 읽으면서 머릿 속에 막 들어오지 않아서 최대한 적으면서 조건들을 분기화하면서 읽었습니다.이해가 안되는 부분들은 예제들을 보면서 최대한 이해하려고 했습니다. 문제는 재귀함수가 가미된 단순 구현문제였습니다.아래처럼 적으면서 읽었습니다. [풀이 전략]위에 작성한 문제 접근방법을 ..
[프로그래머스/C++] 알고리즘 - 메뉴 리뉴얼 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 메뉴 리뉴얼 을 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 접근]orders의 최대크기 20, orders각 원소의 크기를 10, course =[2,3,4,5,6,7,8,9,10]라 가정하면연산 개수는 약 20*(10C2+10C3+10C4+ ... 10C10) 으로 시간복잡도가 크지 않음을 알 수 있습니다.그래서 완전탐색으로 접근했고, 조합을 이용하여..
[프로그래머스/C++] 알고리즘 - 주차 요금 계산 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 주차 요금 계산 을 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 접근]문자열을 다루는 능력과 구현력을 요구하는 문제입니다. c++에서는 split함수가 제공되지 않기 때문에 직접 구현을 해주었고, unordered_map과 map을 이용하여 문제에 접근했습니다. 유의해야할 점은 00:00도 존재하기 때문에 Out을 할 때 0이 아니라 -1로 변경해주어야 ..
[프로그래머스/C++] 알고리즘 - 양궁대회 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 - 양궁대회 를 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 접근]처음에 얼핏 생각하면 과녁 점수마다 0~10발 맞힐 수 있으니 10^11이니 완전탐색이 불가능하고 그리디 알고리즘으로 접근해야하는 거아닌가라고 생각을 했습니다. 그러나 모든 과녁점수의 맞힌 횟수의 합이 n이기 때문에 시간복잡도가 현저히 낮다는 사실을 알 수 있고, 정확성 테스트를 위하 시간..
[프로그래머스/C++] 알고리즘 - 도넛과 막대 그래프 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 - 도넛과 막대 그래프 를 풀어보도록 하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 접근]시간제한은 딱히 나와있지는 않았지만 edges의 길이가 백만이하이고, 노드번호의 최댓값이 백만이기 때문에 시간복잡도를 신경쓰면서 문제를 접근했습니다.처음에 이 문제를 어떻게 풀어나가야할 지 바로 생각이 들지는 않았습니다.예제를 보면서 그래프와 무관한 정점 하나를 어떻게 찾아야할..
[프로그래머스/C++] 알고리즘 - 주사위 고르기 안녕하세요! 테크지니어22입니다.오늘은 프로그래머스 알고리즘 주사위 고르기를 풀어보도록 하겠습니다. [문제 접근]처음에는 for문으로 묵묵히 풀었습니다. 그러나 시간초과가 발생했습니다. 시간복잡도를 줄여야 한다는 것을 느꼈고, 어떤 알고리즘을 이용해야할지 생각했습니다. 가장 만만한게 이분 탐색이었는데 왜 이분 탐색을 써야하는지 당위성을 찾지 못했습니다. 이후 도움을 받았는데 아래의 예제표를 보고 어떤 알고리즘을 풀어야할 지 생각해보라는 힌트를 얻었습니다.열을 보았을 때 b의 값보다 큰 a값이 나오는 순간만 찾으면 B가 특정값일때 이 값보다 큰 A의 값들의 개수를 셀 수 있습니다. 이를 통해 이분 탐색의 upper_bound 개념을 떠올릴 수 있었고 이를 활용하여 문제를 풀었습니다.[풀이 전략]1. 주사위..