전체 글 35

[이코테] Chap 9. 최단 경로

이론최단 경로 알고리즘이란?Shortest Path; 가장 짧은 경로를 찾는 알고리즘길 찾기 문제다양한 종류가 있고, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있음한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우→ 이렇듯 다양한 사례에 맞는 알고리즘을 적용하면 쉽게 문제를 풀 수 있다.표현주로 그래프를 이용해 표현함각 지점 ⇒ 노드지점 간 연결된 도로 ⇒ 간선(사진)코테에서의 최단 거리 알고리즘 유형컴공 학부 수준다익스트라 최단 경로 알고리즘플로이드 워셜 알고리즘벨만 포드 알고리즘코테에 많이 등장하는 유형다익스트라 최단 경로 알고리즘플로이드 워셜 알고리즘그리디 알고리즘과 DP 알고리즘은 최단 경로 알고리즘에 그대로 ..

카테고리 없음 2024.10.05

[이코테] Chap 8. 다이나믹 프로그래밍

이론시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제는 컴퓨터를 활용해도 해결하기 어렵다. 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이기 때문이다. 따라서 두 요소를 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 하지만 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다! 대표적으로 다이나믹 프로그래밍(Dynimic Programming) 기법이 여기 속한다.프로그래밍에서 보통 다이나믹은 '프로그램이 실행되는 도중에'라는 의미이지만, 다이나믹 프로그래밍에서의 '다이나믹'은 이 의미가 아니다. 예시 - 피보나치 수열기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문..

[백준|골드5] 18405번 경쟁적 전역 - Python(파이썬)

문제NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다. 시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다. 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 ..

[프로그래머스|Lv.2] 괄호 변환 - Python(파이썬)

문제https://school.programmers.co.kr/learn/courses/30/lessons/60058카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')'..

[백준|실버3] 3273번 두 수의 합 - Python(파이썬)

문제https://www.acmicpc.net/problem/3273✓ 시간 제한: 1초 / 메모리 제한: 128MB n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i  입력첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000) 출력문제의 조건을 만족하는 쌍의 개수를 출력한다. 예제 입력195 12 7 10 9 1 2 3 1113 예제 출력 13첫 번째 풀이 - 시간초과이중 반복문을 이용했다. 시간초과 날거라고 예상은 ..

[프로그래머스] 삼각 달팽이 (Lv.2) - Python(파이썬)

https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요. 제한 사항n은 1 이상 1,000 이하입니다.입출력 예풀이 과정문제 아이디어가 생각나지 않아 40분을 끙끙대다가, 결국 다른 사람의..

[Mac] Homebrew 설치하기 | 맥북 필수 프로그램🍺

Homebrew(홈브류)란? Homebrew는 macOS의 패키지 관리 툴이며, 맥북 사용자라면 필수적으로 설치해야할 프로그램 중 하나이다. 간단한 명령어로 다양한 소프트웨어를 설치, 관리, 제거할 수 있어 매우 유용하다! ✓ Homebrew 공식 사이트: https://brew.sh/✓ Homebrew 공식 문서: https://docs.brew.sh/Manpage✓ Homebrew Github 주소: https://github.com/Homebrew/brew Homebrew는 Ruby로 개발되었고, 오픈소스 소프트웨어로 현재(2024년)도 많은 개발자들이 활발하게 개발이 이루어지고 있다. 2010년 Hoebrew는 Github에서 세 번째로 많이 포크된 저장소였을 정도로 활발한 오픈소스 기여가 이루..

IT 2024.08.07

[코드트리 조별과제] 1주차

숫자로 이루어진 사각형Novice Mid 레벨의 문제 풀이와 복잡도 분석을 해보았다.🔗 문제 바로가기 내 코드def n_by_n_rect(n): i = 1 for _ in range(n): for _ in range(n): print(i, end=' ') i += 1 if i==10: i = 1 print() n = int(input())n_by_n_rect(n) 시간 복잡도 (Time Complexity)코드에서 두 개의 중첩된 루프가 있으며, 각 루프는 n번씩 실행된다. 내부 루프 안의 모든 작업은 상수 시간 O(1)에 수행된다.- 외부 루프: n번 반복- 내부 루프: n번..

Coding Test 2024.07.21

[백준] 3009번 네 번째 점 - Python(파이썬)

https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. 입력 세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다. 출력 직사각형의 네 번째 점의 좌표를 출력한다. 예제 입력 1 5 5 5 7 7 5 예제 출력 1 7 7 예제 입력 2 30 20 10 10 10 20 예제 출력 2 30 10 풀이과정 점의 좌표를 세 번 입력받고, x좌표와 y좌표 각각 1번만 나온 값..

[백준] 11005번 진법 변환2 - Python(파이썬)

https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 문제 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 사용한다. A: 10, B: 11, ..., F: 15, ..., Y: 34, Z: 35 입력 첫째 줄에 N과 B가 주어진다. (2 ≤ B ≤ 36) N은 10억보다 작거나 같은 자연수이다. 출력..