본문 바로가기
반응형

알고리즘19

ㄷ파이썬 Python | 알고리즘 | 백준 먹을 것인가 먹힐 것인가 ⭕ 파이썬 Python | 알고리즘 | 백준 먹을 것인가 먹힐 것인가➡️ 문제링크https://www.acmicpc.net/problem/7795 ➡️ 문제 탐색하기가장 구현하기 쉬운 방법은 A의 모든 원소와 B의 모든 원소를 비교하는 것이지만, 시간 복잡도는 O(N * M)이며, N과 M이 최대 20,000일 때는 400,000,000번의 연산이 필요하게 된다. 이는 실제 시간으로 4초 이상 걸릴 수 있어 비효율적이라고 판단하였다.문제에서 주어진 조건을 고려할 때, 보다 효율적인 방법이 필요하다고 생각하였다.집합 A와 B를 오름차순으로 정렬하면, B에서 A의 원소보다 작은 원소들을 빠르게 찾을 수 있게 된다. 정렬 자체의 시간 복잡도는 O(N log⁡N) 및 O(M log⁡M)이다.정렬된 B에서 A의 .. 2024. 8. 19.
파이썬 Python | 알고리즘 | 백준 거스름돈 ⭕ 파이썬 Python | 알고리즘 | 백준 거스름돈 ➡️ 문제링크https://www.acmicpc.net/problem/14916 ➡️ 문제 탐색하기2원과 5원 동전만을 사용하여 특정 금액을 거슬러 주는 문제이다. 가장 직관적인 방법은 큰 단위의 동전을 우선적으로 사용하는 것이다. 14원을 거슬러 준다고 가정하면, 처음에 5원으로 최대한 많이 나누어 보면 5원 세 개를 사용하면 15원이 되지만, 14원을 넘으므로 5원 두 개를 사용하면 10원이 되고, 남은 4원을 2원 두 개로 거슬러 줄 수 있다. 6원을 거슬러 준다면, 5원 하나를 사용하면 1원이 남아 불가능하지만, 2원 세 개를 사용하면 가능하다.조건2원과 5원 동전만 사용하여 거스름돈을 주어야 한다.가능한 적은 개수의 동전을 사용해야 한다.그리.. 2024. 8. 15.
파이썬 Python | 알고리즘 | 백준 컵홀더 ⭕ 파이썬 Python | 알고리즘 | 백준 컵홀더➡️ 문제링크https://www.acmicpc.net/problem/2810 ➡️ 문제 탐색하기극장의 한 줄에 있는 좌석의 정보가 주어졌을 때, 모든 사람이 컵홀더를 사용할 수 있는 최대 사람의 수를 구하는 문제이다.일반석(S)의 경우, 각 좌석마다 컵홀더가 하나씩 배치되는 것이 당연하다. 이를 바탕으로 초기 계산은 각 좌석 수 + 1로 설정하였다.커플석(L)은 두 개씩 쌍으로 주어지므로, 하나의 커플석 쌍당 하나의 컵홀더가 필요하다. 따라서 커플석 두 개당 하나의 컵홀더만 필요하다는 점을 고려하여 컵홀더 수를 줄였다. 커플석 두 개당 하나의 컵홀더가 필요하다는 점에서 커플석의 수를 2로 나누는 것이 합리적이다.좌석의 수 N과 계산된 컵홀더 수 중 작은.. 2024. 8. 14.
파이썬 Python | 알고리즘 | 백준 덩치 ⭕ 파이썬 Python | 알고리즘 | 백준 덩치➡️ 문제링크https://www.acmicpc.net/problem/7568 ➡️ 문제 탐색하기두 사람 A와 B의 덩치가 각각 (x, y), (p, q) 일 때, x > p 그리고 y > q이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"라고 판단한다. 같은 방식으로 다른 사람들과 비교하여 자신의 덩치가 몇 번째인지 등수를 매긴다. 최대 N이 50이므로 O(N^2) 복잡도, 연산 약 2,500개로 시간복잡도 1초 안에 충분히 해결 가능하다. 입력 범위를 항상 잘 살피자! 이렇게 모든 경우의 수를 탐색해보는 알고리즘을 완전탐색 또는 브루트포스라고 한다. ➡️ 코드 설계하기사람의 수 N과 각 사람의 몸무게와 키를 입력받는다.각 사람의 몸무게와 키를 리스트.. 2024. 8. 11.
파이썬 Python | 알고리즘 | 백준 나무 조각 ⭕ 파이썬 Python | 알고리즘 | 백준 나무 조각➡️ 문제링크https://www.acmicpc.net/problem/2947 ➡️ 문제 탐색하기1부터 5까지의 숫자가 적힌 나무 조각을 1, 2, 3, 4, 5 순서로 정렬해야 한다. 인접한 두 조각만 바꿀 수 있고, 바뀔 때마다 현재 순서를 출력해야 한다.버블 정렬을 직접 구현하는 문제라고 생각한다. 버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘으로, 시간 복잡도는 O(n^2)이다. 하지만, 항상 5개의 조각만 다루고, 각 단계를 출력해야 하는 요구사항 때문에 버블 정렬이 오히려 적합하다고 생각한다.(N-1) + (N-2) + ... + (2) + (1) = N(N-1)/2 단순 구현 문제는 시간복잡도를 계산할 만큼 빡빡하게 나오는 일이.. 2024. 8. 10.
파이썬 Python | 알고리즘 | 백준 단어 정렬 ⭕ 파이썬 Python | 알고리즘 | 백준 단어 정렬➡️ 문제링크https://www.acmicpc.net/problem/1181 ➡️ 문제 탐색하기우선, 몇 개의 단어를 처리할지를 미리 알아야 하기 때문에 단어의 개수를 먼저 입력받는 것이 필요하다. 처음에는 단어를 리스트에 저장하려 했으나, 문제 조건에서 중복을 제거하라는 것을 보고 set을 사용하도록 변경했다. set은 중복을 자동으로 제거하는 특성이 있다. 따라서, 단어를 하나의 리스트에 저장하는 대신, 중복된 단어를 제거하기 위해 set을 사용한다. set에 원소 하나를 추가하는 시간복잡도는 O(1)이다. N개의 단어들을 set에 넣어야 하므로 , 총 시간복잡도는 O(N)이다. N은 최대 20,000개로 연산 20,000번은 시간 2초내에 충분.. 2024. 8. 7.
파이썬 Python | 알고리즘 | 백준 나이순 정렬 ⭕ 파이썬 Python | 알고리즘 | 백준 나이순 정렬➡️ 문제링크https://www.acmicpc.net/problem/10814 ➡️ 문제 탐색하기2차원 배열을 사용하여 0번째 인덱스에 나이(age)를, 1번째 인덱스에 이름(name)을 저장하고, 나이끼리 비교하면 될 것 같았다. 하지만, 분명 2차원 배열보다 더 좋은 방법이 있을 것 같다는 고민이 들었다. 찾지 못했다. ㅎㅎ 그렇지만 시간복잡도에 있어서 여유 있다고 생각된다. ➡️ 코드 설계하기우선, 회원의 수를 정하기 위한 숫자를 input() 함수를 사용하여 입력받는다.한 줄씩 나이와 이름을 입력받아 2차원 배열 [나이, 이름]에 저장하는 방식으로 설계했다.나이순으로 정렬하는 방법을 고민했는데, sort 함수를 사용하면 어떨지 생각해 봤다... 2024. 8. 6.
파이썬 Python | 알고리즘 | 카카오 개발자 코딩테스트 및 오픈채팅방 알고리즘 ⭕ 파이썬 Python | 알고리즘 | 카카오 개발자 코딩테스트 및 오픈채팅방 알고리즘카카오의 핵심은 카카오톡입니다. 카카오의 신입 공개 채용 코딩 테스트 문제는 대학교 학부 과정에서 배우는 기초 알고리즘에 충실하지만, 문자열 기반 채팅 애플리케이션인 카카오톡은 카카오의 핵심인 만큼 문자열과 관련된 알고리즘이 항상 출제됩니다. ➡️ 2020년 카카오 개발자 신입 공개 채용 1차 1번 오픈채팅방 문제[프로그래머스 문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/42888)문제 설명카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있으며, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있습니다. 신입사원인 김크루.. 2024. 6. 12.
파이썬 Python | 알고리즘 | 시간 복잡도 ⭕ 파이썬 Python | 알고리즘 | 시간 복잡도컴퓨터는 1초에 약 1억 정도의 연산을 할 수 있다고 가정합니다. ➡️ 알고리즘이 왜 필요한가?구글 검색엔진을 예로 들어보겠습니다. 우리가 구글을 통해 검색할 때, 전 세계에서 업로드된 모든 게시물을 검색 키워드와 비교하여 찾으려 한다면 수백 초 이상의 시간이 걸릴 것입니다. 하지만 실제로 구글과 유튜브는 검색창에 키워드를 입력했을 때 빠르면 1초 안에, 느려도 몇 초 안에 검색 결과를 보여줍니다. 이는 효율적인 알고리즘 덕분입니다. 이러한 이유로 대기업에서는 개발자를 채용할 때 알고리즘 시험을 보며, 개발자들에게 있어서 알고리즘은 필수적인 기술입니다. ➡️ 그래서 구글 검색 엔진은?구글의 검색 알고리즘은 비밀에 부쳐져 있지만, 실무적인 개발 이야기로 추.. 2024. 6. 12.
파이썬 Python | 알고리즘 | Coding Test 준비 ⭕ 파이썬 Python | 알고리즘 | Coding Test 준비 문제 해결 역량(알고리즘 및 자료구조)에 관한 학습 기록 레퍼지토리 자주 사용하는 알고리즘 코드를 라이브러리화 ➡️ 사용 언어 변경: Java에서 Python으로 2024년 03월 06일부터 Python을 주 사용 언어로 전환함 다양한 프로그래밍 언어에 대한 학습 욕구 특히, Python은 풍부한 라이브러리 지원으로 알고리즘 학습에 집중하기 용이(예시, 문자열 처리가 다른 언어에 비해 간결하고 쉬움) 따라서, 다양한 상황에 능동적이고 쉽게 대응 가능 ⭕ 학습 계획 ➡️ 알고리즘 개념 학습 학습 내용: 그리디, 구현, DFS, BFS, 정렬, 이진 탐색, 다이나믹 프로그래밍, 최단 경로, 그래프 이론 등 학습 자료: 나동빈님의 YouTube.. 2024. 3. 9.
자바 Java | 알고리즘 | 자료구조(Data Structure) - 배열(Array) 리스트(List) ⭕ 자바 Java | 알고리즘 | 자료구조(Data Structure) - 배열(Array) 리스(List) 두 가지 주요 자료구조인 배열과 리스트는 각각의 특징에 따라 적절한 상황에서 선택되어 사용됩니다. ➡️ 배열(Array) 배열은 연속된 메모리 공간에 값을 저장하는 자료구조입니다. 각 원소는 고유한 인덱스를 가지고 있어 해당 인덱스를 통해 직접 참조할 수 있습니다. int[] numbers = {1, 3, 5, 7, 9}; 배열의 특징 인덱스를 통한 직접 접근: 배열은 각 원소가 고유한 인덱스를 가지므로, 해당 인덱스를 사용하여 빠르게 값을 접근할 수 있습니다. 값의 삽입 및 삭제 어려움: 새로운 값을 삽입하거나 삭제할 때 주변의 값을 이동시켜야 하므로 연산이 복잡합니다. 예를 들어, 두 번째 값.. 2024. 1. 10.
자바 Java | 알고리즘 | 디버깅 ⭕ 자바 Java | 알고리즘 | 디버깅 디버깅은 프로그래밍 과정에서 코드의 논리 오류를 찾아내고 수정하는 중요한 단계입니다. 모든 프로그래머는 실수를 할 수 있으며, 이러한 실수는 코드의 논리 오류로 나타날 수 있습니다. 특히 자바와 같은 언어에서는 디버깅이 더욱 중요한데, 여기에는 몇 가지 핵심적인 이유가 있습니다. 첫째로, 코드 작성 시 실수는 불가피합니다. 논리적인 오류는 문법적인 오류와 달리 컴파일러가 감지하지 못하므로 실행 중에 발견되어야 합니다. 그리고 디버깅을 통해 이러한 오류를 찾아내고 수정할 수 있습니다. 둘째로, 많은 프로그래머들은 문법을 배우는 과정에서 디버깅을 가볍게 여기곤 합니다. 그러나 실제로는 디버깅이 코드 작성 과정에서 필수적인 스킬이며, 특히 코딩테스트를 응시할 때 디버깅.. 2024. 1. 9.
자바 Java | 알고리즘 | 시간복잡도 ⭕ 시간복잡도 시간 복잡도는 알고리즘 선택의 주된 기준 중 하나로, 주어진 문제를 해결하는 데 필요한 연산 횟수를 나타냅니다. 코딩테스트에서는 1억 번의 연산을 1초로 가정하며, 주어진 시간제한 내에 문제를 해결할 수 있어야 합니다. 시간제한이 2초인 경우 최대 2억 번의 연산 안에 답을 도출해야 합니다. ➡️ 시간 복잡도 유형 시간 복잡도는 주로 빅오(O), 빅세타(Θ), 빅오메가(Ω) 세 가지 유형으로 나뉩니다. 빅오(O): 알고리즘의 최악의 경우 시간 복잡도를 나타냅니다. 이는 주어진 입력 데이터에 대해 알고리즘이 최대로 소요될 수 있는 시간을 표현합니다. 코딩테스트에서는 주로 빅오를 고려하여야 합니다. 특히 TEST SET이 복잡하게 나오는 상황에서는 항상 최악의 경우를 염두에 두고 알고리즘을 선.. 2024. 1. 8.
[2023년도 2회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리 ⭕ [2023년도 2회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리➡️ 1. [C 언어 코드] 괄호 안에 알맞은 코드를 작성하시오.[조건]입력값이 54321일 경우 출력값이 43215로 출력되어야 한다.#include int main(void) { int n[5]; int i; for (i = 0; i 정답n[(i + 1) % 5]해설 ➡️ 2. [JAVA 코드] 괄호 안에 알맞은 코드를 작성하시오.[조건]- 예시: 4620원- 1000원, 500원, 100원, 10원의 지폐 및 동전을 이용- 변수: m- 연산자: /, %- 괄호: [ ], ( )- 정수: 1000, 500, 100, 10public class Main { public static void main(Strin.. 2024. 1. 7.
[2021년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리 ⭕ [2021년도 3회] 정보처리기사 정처기 | 실기 기출 | 회차별 정리➡️ 1. 다음 Java 코드에 대한 알맞은 출력값을 쓰시오.class Sugoring { private static Sugoring _inst = null; private int connectionCount = 0; static public Sugoring getInstance() { if (_inst == null) { _inst = new Sugoring(); return _inst; } return _inst; } public void incrementCount() { connectionCount++; }.. 2024. 1. 6.
정보처리기사 정처기 | 필기 4과목 프로그래밍 언어 활용 | 기출문제 정리본, 두문자 ✅ 2022년 04월 24일💡 61. C언어에서 문자열 처리 함수의 서식과 그 기능의 연결로 틀린 것은?strlen(s):  s의 길이를 구한다.strcpy(s1, s2):  s2를 s1으로 복사한다.strcmp(s1, s2): s1과 s2를 연결한다.strrev(s): s를 거꾸로 변환한다. strcmp(s1, s2): 문자열 s1과 문자열 s2를 비교하여, s1이 s2보다 앞에 있으면 음수, s2가 s1보다 앞에 있으면 양수, 같으면 0을 반환하는 함수strcat(s1, s2): 문자열 s2를 문자열 s1의 끝에 연결하는 함수 💡 62. 다음 C언어 프로그램이 실행되었을 때, 실행 결과는?#include int main(int argc, char *argv[]){ int a = 5, b = .. 2023. 2. 27.
자바 JAVA | 백준 1330번 두 수 비교하기 | 조건문(if-else) 활용 https://www.acmicpc.net/problem/1330 1330번: 두 수 비교하기두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오.www.acmicpc.net ✅ 문제두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오.시간 제한: 1 초메모리 제한: 512 MB 💡 입력첫째 줄에 A와 B가 주어진다. A와 B는 공백 한 칸으로 구분되어 있다. 💡 출력첫째 줄에 다음 세 가지 중 하나를 출력한다.A가 B보다 큰 경우에는 '>'를 출력한다.A가 B보다 작은 경우에는 'A와 B가 같은 경우에는 '=='를 출력한다. 💡 출력-10,000 ≤ A, B ≤ 10,000 💡 예제 입력 11 2 💡 예제 출력 1 💡 예제 입력 210 2 💡 예제.. 2022. 9. 28.
자바 JAVA | 백준 11659번 구간 합 구하기 4 | 부분 합을 이용한 구간 합 구하기 알고리즘 https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 jwww.acmicpc.net ✅ 문제수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.시간제한: 1초메모리 제한: 256 MB 💡 입력첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 💡 출력총 M개.. 2022. 9. 13.
개발자로서 성장하기 위한 블로그 ✅ 슈고링슈고링의 티스토리 블로그이다. 2년간의 휴학을 마치고 복학하면서 새로운 시작에 대한 막막함을 느꼈다. 그래서 블로그를 시작하게 되었다. 이 블로그는 나의 공부한 내용을 정리하고 기록하는 공간이자, 다른 분들과 함께 발전하고 자신감을 키우는 공간이다. 주로 컴퓨터 기술, 프로그래밍 등의 주제를 다룰 예정이다. 이 분야들은 빠르게 발전하고 있으며, 새로운 지식과 기술을 습득해야 하는 상황에서 블로그를 통해 기록하고, 공유함으로써 함께 발전할 수 있으면 좋겠다. Java 프로그래밍, 프로그래밍 기초, 알고리즘, 백준 문제풀이, 안드로이드 프로그래밍, 프로젝트 개발, 컴퓨터 과학 등의 카테고리로 구성된 이 블로그에서는 개발자로서 필요한 지식과 스킬을 다룰 예정이다. 또한 새로운 기술이나 프레임워크 등에.. 2022. 9. 12.
반응형