자두의 데브로그

* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다. https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4 정렬 알고리즘 정렬: 데이터를 특정 기준에 따라 순서대로 나열하는 것 → 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용됨 ex. 데이터의 개수가 적을 때, 데이터의 개수가 많지만 데이터의 범위가 특정하게 한정되어있을 때, 이미 데이터가 정렬되어있을 때 컴퓨터에게 정확히 어떠한 방식으로 정렬을 수행할 것인지 코드를 사용해서 나타내어야 함 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복 → 매번 현재 범위에..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을www.acmicpc.net[문제 이해]나이와 이름이 주어졌을 때 나이순으로 정렬하고, 만약 나이가 동일하다면 입력 받은 순서대로 회원을 정렬하는 문제였다. [문제 풀이]문제의 난이도는 높지 않아서 해결 방법은 쉽게 찾긴 했지만 헷갈리는 부분이 몇 개 있었다.1. 입력을 어떻게 받아야 하지?2. 정렬 기준을 어떻게 하지?3. 출력은 어떻게 하지?사실 문제를 풀면서 당연히 고민해보게 될 부분인데 이번에는 특히나 문제가 쉬운 만큼 고민이..

https://www.acmicpc.net/problem/18870 Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 " data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/18870" data-og-url="https://www.acmicpc.net/problem/18870" data-og-image="https://scrap.kakaocdn.net/dn/btjHbV/hyVDEsnKE8/CukpDZnIkubYTSCFFBrH9K/img.png?width=2834&height=1480&face=0_0_2834_1480"> 18870번: 좌표 압축수직선 위에 N개의 좌표 ..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.www.acmicpc.net[문제 이해]알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래의 조건에 따라 정렬하는 프로그램을 작성하는 문제이다.1. 길이가 짧은 것부터2. 길이가 같으면 사전 순으로단, 중복된 단어는 하나만 남기고 제거한다. [문제 풀이]단어 리스트를 받았을 때, 조건대로 짧은 순으로 먼저 정렬하고, 만약 길이가 같으면 사전 순으로 정렬하는 문제라 어렵지 않게 풀 수 있었다. 그 전에 받은 리스트 중..

https://www.acmicpc.net/problem/11047 11047번: 동전 0첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)www.acmicpc.net [문제 이해]입력 받은 동전 종류 중 일부를 적절히 사용해서 입력 받은 결과 값을 만들기 위해 필요한 최소 동전 개수를 구하는 문제이다.  [문제 풀이]내림차순 정렬을 통해 가지고 있는 동전 중 가장 높은 수부터 만들어야 하는 값과 비교한다. 가지고 있는 동전이 크다면 더 작은 동전과 비교해가며 동전의 개수를 센다. 이때 동전의 개수는 ..

* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다. https://www.youtube.com/watch?v=7C9RgOcvkvo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=3 이번 주차 개요 탐색: 많은 양의 데이터 중 원하는 데이터를 찾는 과정 → 특정 조건에 맞는 데이터가 존재하는지, 존재한다면 어떤 위치에 존재하는지.. ex. DFS, BFS: ⭐ 매우 자주 등장하는 유형 ⭐ 스택 먼저 들어온 데이터가 나중에 나가는 형식 (선입후출): 먼저 입력되는 데이터가 나중에 출력 → 입구와 출구가 동일한 형태 ex. 박스 쌓기 → 다양한 알고리즘에서 사용되기 때문에 스택의 동작 방법과 사용 방법에 대해 꼭 숙지하기! 동작) 삽입(원소) + 삭제() sta..

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 이해]주어진 숫자들을 활용하여 덧셈 혹은 뺄셈 만을 사용하여 target에 해당하는 숫자가 결과 값으로 나오도록 계산할 수 있는 가짓 수를 세는 문제였다. 예를 들어, -1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3 이런 식으로 numbers가 [1, 1, 1, 1, 1] 로 주어졌을 때 target이 3이 되는 방..

* 해당 포스팅은 아래 알고리즘 강의를 듣고 정리한 내용입니다. https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2 Greedy (그리디 알고리즘) 탐욕법: 지금 당장 좋은 것만 구함 (최소한의 아이디어) => 크루스칼/다익스트라와 같이 잘 알려진 알고리즘을 제외하고 출제 시 해당 문제를 풀기 위한 최소한의 아이디어를 적절히 떠올릴 수 있어야 풀리도록 출제 ⭐ 정당성 분석 → 단순히 현재 상황에서 가장 좋아보이는 것 => 반복 선택하는 것: 최적해를 보장하는지 검토하는 과정이 필요 탐욕적으로 현재 상황에서 지금 당장 좋은 것만 고르는 방법 = 탐욕법 → 최적의 해를 구할 수 있는지 검토 과정 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42862 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr [문제 이해]체육복을 도난 당한 학생들이 lost, 여분의 체육복을 가진 학생들이 reserve 리스트로 표현하고 있다. 이 문제에서 가장 중요한 제한 사항은 여분의 체육복을 가진 학생이 체육복을 도난 당했을 때, 더이상 체육복을 빌려줄 수 없기 때문에 lost와 reserve 모두에서 제외되어 도난을 당하지도 않고, 체육복을 빌려주지도 않는 상태가 된다는 것을 이해하는 것이다.이 외에는 본인보다 앞..