본문 바로가기

알고리즘

 (87)
프로그래머스, 공원산책 프로그래머스, 공원산책 문제 https://school.programmers.co.kr/learn/courses/30/lessons/172928 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분류 시뮬레이션 풀이 일단, 시작 위치(S)를 알아야 한다. 중요한 포인트는 산책을 할 수 있는지 여부와 산책 할 수 없을 경우 스킵한다는 점! 처음에 스킵한다는 걸 어떻게 할까 고민하다가 flag(True, False)사용 nr, nc로 도달하게 될 장소를 갈 수 있는지 확인! 만약, 주어진 횟수만큼 갈 수 있다면, flag를 True로 하고 현재 위치를 이동시켜줬..
2.1 삽입 정렬 2. 시작하기 삽입정렬 분할정복 + 병합 알고리즘 2.1 삽입정렬 정렬하고자 하는 숫자 = key n의 크기가 작을 경우 삽입정렬 > 병합정렬 루프 불변성 초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야 한다. 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다면 다음 반복이 시작되기 전까지도 계속 참이어야 한다. 종료조건 : 루프가 종료될 때 불변식이 알고리즘의 타당성을 보이는데 도움이 될 유용한 특성을 가져야 한다. 수학 귀납적 과정과 유사 초기 조건: 불변식 유지 조건 : 불변식 만족 종료 조건 : 불변식 불만족 연습문제 2.1-1 2.1-2 for j = 2 to A.length key = A[j] i = j - 1 while i > 0 그리고 A[i] < k..
프로그래머스, 정수를 나선형으로 배치하기 프로그래머스, 정수를 나선형으로 배치하기 https://school.programmers.co.kr/learn/courses/30/lessons/181832 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 보자마자 백준 뱀 문제가 떠올랐다. 뱀 문제도 복습해야 겠다. 일단 방문표시를 해주시기 위해 0으로 배열을 초기화 해준다. 딱 방문하려고 봤을때 0이면 방문하면 되는 것! result = [[0 for _ in range(n)] for _ in range(n)] 그리고 북동남서 모든 방향으로 갈수 있도록 방향과 백터를 표시해준다. 행열에서 (..
백준 2447번 별찍기 - 10 백준 2447번 별찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 행 index 를 3으로 나눴을 때 나머지가 1이면서 열 index 를 3으로 나눴을 때 나머지가 1인 경우에만 빈칸으로 출력하면 위와 같이 찍힐 것이다. 하지만, 규칙에서는 행 index 3,4,5 와 열 index 3,4,5 일 때 빈칸이어야한다. 3분할로 자꾸 쪼개지는 느낌의 규칙! index를 3으로 나눠봤다. 그랬더니 행 i..
1.2 기술로서의 알고리즘 1.2 기술로서의 알고리즘 시간과 메모리는 한정적인 자원이므로 알고리즘을 공부해 시간과 공간의 자원을 효율적으로 사용해야 함. 📌 알고리즘의 역할 고급 컴퓨터 아키텍처와 제작 기술 사용하기 쉽고 직관적인 그래픽 사용자 인터페이스(GUI) 객체 지향 시스템 통합 웹 기술 유선 및 무선 모두에 대한 빠른 네트워킹 기계 학습 모바일 장치 📌 하드웨어 = 알고리즘 설계 응용 프로그램 = 알고리즘 설계 즉, 알고리즘 작업을 수행하는 방법이 곧 기계 학습이라고 생각 할 수 있음. 컴퓨터가 계산을 수행하고, 정보를 검색하고, 데이터를 정렬하고, 오류 없이 수많은 다른 작업을 수행하도록 도와주는 게 바로 알고리즘이다. 1.2-1 흠..네이버 길찾기 어플을 사용할때, 걸리는 시간 거리 데이터를 이용해 알고리즘 기능으로 ..
1.1 알고리즘 1.1 알고리즘 다량의 데이터 : 정보를 많이 얻을 수록 시간, 장비, 자금, 인적자원 등이 소요된다. 알고리즘 기술은 이러한 자원을 효율적으로 절약해준다. 빠른 서비스 제공 : 테이터가 전송되는 경로를 찾거나, 특정 정보가 있는 페이지를 빨리 검색하는 문제 등을 해결해준다. 보안 : 개인정보 공개키 암호화, 전자 서명 등의 핵심 기술은 수치 알로리즘과 정수론 등을 기반으로 만들어 졌다. 기업 기대 수익 극대화 : 석유회사 어디에 유정을 뜷어햐 하는지 결정, 정치 입후보자의 승리 가능성 높은 캠페인 예측, 최소 비용이 드는 승무원 스케줄 관리 및 배치, 추가 장비 배치할 위치 결정. 현실세계에서 알고리즘으로 최상의 해를 구하는건 불가능에 가깝다. 하지만 최적의 해를 찾는데는 효율적이라 할 수 있다. 📌 ..
백준 2869 달팽이는 올라가고 싶다 백준 2869 달팽이는 올라가고 싶다 문제 https://www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 풀이 처음 이 문제의 식을 이해하는데 많이 시간이 소요됐다. 이 문제의 핵심은 낮과 밤! 하루를 넘어가는 기준을 잘 생각해봐야 한다. 1일 최대 갈 수 있는 거리 : 낮 이동 거리 2일 최대 갈 수 있는 거리 : 낮 이동거리 - 밤 이동거리 + 낮 이동거리 3일 최대 갈 수 있는 거리 : 낮 이동거리 - 밤 이동거리 + 낮 이동거리 - 밤 이동거리 + 낮 이동거리 이제 조금 규칙이 보이는가? 이때, (V-B)/(..
프로그래머스, 예산 프로그래머스, 예산 예산 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 6개월전? 나의 풀이 def solution(d, budget): d.sort() for i in range(1, len(d)+1): if(d[0] > budget): return 0 if(sum(d[:i]) > budget): break else: answer = i return answer 왜 이렇게 풀었는지.. 생각 안나지만, 오늘 푼 풀이와 별반 다르지 않다. 다시 풀어보니, 이 문제는 그리디 문제였다. 6개월 전에는 그리디 개념도 몰랐던 나. 예산이 적은 부서부터 지급해야 최..
백준 8983 사냥꾼 백준 8983 사냥꾼 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 처음 이 문제를 봤을 때, 풀이 방법을 아예 모르겠어서 막막했었다. 여러번 반복해서 보니, 신기하게 풀린다. 접근방법 사대를 움직여 해당 동물을 죽일 수 있는지 살펴본다! 기준을 사대로 잡아야 한다!! 풀이 사대 길이와 |x-a| + b 길이 비교해 해당거리 내에 있으면 동물을 잡을 수 있고 없으면, 사대 위치를 조정해..
[Hash Table] 백준 10816 숫자 카드 2 [Hash Table] 백준 10816 숫자 카드 2 📌 문제 백준 10816 숫자 카드 2 난이도 : 실버 4 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 분류 : Accepted 📌 Hash Table(Dictionary) target in hash_table.keys() // True or False 반환 만약 해시테이블 key값에 해당 숫자 있으면 해당 키값의 벨류를 하나 증가시킴 없다면, key값..

티스토리툴바