본문 바로가기

전체 글

 (150)
[알고리즘]BFS(너비우선탐색)/DFS(깊이우선탐색)에 대한 개념과 예시 안녕하세요. 진또배기 입니다. 오늘은 코딩테스트에서 많이 쓰이는 BFS와 DFS알고리즘에 대해 알아보겠습니다. 코딩테스트에서 Level3의 난이도로 어려운 개념이니 쉽게 풀어서 잘 설명드리겠습니다. 0. 탐색 시작하기에 앞서 그래프를 탐색하는 방법에는 BFS,DFS 방법이 있습니다. 여기서, 그래프란 노드(거점)과 노드를 연결하는 간선(edge)로 이루어진 자료구조를 말합니다. 그래프는 트리라는 자료구조와 자주 비교되는데요. 이 둘간의 비교는 다음 포스팅에 업로드하도록 하겠습니다. 1. BFS(Breadth-First-Serch) 1) 개념 BFS를 직역하면 너비우선탐색입니다. 탐색을 하는 과정에서 현재 분기에서 최대한 넓게 각 노드를 탐색하고 현재 분기의 탐색을 마쳤다면, 다음 분기로 넘어가 다시 최대..
[프로그래머스](파이썬)FloodFill-Level3-BFS알고리즘 사용 안녕하세요. 그러면 시작하겠습니다...!!입니다. 오늘은 프로그래머스의 FloodFill문제를 풀어보는 시간을 가져보겠습니다. 이 문제는 전형적인 BFS알고리즘을 사용하는 문제로, Level3에 해당하는 어려운 문제입니다. 하지만 아주 많이 응용되는 문제이니 슈도코드를 토대로 잘 따라오시면 되겠습니다. 그러면 시작하겠습니다! 1. 문제소개 2. 슈도코드 목표: 각 좌표를 하나하나 탐색하면서 효율적인 방법을 고안하자. 0. 좌표를 방문했는지 안했는지 체크리스트 생성-->2차원 배열로 체크해줄거임. -방문했으면 2차원 배열의 원소가 True, 방문안했으면 2차원 배열의 원소가 False. -큐를 이용한 bfs기법 1. (0,0)=> 처음보는 좌표이므로 큐에 넣음 -queue[(0,0)] 2-a. 큐에서 원소..
[자료구조]큐(Queue)에 대한 모든 것-개념,사용예시, 파이썬 내장 함수 안녕하세요. 진또배기 입니다. 오늘은 저번 스택 자료구조에 이어서 큐에 대해 알아보겠습니다. 저번에 설명한 스택 개념과 이번에 설명드릴 큐 개념을 동시에 가져가시는 것을 추천드립니다. 1. 큐(Queue)란? 큐는 '밑빠진 독에 물붓기'와 같습니다. 밑빠진 독에 물을 붓는 것처럼 가장 먼저 들어간 물이 가장 먼저 나오는 것입니다. 즉, 가장 먼저 들어간 데이터가 가장 먼저 처리되는 자료구조입니다. 이 규칙을 FIFO 규칙으로 불리며 First-in First-out의 줄임말입니다. 이를 그림으로 표현하면 이와 같은데요. 큐를 다른 말로 하면 가장 나중에 들어간 데이터가 가장 나중에 처리되는 자료구조입니다. Queue를 영어로 직역하면 '열'이라는 뜻인데 왜 이 뜻인지는 이제 이해하시겠죠? 2. 큐 사용예..
[OS]교착상태에 대한 모든 것-개념, 조건, 해결 방법 안녕하세요. 진또배기입니다. 오늘은 저번 포스팅에 이어서 교착상태에 대해 알아보도록 하겠습니다. 저번 포스팅에 교착상태에 대한 재미있는 이야기를 담았으니 궁금한 분은 방문해주세요! 0. 교착상태에 대한 재미있는 이야기 링크: 410leehs.tistory.com/11 교착상태에 대한 재미있는 이야기(Feat. 마지노선) 안녕하세요. IT린이입니다. 오늘은 운영체제에서 볼 수 있는 교착상태에 대해 지루하지 않게 재미있는 썰을 준비해보았습니다. 교착상태에 대한 개념과 조건 해결방법은 다음에 포스팅하도록 410leehs.tistory.com 1. 교착상태란? IT세계에서의 교착상태란 다중프로그래밍 구조에서 두 개 이상의 프로세스(일을 수행하는 동작 단위)가 하나의 자원을 차지하기 위해 무한정 대기하는 상태입니..
[프로그래머스](파이썬)-게임아이템-Level3-힙(heap)사용 문제 안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 게임아이템 문제를 풀어보겠습니다. 이 문제는 사실 그냥 List로도 풀 수 있는 문제입니다. 하지만 List를 사용하면 시간복잡도가 증가해 비효율적인 알고리즘입니다. 따라서 제목에 나타낸 것처럼 heap이라는 자료구조를 사용해야 되는데요. 이러한 문제는 응시자가 효율성에 대한 개념이 있는 지 확인하는 문제입니다. 따라서 효율성을 검증하는 문제를 통해 여러분이 기존 방법대로 풀지 않는, 창의적인 지원자라는 것을 어필합시다! 그러면 시작하겠습니다. 1. 문제소개 2. 슈도코드 제가 처음 시도한 방식: 모든 캐릭터의 체력을 리스트에 담고, 배정가능한 아이템을 모두 찾은 후, 모든 배정 가능한 경우의 수를 리스트에 담은 뒤, 가장 높은 공격력을 뽑는다. 즉, 1..
DB 면접준비-기초(Oracle, Mysql) 보호되어 있는 글입니다.
프로그래밍 대답준비-심화편 안녕하세요. 진또배기입니다. 오늘은 저번에 이어서 50초의 프로그래밍 대답준비 심화편입니다. 기본편은 못보고 오신 분들을 위해 링크를 올려둘테니 이번 개념이 너무 어렵다하신분들은 기본편을 방문해주세요. 0. 프로그래밍 대답준비-기본편 410leehs.tistory.com/7?category=855622 Java 개발자 면접 준비-기본편 안녕하세요. IT린이입니다. 오늘은 Java 개발자 면접 준비 기본 답변에 대해 준비하는 시간을 가지겠습니다. 질문 한 가지가 나오면 그와 관계되어 있는 꼬리질문까지 준비해 여러분의 시각을 넓 410leehs.tistory.com 1. jdbc가 무엇인가요? 자바에서 데이터베이스를 접속할 수 있도록 해주는 자바 API입니다. JDBC는데이터베이스에서 자료를 쿼리하거나 업데..
[프로그래머스](파이썬)-이중 우선순위큐-Level2.5-힙,큐 문제 안녕하세요. 진또배기입니다. 오늘은 프로그래머스의 이중 우선순위큐 문제를 풀어보도록 하겠습니다. 음 제 생각에는 이런 문제는 복잡한 알고리즘은 쓰이지 않지만 다양한 스킬들과 2가지의 자료구조가 쓰이기때문에 2.5레벨의 문제라고 생각합니다. 이 정도 난이도의 문제는 현재 한국 대기업에서 가장 어려운 코딩테스트 문제에요. 물론 Level4, Level5의 문제도 있지만 거기까지는 나오지 않는 것 같습니다. (네이버, 카카오, 구글, AWS 등 자체 IT서비스 기업제외-여긴 더 어려운 문제나옴..ㅋㅋ) 그러면 시작하겠습니다! 1. 문제 소개 문제 설명 급한 일을 먼저 처리해주는 서버가 있습니다. 이 서버에 3초에 한 번씩 요청이 들어온다고 할 때, 서버가 각 요청을 처리하는 순서를 알아보려 합니다. 요청은 [..
[프로그래머스]-(파이썬)더맵게-Level2 보호되어 있는 글입니다.
교착상태에 대한 재미있는 이야기(Feat. 마지노선) 안녕하세요. 진또배기입니다. 오늘은 운영체제에서 볼 수 있는 교착상태에 대해 지루하지 않게 재미있는 썰을 준비해보았습니다. 교착상태에 대한 개념과 조건 해결방법은 다음에 포스팅하도록 하겠습니다. 0. 교착상태에 대한 SSUL (+마지노선 기원까지) 교착상태는 PC용어로 많이 쓰이지만 정치적, 군사적, 경제적용어이기도 합니다. 제가 좀 아재같지만 사실 세계사에 관심이 많습니다..ㅎㅎ 그래서 세계사 책을 읽다가 교착상태라는 용어가 만들어진 역사를 알 수 있었습니다. 교착상태 용어의 기원은 제 세계 1차대전으로 내려갑니다. 세계 1차대전은 1914년부터 1918년까지 유럽을 중심으로 한 전쟁인데요. 1914년 9월 마른전투에서 프랑스 서부지역인 서부전선을 사이에 두고 영국군+프랑스군과 독일군이 대치해 참호전을..
[프로그래머스](파이썬)나머지한점-Level2-2가지 방법 문제풀이 안녕하세요.진또배기입니다. 오늘은 프로그래머스에 올라와있는 '나머지 한점'문제를 파이썬을 사용해 2가지 방법으로 풀이를 해보겠습니다. 한 가지는 해시를 이용한 방법, 다른 한 가지는 Counter를 이용한 방법입니다. 1. 문제 소개 문제 설명 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 라이트닝 볼트 → 스파크 → 썬더일때, 썬더를 배우려면 먼저 스파크를 배워야 하고, 스파크를 배우려면 먼저 라이트닝 볼트를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 라이트닝 볼트 → 힐링 → 스파크 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 힐링 → 썬더 → 스파크와 같은 ..
[프로그래머스](파이썬)스킬트리2-Level3-큐(Queue), 해시(dict)사용 안녕하세요. 진또배기입니다. 오늘은 파이썬을 사용해 프로그래머스에 올라와있는 '스킬트리2'문제를 이전에 포스팅한 것과 다른 방법으로 풀어보도록 하겠습니다. 1. 문제 소개 문제 링크: programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 2. 슈도코드 스킬의 습득 순서를 저장할 필요가 있을 것 같아 enumerate() 함수를 이용해 인덱스와 스킬 페어로 저장했습니다. 이후 skill_tree의 각 skill에 대해 순회하며 인덱스를 비교하도록 구현했습니다 시간복잡도: 선행스킬 순서 배열(skills_order)의 길이 n과 스킬트리 배열(skill_tree)의 길이 m에 대해 O(n+m) 3. 문제풀이

티스토리툴바