본문 바로가기

Problem Solving

 (85)
알고리즘과 효율성 분석 알고리즘이란? 문제를 해결하는 단계적인 절차를 말한다. 알고리즘을 설계하고 분석하는 기술을 배우는 이유는 무엇일까? 새로운 문제에 직면했을 때 그 문제를 해결하기 위한 방법들을 익혀두기 위함이다. 여러 가능한 방법들이 있을 때 알고리즘 분석을 통해 어떤 방법을 선택할 지 결정할 수 있도록 수치화 하는 능력을 길러야 한다. -> 문제 해결력 제고 알고리즘 분석 요소 알고리즘을 수행했을 때 소요되는 시간 알고리즘을 수행할 때 차지하는 메모리 공간 알고리즘 분석 Time Complexity Analysis (시간 복잡도 분석) input size에 따라서 basic operation이 몇번 수행되는 지 결정하는 절차를 말한다. CPU에서의 실제작동 시간, 명령문의 개수, 프로그래밍 언어, 프로그래머, 포인터의..
[서평] Do it! 알고리즘 코딩테스트 (파이썬편) https://www.aladin.co.kr/shop/wproduct.aspx?ItemId=299409119 Do it! 알고리즘 코딩 테스트 : 파이썬 편 네이버, 카카오, 삼성, 라인 등 주요 IT 기업의 시험에 나오는 알고리즘 내용이 모두 담겨 있다. 책에 수록된 알고리즘 문제 100개는 모두 최신 기출 유형을 반영하고 있어서 이 책의 문제만 다 풀 www.aladin.co.kr 좋은 기회가 되어 이지스퍼블리싱의 'Do it! 알고리즘 코딩 테스트 파이썬 편(김종관)' 의 서평단을 하게 되었습니다. 기회를 주신 이지스퍼블리싱 관계자님께 감사 말씀을 전합니다. 현재 IT관련학과 4학년이기도 하고, 알고리즘 관련 동아리에서 튜터로 활동한 경험을 바탕으로 책을 학습자의 입장과 지도자의 입장에서 바라보려고..
7869. 두 원 https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net 문제 설명 두 원이 주어졌을 때, 두 원이 교차하는 영역의 넓이를 소수점 셋째자리까지 구하면 된다. solve 문제에서 제시하는 조건은 각 원의 중심 좌표와 반지름이다. 코사인 법칙을 활용해 문제를 해결할 수 있다. 먼저 두 원의 위치를 파악한다. 두 원의 중심을 잇는 선분을 긋고 이 선분의 길이를 d라고 하자. 1. 두 원이 멀리 떨어져 교차하는 영역이 없는 경우. ( d > r1 + r2) 2. 두 원이 외접하는 경우 ( d = r1 + r2) 3. 두 원이 ..
11780. 플로이드 2 https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 설명 문제 제목처럼 플로이드-워셜 알고리즘을 한 뒤, 경로 추적을 통해 i -> j 로 가는 최소비용의 경로를 출력하는 문제이다. solution 먼저 플로이드-워셜 알고리즘을 통해 최소비용 테이블은 만든다. i에서 j로 가는 비용을 i -> k -> j 비용으로 갱신할 때, 추적 테이블에 i -> j 갈 때 k를 거쳐간다고 저장한다. 1 2 3 4 5 6 7 8 9 10 11 12 13..
3015. 오아시스 재결합 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 문제 설명 N명이 한 줄로 서 있는데, i번째에 서있는 사람과 j번째에 서있는 사람 (i < j) 사이에 둘중 한 명보다 키가 큰 사람이 없으면 서로 볼 수 있다고 한다. 이 때, 서로 볼 수 있는 쌍의 수를 구하는 문제이다. solution i번째에 서있는 사람과 j번째에 서있는 사람 사이에 둘 중 한 명 보다 키가 큰 사람이 있으면 서로를 볼 수 없고, 만약 i번째에 서..
1509. 팰린드롬 분할 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 설명 어떤 문자열이 주어집니다. 팰린드롬 단위로 문자열을 분할했을 때, 분할의 수가 가장 적은 값을 출력하면 되는 문제입니다. 풀이 분할 수를 가장 적게 하려면 팰린드롬 단위로 자를 때 가장 큰 단위로 잘라야합니다. 문자열 "AAAA"를 {A, A, A, A}, {AA, AA}, {AAA, A} .... 으로 나눌 수 있지만..
1007. 벡터 매칭 https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net 평면상의 좌표 N개가 주어지고, 점 2개씩 짝지어 벡터를 이룰 수 있다. 각 점들을 1번만 사용하고 2개씩 매칭하여 N/2 개의 벡터를 만들 수 있다. 이렇게 만든 N/2개의 벡터들을 다 더한 벡터의 길이가 최소가 되도록 만들면 된다. sol1. 재귀 완전탐색으로 탐색하면서 벡터를 만들어 갔다. 현재 위치가 N이 되는 순간 벡터 요소의 제곱들의 합을 비교하여 최소값을 찾았다. 최적화를 한..
세그먼트 트리 - (3). K번째 원소 찾기 이번 글은 세그먼트 트리 활용중 하나인 K번째 원소 찾기 입니다. https://www.acmicpc.net/problem/12899 12899번: 데이터 구조 첫째 줄에 사전에 있는 쿼리의 수 N 이 주어집니다. (1 ≤ N ≤ 2,000,000) 둘째 줄부터 N개의 줄에 걸쳐 각 쿼리를 나타내는 2개의 정수 T X가 주어집니다. T가 1이라면 S에 추가할 X가 주어지는 것입니 www.acmicpc.net 문제에는 두 가지 종류의 쿼리가 존재한다. 유형 1 : 데이터베이스 S에 자연수 X를 추가한다. 유형 2 : S에 포함된 숫자 중 X번째로 작은 수를 응답하고 그 수를 삭제한다. 쿼리는 최대 200만개 까지 가능하니 한 쿼리를 최대 O(NlogN)에 처리해야 한다. 다행히도(?) X의 범위는 1부터 ..

티스토리툴바