티스토리

대범하게
검색하기

블로그 홈

대범하게

bo5mi.tistory.com/m

대범하게 님의 블로그입니다.

구독자
22
방명록 방문하기
공지 개발자의 평생 공부 : [임백준 칼럼⋯ 모두보기

주요 글 목록

  • [알고리즘] 유클리드 호제법 & 백준(최대공약수와 최소공배수) 유클리드 호제법 유클리드 호제법을 알기 전에 먼저 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 말한다. 우리가 알고자 하는 유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다. (A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다는 것이다.) 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r)와 같다는 말이다. (gcd()는 최대공약수를 나타내는 표기이다.) 예시 입력으로 보면, gcd(24, 18) = gcd(18, 6) = gcd(6, 0)인 것이다! 여기서 b가 0이 되는 순간의 6이 바로 최대공약수가.. 공감수 0 댓글수 0 2022. 12. 13.
  • [알고리즘] 이진 트리, 이진 검색 트리 & 백준(이진 탐색 트리, 트리의 순회) 이진트리(Binary Tree) : 노드가 왼쪽 자식(left chile)과 오른쪽 자식(right child)만 가진다. 자식이 없을 수도 있다. (최대 두 개의 자식 노드를 가지는 트리 형태의 자료구조로서, 단순히 값을 저장하기 위한 용도로 사용되기 보다는 효율적인 탐색 혹은 정렬을 위해 사용된다.) 완전 이진 트리(Complete Binary Tree) - 마지막 레벨을 제외하고, 모든 레벨에 노드가 가득 찬다. - 마지막 레벨은 왼쪽부터 채우고 끝까지 꽉 차지 않아도 된다. - Heap, 우선순위 큐에서 사용하는 트리 구조이다. * 힙(Heap): 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리(complete binary tree)를 기본으로 한 자료구조이다. 이진 .. 공감수 8 댓글수 2 2022. 10. 12.
  • [알고리즘] BFS 뿌셔 DFS 뿌셔 BFS - BFS = Breath-First Search - 가까운 노드부터 우선 탐색 : s로부터 거리가 k+1인 한 정점을 만나기 전에, s로부터의 거리가 k인 정점을 모두 발견하는 알고리즘 (CLSR에 적힌 정의) - 큐 자료구조를 이용: 1. 탐색 시작 노드를 큐에 삽입, 방문 처리 => Queue에 들어있는 애들 = frontier 2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 => frontier 갱신 1) 큐에서 popleft() (popleft()한 값 u / deque이기 때문에 popleft()를 통해서 큐의 맨 앞 요소를 빼줌) 2) u의 인접 노드 v 를 방문했는지 확인 3) 방문 안 했으면 큐에 v 삽입 + v의 dist.. 공감수 6 댓글수 0 2022. 10. 10.
  • [알고리즘] 그래프와 트리, 전위순회, 중위순회, 후위순회& 백준(트리 순회) 그래프 그래프는 현상이나 사물을 정점(Vertex) 또는 노드(Node), 간선(Edge)으로 표현하기 위해 사용한다. - 노드(Node) : 위치를 말함, 정점(Vertex)라고도 함 - 간선(Edge) : 위치 간의 관계를 표시한 선으로 노드를 연결한 선을 뜻함(Link 또는 Branch라고도 함) - 인접 정점(Adjacent Vertext) : 간선으로 직접 연결된 Vertex(또는 Node) 1) 무방향 그래프(undirected graph) - 방향이 없는 그래프로 간선을 통해 노드는 양방향으로 갈 수 있음 - 보통 노드 A,B가 연결되어 있을 경우 (A,B) 또는 (B,A)로 표기 2) 방향 그래프(directed graph) - 간선에 방향이 있는 그래프로 방향이 가르키는 곳으로만 갈 수 .. 공감수 4 댓글수 1 2022. 10. 8.
  • [알고리즘] 스택 & 백준(탑, PPAP) * Deque을 활용하여 스택을 구현하는게 더 효율적이다. [파이썬/Python] Collections - Deque 들어가며 코딩테스트에 응시할 때 빠르게 찾아볼 수 있도록 따로 정리한 내용입니다. 공부하시기에는 빈약한 내용일 수 있음을 미리 알려드립니다. 공식 문서를 참고할 때에는 대부분의 기업이 mong9data.tistory.com 1. 2493: 탑 문제 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이.. 공감수 7 댓글수 0 2022. 10. 8.
  • [알고리즘] 이분 탐색, 투 포인터 알고리즘 & 백준(두 수의 합, 두 용액) 이분탐색에 문제를 풀다가 두 용액이라는 문제가 나왔고, start, end, mid를 놓고 계속 풀었기 때문에 mid값을 어떻게 설정해야하는지에 대한 어려움이 있었다. 두 용액 문제의 알고리즘 분류를 보니 두 포인터(- 투 포인터)가 있어서 이를 활용해야함을 알았다. 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 투 포인터 알고리즘이란? 포인터가 C언어에서의 포인터가 아니다. 정말 말그대로 가리키는 두 개의 포인터라고 생각하면 된다. 이름처럼 양 끝을 각각 포인터로 설정한 다음, 포인터의 위치를 안쪽으로 옮기며 주어진 연산을 반복해 최적값을 찾아내는 방식이다. 투포인터 알고리즘의 장점은 리스.. 공감수 3 댓글수 1 2022. 10. 6.
  • [알고리즘] 이분 탐색, 매개 변수 탐색 & 백준(랜선 자르기, 나무 자르기, 공유기 설치, 히오스 프로게이머) 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 매개 변수 탐색(Parametric Search)란? 이분 탐색과 유사하다. 탐색 범위를 반으로 줄이기 때문에 시간복잡도는 O(logN)이다. 최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다. - 최적화 문제: 어떤 알고리즘의 최적 솔루션을 찾는 것 - 결정 문제: 답이 이미 결정되어 있다고 보고 문제를 푸는 것 이진 탐색과 매개변수 탐색의 차이점 이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다. 따라서, 매개변수 탐색은 어떤 조건을 만족하는 위치 중 .. 공감수 1 댓글수 0 2022. 10. 6.
  • [알고리즘] 분할 정복 & 백준(곱셈, 행렬 제곱) 분할 정복(Divide & Conquer) 분할 정복은 문제를 여러개로 나누어서 푸는 알고리즘이다. 교수님께서 미친듯이 강조해서 "디바이드앤퀀쿼"만 기억이 난다.. * 동적 계획법(DP)과의 차이점 1. 동적 계획법은 분할한 문제들이 서로 영향을 미침. 2. 분할 정복은 분할한 문제들이 서로 영향을 미치지 않음. * 분할 정복의 필요조건 1. 문제를 나눌 수 있어야 한다. 2. 부분 문제의 답을 이용하여 원래 문제의 답을 계산하는 방법이 있어야 한다. * 분할 정복의 알고리즘의 접근법 1. 분할: 문제를 작은 문제로 분할하는 과정 2. 정복: 분할한 작은 문제들을 해결 3. 조합: 작은 문제에 대한 결과를 원본 문제에 대한 결과로 조합한다. 분할 정복을 이용한 거듭제곱 먼저, 거듭제곱이란 주어진 수를 주.. 공감수 3 댓글수 1 2022. 10. 5.
  • [알고리즘] 행렬 곱셈, 행렬 제곱 행렬 제곱의 문제를 풀어야하는데, 행렬 곱셈을 하는 법부터 정확히 알지 못 했기 때문에 정리하는 글이다. 1. 2740: 행렬 곱셈 문제 N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오. => 행렬의 곱셈 공식에 의해서 N*M, M*K 행렬을 곱하면 N*K 행렬이 된다. 오른쪽 사진에 의하면, 3 x 2 행렬과 2 x 3 행렬이다. 3 x 2 행렬과 2 x 3 행렬을 곱하면 3 x 3 행렬이 만들어진다. 두 행렬을 곱하면 위의 왼쪽 사진과 같은 결과가 나온다. 1) N과 K에 대해 이중 for문을 돌면서, 2) 벡터의 크기 M만큼 for 돌면서 행벡터와 열벡터의 각 요소 곱의 더하기 값을 구해주고 3)결과 행렬에(2차원 리스트) 넣어주면 된다. impo.. 공감수 7 댓글수 0 2022. 10. 4.
  • [알고리즘] 우선순위 큐, 힙 & 백준(최대 힙, 최소 힙, 가운데를 말해요, 카드 정렬하기) 우선순위 큐란, 데이터 삽입은 어떤 순서로 해도 상관없지만 데이터를 삭제할 때는 우선순위에 맞춰 더 높은 우선순위를 갖는 데이터를 먼저 삭제하는 큐를 말한다. 우선순위 큐는 힙을 통해 구현할 수 있다. 힙이란 완전 이진트리의 일종으로 대표적으로 최대 힙과 최소 힙이 있다. - 최대 힙: 루트 노드가 가장 큰 값을 가지며, 부모 노드는 항상 자식 노드보다 큰 값을 갖는다. - 최소 힙: 루트 노드가 가장 작은 값을 가지며, 부모 노드는 항상 자식 노드보다 작은 값을 갖는다. 힙에서의 삭제는 항상 루트 노드를 먼저 삭제하며 노드 변동 시 힙의 성질을 만족하도록 힙을 변동시킨다. 이러한 힙의 특징을 이용하여 우선순위 큐를 구현하는 것이다. 사실상 우선순위 큐를 구현하는 것은 힙을 구현하는 것이다. 최대 힙 구.. 공감수 4 댓글수 1 2022. 10. 3.
  • [Programmers] Level1 직사각형 별찍기 https://school.programmers.co.kr/learn/courses/30/lessons/12969 * 문제 설명 프로그래머스 Level1 직사각형 별찍기 표준 입력으로 두 개의 정수 n과 m이 주어짐 별(*) 문자를 이용해 가로의 길이 n, 세로의 길이 m인 직사각형 형태 출력 * 입출력 예 입력) 5 3 출력) ***** ***** ***** * 소스코드1 1. 정수 n과 m을 nextInt()로 입력받는다. 2. 이중 for문을 이용하여 직사각형을 만든다. *주의할 점은 for문에 순서에 따라 직사각형이 달라지기 때문에 순서를 잘 고려하면 됨.* print: 개행 없음/println: 개행 최종 코드) import java.util.Scanner; public class Solutio.. 공감수 0 댓글수 0 2022. 8. 3.
  • [Programmers] Level1 문자열 내 p와 y의 개수 https://school.programmers.co.kr/learn/courses/30/lessons/12916 * 문제 설명 프로그래머스 Level1 문자열 내 p와 y의 개수 대문자, 소문자가 섞여있는 문자열 s s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return하는 solution 완성하시오. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴 단, 개수를 비교할 때는 대문자와 소문자를 구별하지 않음 * 입출력 예 s answer pPoooyY true Pyy false * 소스코드1 1. 문자열의 길이만큼 연산 str.length() for문을 사용해서 문자열을 길이만큼 연산하도록 한다.for(int i=0; i 공감수 0 댓글수 0 2022. 8. 2.
  • [Programmers] Level1 자릿수 더하기 https://school.programmers.co.kr/learn/courses/30/lessons/12931 * 문제 설명 프로그래머스 Level1 자릿수 더하기 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return하는 solution 함수를 만들라 예를 들어 N = 123이면 1+2+3=6 을 return 하면 된다. * 입출력 예 N answer 123 6 987 24 * 소스코드1 1. 숫자를 쪼개기 힘들기 때문에 문자열로 변환 숫자를 문자로 변환은 생각보다 간단하다........! new String으로 선언한 후, 파라미터로 입력받은 n과 텅 빈 값("")을 붙이면(+) 된다. (long n = 12345 이었으면, String str = 12345; 문자열이 된다.) 2. 문.. 공감수 0 댓글수 0 2022. 8. 2.
  • [Programmers] Level1 자연수 뒤집어 배열로 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12932 * 문제 설명 프로그래머스 Level1 자연수 뒤집어 배열로 만들기 자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴 예를 들어, n이 12345이면 [5, 4, 3, 2, 1]을 리턴 * 접근 포인트 1) 자연수 n의 자릿수에 구애받지 않고 성립해야 한다. - 제한 조건 n은 10,000,000,000이하인 자연수입니다. 2) 숫자열을 배열로 쪼개야 한다. 3) 숫자열의 순서를 뒤집어야 한다. * 소스코드1 1. 숫자를 쪼개기 힘들기 때문에 문자열로 변환 숫자를 문자로 변환은 생각보다 간단하다........! new String으로 선언한 후, 파라미터로 입력받은 n과 텅.. 공감수 0 댓글수 0 2022. 8. 1.
  • 프로그래머스 Level 1 모음 Level 1 1 신고 결과 받기 2 로또의 최고 순위와 최저 순위 3 신규 아이디 추천 4 숫자 문자열과 영단어 5 키패드 누르기 6 크레인 인형뽑기 게임 7 없는 숫자 더하기 8 음양 더하기 9 내적 10 소수 만들기 11 폰켓몬 12 완주하지 못한 선수 13 K번째 수 14 모의고사 15 체육복 16 실패율 17 약수의 개수와 덧셈 18 3진법 뒤집기 19 예산 20 두 개 뽑아서 더하기 21 2016년(연습문제) 22 최소직사각형 23 나머지가 1이 되는 수 찾기 24 부족한 금액 계산하기 25 [1차] 비밀지도 26 가운데 글자 가져오기(연습문제) 27 [1차] 다트 게임 28 같은 숫자는 싫어 29 나누어 떨어지는 숫자 배열(연습문제) 30 두 정수 사이의 합(연습문제) 31 문자열 내 마음대.. 공감수 0 댓글수 0 2022. 8. 1.
  • [Java Algorithm] 1-4 단어 뒤집기(StringBuilder 이용법 또는 직접 뒤집기) * 문제 설명 N개의 단어가 주어지면 각 단어를 뒤집어 출력하는 문제 입력: 첫 줄에 자연수 N(3 공감수 0 댓글수 0 2022. 7. 27.
  • [알고리즘] 큐(Queue) 정리 & 문제 풀이(Python) 큐 : 자료구조 중 하나로, 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조이다. - 큐는 한쪽 끝에서는 삽입 연산만 이루어지며 다른 한쪽 끝에서는 삭제 연산만 이루어지는 유한 순서 리스트이다. - 구조상으로 큐가 스택과 다른 점은 스택에서는 삽입과 삭제가 같은 쪽에서 일어나지만 큐에서는 다른 쪽에서 일어난다. 큐의 연산 큐의 포인터 - front: 큐의 첫 번째 원소를 가리키는 포인터 - rear: 큐의 마지막 원소를 가리키는 포인터 - push(): 큐에 값을 넣는 연산 (Enqueue) rear 위치에 자료를 추가하고 rear를 1 증가시킴 - pop(): 큐에서 자료를 빼는 연산 (Dequeue) front 위치에 자료를 제거하고 front를 1 증가시킴 - fro.. 공감수 0 댓글수 0 2022. 2. 7.
  • [알고리즘] 스택(Stack) 정리 & 문제 풀이(Python) 스택 : 자료구조 중 하나로, 먼한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 구조이다. - 파이썬은 스택 자료구조를 제공하지 않는다. 기본 클래스인 list를 통해 스택을 흉내낼 수 있다. 스택의 연산 - push(item): item 하나를 스택의 가장 윗 부분에 추가한다. - pop(): 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다. - peek(): 스택 가장 위에 있는 원소를 반환한다. (삭제하지는 않는다.) - isEmpty(): 스택이 비어있다면 1, 아니면 0을 반환한다. 대표적인 문제 및 사용 - 웹 브라우저 방문기록(뒤로가기) - 실행 취소(undo) - 역순 문자열 만들기 - 수식의 괄호 검사(연산자 우선순위 표현을 위한 괄호검사) -.. 공감수 0 댓글수 0 2022. 1. 31.
  • [운영체제] 메모리 구조 (재귀호출 vs 반복문) 재귀에서 탈출조건(적절하게 빠져나오는 구문?)이 없으면 스택오버플로우가 발생한다. why? 스택에서 뭔 문제가 있겠지!! 스택이 존재하는 메모리 구조를 더 이해해두기 위해 포스팅한다. 메모리 구조 https://blog.naver.com/zzaxowns/222611286857 (참고블로그! 여기 더 자세하게 설명되어있는듯한..) 프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간은 다음과 같다. 코드(Code) 영역 실행할 프로그램의 코드가 저장되는 영역이다. 프로그램이 시작하고 끝날 때까지 메모리에 계속 남아 있는다. 컴파일된 기계어가 들어가게 된다. CPU는 코드 영역에 저장된 명령어를 하나씩 가져가서 처리한다. 데이터(Data) 영역 프로그램의 전역 변수와 정적 변수, 문자열 상수가 저장되는 영.. 공감수 0 댓글수 0 2022. 1. 26.
  • [알고리즘] 재귀함수(Recursive function) 정리 & 문제 풀이(Python) 재귀함수 : 함수 안에서 자신의 함수를 다시 호출하는 방식 - 재귀, 즉 자기호출은 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 접근하는 방식이다. 재귀함수의 장점 - 반복문을 대신해서 재귀함수로 사용하게 되면 보다 간결한 코드 작성이 가능해진다. 재귀함수의 단점 - 연산이 느리다.(많은 연산을 필요로 한다는 얘기) - 재귀함수의 단점으로 인해 현재 실무에서는 거의 사용하지 않는다고 함. - 재귀함수 단점 보안으로 동적프로그래밍 사용 def recursive(): print("재귀함수") recursive() recursive() # 함수 호출 재귀함수를 사용할 때 가장 중요하게 봐야하는 것은 "탈출조건"이다. 위 코드와 같이 탈출조건.. 공감수 0 댓글수 0 2022. 1. 13.
  • [Java Algorithm] 1-3 문장 속 단어( for each문, split(), indexOf(), substring()) * 문제 설명 문장 속의 각 단어는 공백으로 구분되고 한 개의 문장이 주어지면 그 문장 속에서 가장 긴 단어를 출력하는 문제 (출력: 첫 줄에 가장 긴 단어를 출력하고 가장 길이가 긴 단어가 여러개일 경우 문장속에서 가장 앞쪽에 위치한 단어를 답으로 함.) 예시 입력 1 it is time to study 예시 출력 1 study * 소스코드1 풀기 전 생각) 공백을 기준으로 나누면 되지 않을까? => split() 먼가 생각으로는 처음 나온 공백을 기준으로 앞 글자들을 묶고 공백이 나올 때마다 반복한 다음 그 묶여진 단어들을 배열에 넣어서 비교하면 되지 않을까? 싶음 => String[] arr = str.split(" "); 1. 공백으로 구분된 단어들을 입력받고 2. 해당 단어를 " "으로 spli.. 공감수 0 댓글수 0 2021. 8. 16.
  • [Java Algorithm] 1-2 대소문자 변환(대문자는 소문자로, 소문자는 대문자로) // 대문자와 소문자가 같이 존재하는 문자열을 입력받아 // 대문자는 소문자로, 소문자는 대문자로 변환하는 프로그램 // 첫 줄에 문자열이 입력된다. 문자열 길이 100 안 넘음 import java.util.*; public class Practice_02 { public String solution(String str) { String answer = ""; for(char x : str.toCharArray()) { if(Character.isLowerCase(x)) answer+=Character.toUpperCase(x); else answer+=Character.toLowerCase(x); } return answer; } public static void main(String[] args) .. 공감수 0 댓글수 0 2021. 8. 15.
  • [Java Algorithm] 1-1 문자 찾기(자바 한 문자만 입력 받기, 대소문자 변환) * 문제 설명 한 개의 문자열을 입력받고, 특정 문자를 입력받은 후 해당 특정문자가 대소문자에 관계없이 문자열에 몇 개 존재하는지 알아내어 출력해주는 문제 * 소스코드 package algorithm; import java.util.Scanner; public class Main { public int solution(String str, char t) { int answer = 0; str = str.toUpperCase(); //string이 대문자로 된다.! t = Character.toUpperCase(t); // t는 문자이기 때문에 Character라는 클래스에서 클래스에 있는 메서드 사용한다. for(int i = 0; i < str.length(); i++) { if(str.charAt(i.. 공감수 0 댓글수 0 2021. 8. 14.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.