본문 바로가기

algorithm

[프로그래머스] - "괄호 변환" C++ / 재귀 / stack 2022. 7. 13. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 # 해석 '(' 과 ')' 두가지 문자로만 이루어진 문자열이 주어졌을 때, 올바른 괄호 문자열로 바꿔서 반환하는 것이 목적입니다. 그리고 올바른 괄호 문자열로 변환하는 알고리즘은 문제에서 다음과 같이 주어졌습니다. 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 ..
[프로그래머스] - "메뉴 리뉴얼" C++ / 조합 / map 2022. 7. 13. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 # 해석 파라미터로 orders (모든 주문) , course (코스를 구성하는 요리의 개수) 두가지가 주어지며, orders에 담긴 단품메뉴들을 course에 적힌 개수만큼 조합해서 코스요리를 만드는 것이 목표입니다. 고려해야 할 점은 1. 코스요리로 만들 단품요리들은 2번이상 손님에게 주문된 메뉴여야 합니다. 2. 2번 이상 주문된 메뉴들이라도 전부 코스요리가 될 수 있는것..
[프로그래머스] - "신고 결과 받기" C++ / map 2022. 7. 11. 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/92334 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이과정 문제 해석 1. 각 유저는 여러번 신고당할 수 있으며, k번 이상 신고당하면 정지가 된다. 2. A 유저가 B 유저를 여러번 신고할 순 있지만, 한 번만 신고한 걸로 처리된다. 3. id_list 벡터에는 전체 유저 리스트 / report 벡터에는 누가 누구를 신고했는지가 저장되어있다. 4. id_list 벡터에 들어있는 유저 순서대로 몇명을 정지시켰는지 배열에 저장해 리턴한다..
백준 4375 - 1 (모듈러 연산) 2022. 5. 3. 13549번: 숨바꼭질 3 (acmicpc.net) 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이과정 및 주의사항 수빈이는 now*2 (순간이동) / now+1 / now-1 3가지 좌표 중 하나로 이동할 수 있습니다. 순간이동은 시간이 걸리지 않으며 / 한칸 이동 시 시간 + 1이 추가됩니다. 만약 순간이동 역시 시간이 1초 걸렸다면 단순히 bfs로 해결할 수 있었지만, 순간이동의 시간이 걸리지 않으므로 가중치를 최대로 주어서 풀어줬어야 했습니다. 따라서 일반적인 qu..
백준 4375 - 1 (모듈러 연산) 2021. 10. 6. 문제 : 4375번: 1 (acmicpc.net) 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 풀이과정 1, 11, 111, 1111 ... 이렇게 자리수가 하나씩 늘어난다고 할 때 입력값 n의 배수인 가장 작은 수의 자리수를 구하는 문제였습니다. ex) 답이 1111이라면 4 출력 한자리씩 계속해서 늘려가면서 답을 비교해보면 좋겠지만 무한히 늘어난다면 int형으로 담을 수 없기 때문에 모듈러 연산을 통해 풀이할 수 있었습니다. 풀이의 주석을 참고해주세요 #include #include #include #include #include #include #include..
백준 14500 - 테트로미노 2021. 9. 30. 문제 : 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이과정 블록을 만들기 위해 DFS를 사용하는 백트래킹 방법을 사용하면 풀 수 있는 문제였습니다. 다만 ㅜ 모양은 DFS로 만들 수 없는 모양이기 때문에 따로 예외처리를 해줘야 했습니다. #include #include #include #include #include #include #include #include using namespace std; int N,M; int A[501][501]; int ..
백준 17298 오큰수 (stack) 2021. 9. 26. 문제 : 17298번: 오큰수 (acmicpc.net) 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이과정 for문을 2중으로 돌리게 된다면 풀 수 있을것 같은 문제입니다. 하지만 수열의 최대 크기가 1,000,000 이기 때문에 O(N^2)의 시간복잡도로는 시간제한 1초 내에 해결할 수 없습니다. 따라서 stack을 사용한다면 O(N) 시간 내에 해결이 가능합니다. 간단한 풀이과정을 작성해보면, 수열의 맨 끝 숫자부터 시작해서 해당 숫자보다 더 큰 숫자가 스택에 있는지 탐색하고, answer 배열에 있다면 저장하고..
백준 2109 순회 강연 ( greedy ) 2021. 9. 25. 문제 : 2109번: 순회강연 (acmicpc.net) 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 접근과정 이 문제를 풀기 위해서, 정렬된 vector와 priority queue 2가지를 사용했습니다. 처음에는 그냥 vector만을 사용해서 해당 날짜마다 가장 큰 강연료들만 더해주면 된다고 생각했는데, 문제에서 d일 안에 와서 강연을 해준다고 했지, d일에만 정확히 강연을 한다고는 하지 않았습니다. 예를들어 (d,p) = (1,1), (2,10), (2,10) 예제의..

티스토리툴바