본문 바로가기

분류 전체보기1067

BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS (2022-08-27 업데이트) 2022-07-21 업데이트 : 글 맨 아래에 '풀어보기'로 풀어볼만한 문제 링크 추가 2022-08-27 업데이트 : '풀어보기' 좀 더 추가, 목차 추가 목차 BFS (Breadth-first Search) 명확히 검증하면서 쓴게 아니라서 틀린 부분 있으면 알려주세요! - BFS와 DFS 대충 곰처럼 생긴 섬이 바다에 떠 있다. 편의상 이 섬을 20등분해서 격자 형태로 구역을 나누었다. 이제 우측상단의 귀(곰 입장에서 왼쪽귀)부터 출발해서 섬 전체를 둘러보려 한다. 둘러보는 방법은 여러가지가 있을 수 있다. 빨간 숫자는 둘러본 순서를 뜻한다. (0 부터 19까지) A처럼 자신과 가까운 곳부터 순서대로 살펴볼수도 있다. 격자형태로 나누었으므로 Manhattan Distance (Taxicab Geome.. 2021. 9. 24.
백준 2452 자바 - 그리드 게임 (BOJ 2452 Java) https://www.acmicpc.net/problem/2452 어려웠음.. 2일이나 걸렸음.. 기본적인 로직은 아래와 같이 잡음 1. 각 구간은 어차피 동시에 움직이므로 동일 색상으로 된 구간 전체를 하나로 생각함 2. 그러면 배열 전체에 대한 bfs에서, 그래프에 대한 bfs로 압축시킬 수 있음. bfs로 생각한 이유는 결국 각 구역별로 색상이 변하는거니 한칸만 잡고 계속 변경한다고 보면 결국 가장 먼 구역까지의 bfs라고 생각했음. 즉, 구역을 나누고 각 구역별로 모든 지역까지 bfs를 때린다음 그 횟수가 가장 적은게 답이라 생각함. 즉, 3 3 1 0 0 1 0 0 0 1 1 이러한 입력에 대해 구간을 나눠서 숫자를 붙임. (이게 필요할꺼라 생각해서 한건데 하고보니 이게 flood fill 인듯.. 2021. 9. 22.
알고리즘 시간복잡도에 대해 목차 Complexity Up & Down 게임을 해봅시다! 1~100까지의 숫자 중 하나를 생각해보겠습니다. 전 96을 생각할껍니다. 이걸 누군가에게 맞춰보라고 하고, up & down으로 대답하겠습니다. "1" ⇒ up "2" ⇒ up "3" ⇒ up .. (92번을 더 한 후) "96" ⇒ 맞았..어.. 이렇게 물어볼사람은 없을껍니다! 다들 자연스럽게 아래와 같이 물어볼꺼에요. "50" ⇒ up "75" ⇒ up "87" ⇒ up "93" ⇒ up "96" ⇒ 맞았어! 이걸 다르게 표현해보겠습니다. 우선 1부터 차례대로 물어본 전자의 경우를 보겠습니다. 1~100까지의 100개를 N개라 표현하겠습니다. 이 경우 만약 생각한 숫자가 100이라면(= 생각한 숫자가 N이라면) 최악의 경우로, 100번 물.. 2021. 9. 22.
CP 입문 추천 (코딩테스트 연습) CP 입문 추천 CP; Competitive Programing '입문'이라고 적었으나, 애초에 대회라는 특성상 입문이라고 하기엔 난이도가 다소 높은 편. 보통 아무런 공부 없이 참여하면 한 문제도 풀기 힘든 경우가 많음. PS를 경쟁적으로 진행하는 것으로, 프로그래밍 대회 혹은 코테를 부르는 용어라고 보면 됨. 예를들어 대회 접수를 사전에 받고, 9월 16일 오후 9시에 진행되서 2시간이 주어지고 그 동안 5문제를 푸는 경우. 일반적으로 정해진 시각에 시작해서, 정해진 시간동안 진행되며 Score Board로 서로 경쟁할 수 있도록 해두고 순위가 매겨짐. 방식은 개최하는 대회 혹은 개최하는 곳 마다 다르며, 지원하는 언어도 다르므로 확인하고 참여해야 함. (자바, C++, 파이썬은 보통 다 지원함) 프.. 2021. 9. 22.
PS 입문 추천 (알고리즘 입문 추천) PS 입문 추천 PS; Problem Solving 해외 사이트들도 많지만, 국내에서 유명한 사이트로 그냥 입문하기 좋아보이는 개인 추천 루트 백준(boj) : 국내 사이트 중 가장 많은 문제수를 가지고 있지만, 기존엔 난이도에 따른 분류가 되어있지 않아서 문제를 잘 찾아 풀어야 했음. 현재는 solved.ac 라는 애드온을 유저중 한명이 만들면서 백준 사이트에도 정식적으로 채택되어 집단지성에 의한 난이도 분류가 되고있는 중이라 단점이 사라지고 있는 중. 사실상 국내 사이트 중 PS만 보면 최고라 생각합니다. 프로그래머스 : 요즘 많은 회사에서 코딩테스트 시 프로그래머스를 사용하는곳이 많아요. 사실상 문제 풀어보는 사이트보다는 코딩테스트 플랫폼이라고 볼 수 있음. 문제 자체는 매우 빈약한편이지만, 코테 .. 2021. 9. 22.
PS 란? (알고리즘) Problem Solving 이란? 용어 사용, 용어 해석에 있어 작성자의 개인적인 생각이 포함되어 있습니다. The Feynman Algorithm Write down the problem Think hard Write down the solution Problem Solving(이하 PS)은 '문제 해결'이라는 단어 그대로 주어진 문제를 적절하게 해결 할 수 있는 방법을 찾아 해결하는 것을 뜻합니다. ! 프로그래밍으로 본다면 '원하는 결과를 적정한 시간과 메모리 이내에 처리하는 프로그램을 만드는 것'을 뜻합니다. 여기서 '적정한 시간'은 사람이 문제를 해결하는데 걸리는 시간이 아니라, 해당 프로그램이 입력을 받은 후 결과를 내놓기 전까지 걸린 시간을 의미합니다. 예시 정수 A와 B를 입력받아 A+B를.. 2021. 9. 22.
자료구조 배열 기본 Arrays 따로 증빙자료를 찾지 않고 생각의 흐름대로 작성한 것이라 사실과 다를 수 있음. 수정할 부분 혹은 추가할만한 내용이 있다면 댓글로 남겨주세요. — 0 배열은 물론 데이터를 표현하는 기타 자료구조들이 없다고 가정하자. 서로 연관된 데이터라 해도 이를 프로그램상에 표현하기 위해 취할 방법은 변수를 여러개 만드는 것이다. 오늘의 기온 데이터를 적당히 샘플링해서 시간 순서에 따라 676개로 나눈걸 표현해보자. int a = 10; int b = 13; int c = 11; ... int zz = 21; 676개의 데이터를 표현하긴 했지만, 이해하기 힘든 코드가 될 것이고 쓸데없이 코드길이도 길어질것이고, 변수명 창작의 고통(어제날짜 기온도 표현하려면?)도 따른다. — 1 그럼 생각을 좀 바꿔서 어차.. 2021. 9. 22.

티스토리툴바