programming/알고리즘 풀이 (40) 썸네일형 리스트형 [programmers] 118667번 - 두 큐 합 같게 만들기 (brute force, 2022 KAKAO TECH INTERNSHIP) 1. 문제 및 예제 Brute force 문제임을 알았지만, 어느 정도 돌려야할지 모르겠어서 초반에 시간 초과가 좀 나온 문제다. 그것만 정하면 알고리즘을 세우는데는 문제가 없었다. 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나누는건 간단하다. 1. 가장 큰 값이 전체 합의 반 보다 크거나, 전체 합이 홀수면 -1을 반환. 2. 만약 두 큐의 합이 같다면 count를 정답으로 반환. 3. 큰쪽의 원소를 pop하여 작은쪽에 push 4. 위의 과정 300000만큼 반복(전체 원소를 이동시키는 수) 다음은 전체 코드이다. #inclu.. [프로그래머스] 17679번 - 프렌즈4블록 (구현, 2018 KAKAO BLIND RECRUITMENT) 1. 문제 및 예제 엄청난 구현 문제. 설계를 잘 하면 그렇게 어렵지 않게 해결할 수 있다. 중요한 점은 한 배열에서 사라질 모든 블럭을 찾아낸다는 것 같다. 블럭이 포함되어 있다는게 조금 까다로웠다. https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나눠보았다. 1. 블록을 터트리고 터진 블록의 갯수를 반환한다. 2. 터진 블록을 아래로 내린다. 다음은 전체 코드이다. #include #include #include #in.. [프로그래머스] 17686번 - 파일명 정렬 (구현, 2018 KAKAO BLIND RECRUITMENT) 1. 문제 및 예제 간단하게 문자열을 다루는 문제였다. 문자열을 입력에 맞게 나누는 것은 어렵지 않았지만, 안정 정렬에 관한 지식이 있었어야 했다. C++같은 경우는 관련 정렬 함수를 지원해주었지만 미리 알지 않았으면 큰일날뻔 했다... https://school.programmers.co.kr/learn/courses/30/lessons/17686 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 안정 정렬을 알고있으면, compare함수를 커스텀하여 풀 수 있는 문제이다. 문제를 다음처럼 쪼개보았다. 1. 문자열을 전부 소문자로 변경한다. .. [프로그래머스] 72411번 - 메뉴 리뉴얼 (구현, 2021 KAKAO BLIND RECRUITMENT) 1. 문제 및 예제 programmers에서 단계별로 문제를 풀다가 만난 문제다. 처음 문제를 보고 이게 대체... DP인가... 백트레킹인가... 싶었는데 입력 크기를 보고 무조건 브루트포스구나 싶었다. O(N^2)의 조합 문제로 해결하였다. 중간에 set container가 말을 안 들어서 vector로 전환하는 과정에서 시간이 좀 걸렸다. 30분에서 40분 정도? 걸린 것 같다. https://school.programmers.co.kr/learn/courses/30/lessons/72411 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과.. [프로그래머스] 68645번 - 삼각 달팽이 (재귀함수) 1. 문제 및 예제 이게 무슨 유형의 문제인가... 구현인가 싶었는데 재귀가 정답이었다. 배열에 그리는 문제를 전에 만나봐서 예외 처리 빼고는 어렵지 않게 설계할 수 있었다. 재귀함수 잘 쓰고 싶다.. 지금은 그냥 써야될 때 쓰는 수준? 책에서 본 알고리즘 풀이들은 재귀함수를 마치 무기처럼 자유자재로 쓰던데 그 경지에 도달할 때 까지 연습하고 싶다. https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이과정 문제를 나누는게 참 중요하다는걸 .. [백준 알고리즘] 1197번 - 최소 스패닝 트리 (크루스칼 알고리즘) 1. 문제 및 예시 실행 결과 solved.ac의 CLASS가 올라갈수록 모르는 알고리즘이 많다. 어제 토스 코테 한번 찍먹하고 많이 반성하게 됐다. 모르는 것을 공부하는게 맞는 것 같다. Union-find를 활용한 크루스칼 알고리즘을 공부하고 적용해보았다. 한큐에 초록 글자가 떠서 너무 좋았다. 출처: https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 문.. [백준 알고리즘] 2467번 - 용액 (투 포인터) 1. 문제 및 예시 실행 결과 투 포인터를 활용하는 문제... 나름 재밌었다. 보통 이런 경우는 이분탐색 처럼 구현을 하게 되는데 그 과정은 어렵지 않지만 어떤 문제로 접근해야하는지 찾는 과정이 이분탐색 혹은 투 포인터 문제의 핵심이라는 생각이 든다. 출처: https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 이분탐색 진행 왼쪽과 오른쪽으로 부터 시작하여 두 값의 합이 0보다 크면 음수쪽이.. [백준 알고리즘] 11779번 - 최소비용 구하기 2 (Dijkstra에서 경로를 출력하는 방) 1. 문제 및 예시 실행 결과 간단한 다익스트라 문제이지만, 경로를 출력해야한다. 처음에는 문자열을 옮기는 방식으로 풀었는데, 원인을 알 수 없는 이유로 틀렸다는 문자만 계속 떴다. 그래서 경로를 배열에 저장하는 방식을 사용했다... 문자열도 같은 원리인데 대체 왜 그러는지 참... 출처: https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 2. 풀이과정 문제를 잘게 나눠봤다. 1. 입력 2. 다익스트라 진행 3. .. 이전 1 2 3 4 5 다음
