알고리즘 공부

정글 5일차 알고리즘 주차가 시작되었다.문제 자체는 어렵지 않지만 사소한 문제가 있었다.올림 처리를 하기 위해 제곱근에 0.5를 더해 주었는데 제곱근이 정수인 경우에 올림이 되는 경우도 있고 내림이 되는 경우도 있었다.파이썬 등 여러 언어에서는 반올림 방식으로 Bank

오늘 배운 것들 1. 시간 복잡도 1-1. 빅오 표기법 시간복잡도를 이야기하기 전 점근 표기법으로서의 빅오 표기법을 다루는 것이 좋을 것 같다. 점근 표기법은 함수의 증가율이 어떤 형태를 띄는지를 표기하는 방식이다. 컴퓨터과학에서 특히 자주 사용되는 빅오 표기법은 >

오늘 배운 것들 1. 완전탐색 알고리즘 완전탐색(Exhaustive Search)은 말 그대로 모든 경우의 수를 시도하는 알고리즘이다. 해당되는 방법으론: 모든 순열을 테스트 해보는 방법(순서를 알아야 하는 문제일 때) 비트마스크를 이용(flag를 써야할 때. 파이썬에

일주일이 지났다. 학습속도가 점점 느려진다. 지금까지 단 한 문제를 풀었다. 중요한 배움이 있었지만 쓴 시간이 너무 많다. 오늘 배운 것 1. 완전탐색 1-1. 안전 영역(백준 2468) 간단할 것으로 예상해 호기롭게 도전.

오늘은 더 힘내보려고 한다. 오늘 배운 것들 1. 분할 정복 >큰 문제들을 작은 문제들로 분할하여 해결하는 방식 내지는 알고리즘 '작은' 문제란 쉽게 판단할 수 있을 정도인 경우를 말한다. 앞서 배웠던 하노이 탑 문제도 (n-1층의 탑을 옮기는 방법)+(1개의 판을

모호함을 그대로 마주하는 것이 인간이다.사람은 언젠가 죽는다.선택하고 책임져라.모든 삶을 살 수는 없다.(나를 아는 것이 중요하다.)

1\. 그래프와 트리

양의 가중치를 갖는 그래프에서 출발 노드로부터 최단거리를 찾는 알고리즘.임의의 노드까지의 최단거리만 찾으면 되는 경우라면 중간에 정지하도록 구성할 수도 있다.0\. 각 노드로의 최단 거리를 저장할 리스트(최단거리리스트)를 만들고 INF로 초기화한다.1\. 출발 노드가

최초에 내가 작성한 코드이다.bfs로 큐에서 노드를 하나씩 빼내며 방문한다.너무 느려서 gpt에 개선을 부탁해봤다.변경된 bfs만 살펴보면all_vertexes가 사라졌다.비연결 그래프인 경우에도 모든 정점을 탐색하기 위해서 나는 모든 정점을 가진 집합 all_vert

고슴도치와 물이 동시에 퍼져야 하는, 그냥 재미없는 bfs가 더블인 문제.12행에 이미 물이 있는 경우에는 다음 확인할 리스트에 넣지 말아야 했는데 그걸 빼먹어서 메모리 초과가 계속 떴었다.

시간 복잡도는 O(ElogE)하나의 정점에서 모든 정점으로 가는 최단거리를 구함.우선순위 큐 사용시작 노드 결정 0으로 초기화 후 우선순위 큐에 담음나머지 노드 무한대로 초기화우선순위 큐에서 pop한 후 그 노드에서 갈 수 있는 노드를 확인더 빠르다면 갱신하고 우선순위

어디로 가고 있는지 모르고 있다면, 결국 가고 싶지 않은 곳으로 간다.\-요기 베라어디로 가야 할지 모른다면커리어 방향은 한 번 결정하고 나서 내달리기만 하면 되는 것이 아니다.지속적으로 재평가하고 목표를 다시 세워야 한다.어디로 가고 싶은지 확신할 수 없을 때에는,

x86-64에 기초해 어셈블리어를 배우고, 이것이 컴퓨터를 어떻게 조작하는지를 배운다.어셈블리어는 ATT표기법을 따른다.32비트 아키텍처까지 이어오던 인텔의 x86구조를 따라 만들던 AMD가 64비트 전환에서는 치고 나왔다는 그런 이야기.고대부터 호환성을 64비트까지

최장 공통 부분 수열(LCS)를 구하는 문제수열 $X=(x0, x_1, ... , x_n), Y=(y_0, y_1, ... , y_m)$의 LCS($LCS{XY}$)를 구한다고 하자.부분 수열 $X{n-1}=(x_0, x_1, ... , x{n-1})$이라고 하면1\.

오늘 배운 것들 1. 동적계획법(다이나믹 프로그래밍, DP) 복잡한 문제를 단순한 작은 문제로 나누어 해결하는 알고리즘 설계 기법 이 때 작은 문제들을 중복 계산하는 것을 피하는 것이 핵심이다. '기억하며 풀기' 1-1. 사용 조건 Optimal Substructure

스택(stack)은 프로시저 호출 시 지역변수와 매개변수를 저장하기 위한 메모리 공간후입선출(Last In First Out)구조용도: 함수의 로컬 변수 저장: 호출된 각 함수의 로컬 변수들이 스택에 저장 함수의 제어 흐름 관리: 함수가 다른 함수를 호출할 때, 반

# 문제풀이 동기의 문제 풀이 발표 중 김현수 코치님의 피드백: 면접에서 왜 그렇게 접근했는지 설명할 수 있어야 한다. 예: dp를 적용하게 된 이유, dp 적용 조건, 코드 구조 # 오늘 배운 것들 ## 1. 동적 프로그래밍(계속)

매일 문제 풀이 1. 빗물(백준 14719) 벽의 모양이 주어지면 담길 수 있는 빗물의 칸 수를 출력하는 문제. 2차원 정보로 주어졌다면 아래에서 부터 행마다 둘러싸인 칸 수만을 더하면 된다. 하지만 문제는 특이하게 벽의 정보가 2차원으로 주어지지 않고 왼쪽부터 벽의

매일 문제 풀이 1. 웜홀(백준 1865번) 주어진 그래프에서 비용이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력하는 문제. 비용이 줄어든다는 것은 결국 음수 비용이라는 말이고, 출발 위치로 돌아오는 것이 가능하다는 것은 그 경로를 반

완전탐색

숫자가 적힌 카드로 게임을 한다.번갈아 가며 카드를 내는데 상대가 내는 카드보다 큰 카드를 내야하며, 낼 수 있는 카드 중에 가장 작은 카드를 내는 전략을 사용한다.내가 가진 카드의 종류와 상대가 내는 카드의 순서가 입력으로 주어질 때내는 카드의 순서를 출력한다.한 번