🏄 Deep Dive

CT 부셔보기 이번 문제도 SSAFY를 준비하며 추천 받은 문제여서 풀게 되었다. 해당 문제는 비트 연산을 응용해 해결해야 하는 문제인데, 지금까지 비트 연산이라는 말을 들어만 봤지 정확히 무엇인지 공부하지 못했다. 비트 연산은 조건문을 사용하면서 비교 연산자로 사용하던 & 나 | 등을 활용해 비트(bit, 2진수로 이루어진 데이터 단위)를 연산하는 것을 의미한다. 먼저 비트 연산에 대해 공부하고 백준 문제로 넘어가도록 하자! 비트 연산 코딩교육 티씨피스쿨 4차산업혁명, 코딩교육, 소프트웨어교육, 코딩기초, SW코딩, 기초코딩부터 자바 파이썬 등 tcpschool.com 처음 독학을 하며 비교 연산자에 대해 공부할 때 단순히 조건을 검사하는 용도로만 생각했다. 하지만 비교 연산자는 생전 듣지도 보지도 못..

Queue Queue는 자료구조 중 하나로, FIFO(First In First Out, 선입선출) 구조를 가지는 자료구조이다. 먼저 들어온 데이터가 먼저 나가는 구조를 뜻하며, 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 사용한다. 대표적인 예로 너비 우선 탐색(BFS)에서 주로 사용한다. 요세푸스 순열 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net SSAFY를 준비하며 오픈카톡방에서 이런 저런 정보를 공유하던 중 CT를 대비하기 위해 요세푸스 순열을 공부하면 좋을 것 같다는 이야기를 들어 접하게 되었다. 해당 문제는 N명의 인원수(배열의 길이)와 순서대로 M 번째에 제거할 정수..

숫자 카드 2 - 백준 10816 나를 미치게 만든 문제 수많은 런타임 에러, 시간 초과, 메모리 초과를 겪으면서 미쳐버리는 줄 알았다. 이진 탐색으로 풀어보기 package 심성헌.알고리즘_5주차.백준; import java.io.*; import java.util.*; public class 숫자카드2_10816_binary { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static StringBuffer sb = new StringBuffer(); st..

순차 탐색 / 이진 탐색 순차 탐색 배열 안에 있는 특정 데이터를 찾기 위해 앞으로 데이터를 하나씩 차례대로 확인하는 방법이다. 정렬되지 않은 배열에서 특정 데이터를 찾고자 할 때 사용한다. 데이터가 아무리 많아도 시간이 충분하다면 항상 원하는 데이터를 찾을 수 있다는 장점이 있다. 제일 처음 인덱스부터 순차적으로 탐색하기 때문에 시간 복잡도는 **O(N)** 이다. (N = 배열의 길이) (뭔가 버블 정렬과 비슷한 알고리즘 같다.) 이진 탐색 배열이 정렬되어 있다는 전제 하에 사용할 수 있는 알고리즘이다. 시작점과 끝점을 이용해 중간점을 찾고, 찾고자 하는 데이터와 중간점의 데이터가 맞을 때 까지 반복한다. 즉, 재귀 함수 또는 반복문을 통해 구현할 수 있다. 탐색 범위를 절반씩 줄여 나가기 때문에 빠..

그래프, DFS, BFS 복습하기 4-1) Graph, DFS, BFS 탐색 알고리즘 www.notion.so 얼음과 미로 그 사이 어딘가 처음 문제를 접했을 때, 인접 행렬로 만들어진 테이블을 보고 "BFS로 풀어야 하나?" 라고 생각했다. 그래서 구조는 기억이 나지 않지만 BFS(너비 우선 탐색)이 재귀나 Stack 자료 구조를 사용하지 않고, Queue 자료 구조를 이용하는 것을 바탕으로 공부 했던 내용을 톺아보며 코드를 작성했다. 도전! BFS! package 심성헌.알고리즘_5주차; import java.io.*; import java.util.*; public class 단지번호붙이기_BFS { static BufferedReader br = new BufferedReader(new Input..

이해하지 못하는 내가 너무 답답하다! SSAFY 준비를 위해 CT(Computer Thinking) 문제를 연습하던 중 카드 뒤집기 문제를 만났다. 더보기 카드 뒤집기 N개의 카드가 앞면은 1 뒷면은 0 으로 주어진다. 1번의 '찬스' 를 사용하여 i번째, i-1번째, i+1번째 카드를 동시에 뒤집는다.(1번의 찬스로 인접한 카드까지 뒤집는다.) 카드의 앞,뒷 면 정보가 0과 1 로 주어질 때 모두 뒷면으로 만드는 최소 찬스 개수를 구하여라. 예시) 0 0 1 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 예시답) 3 회 예시풀이) 1회> 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 2회> 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 3..

탐색 알고리즘 이번 주는 탐색 알고리즘의 대표적인 두 가지 DFS와 BFS에 공부할 예정이다. 먼저 탐색 알고리즘은 트리 구조로 만들어진 그래프의 노드 그리고 노드와 노드 사이에 연결된 간선의 상태를 파악하기 위해 사용된다. 먼저, 그래프를 데이터로 구현하기 위해서는 먼저 테이블에 대한 이해가 있어야 하며, 이는 인접 행렬 또는 인접 리스트를 이용해서 구현할 수 있다. Graph [자료구조] 그래프(Graph)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 인접 행렬 인접 행렬이란 그래프의 연결 관계를 2차원 배열로 표현하는 방식을 말한다. 즉, 노드의 개수는 이미 정해져 있으니 각 노드(x축 index 번호)와..

재귀 함수 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 즉, 어떤 함수를 호출하면 그 안에 어떤 함수를 또 호출하여 반복한다는 뜻이다. 쉽게 이해하려면 엘리베이터 거울을 생각하면 좋을 것 같다! (내가 이걸로 이해했다.🥶) 처음에는 굉장히 생소한 이름이었지만 Node.js를 공부하며 콜백 지옥 이라는 내용을 접했는데, 여기서 콜백 이 재귀 함수의 개념을 포함하고 있다고 한다.(맞을거다..ㅎ) 사이버다임 면접을 준비하면서 재귀 함수에 대한 문제가 나온다는 이야기를 들었고, 이를 공부하기 위해서 하노이의 탑 문제를 풀어 봤는데 손으로 직접 그려 보기 전까지는 전혀 이해하지 못했다. 근데 한번 손으로 그려 보니까 완벽하지 않지만 대략적으로 재귀에 대한 틀이 잡힌 것 같다. (정작 사이버다임..

그리디 알고리즘 그리디 알고리즘은 최적해를 구하는 데에 주로 사용하며, 동적 프로그래밍과 함께 사용하여 효율을 올린다고 알려져있다. 또한, 그리디 알고리즘은 여러 경우 중 하나를 결정해야 할 때 그 순간의 최적의 선택을 컴퓨터에게 하도록 만드는 것을 의미하는데, 그리디 알고리즘이 최적해를 보장 해주지 않지만 결과까지 도달하는 시간이 굉장히 단축된다는 장점이 있다. 위의 트리 구조에서 가장 최적의 해는 7 → 100 → 107의 경로가 가장 최적의 해로 도달할 수 있는 경우이다. 하지만 그리디 알고리즘은 7 보다 큰 13을, 5 보다 큰 11을 선택한다. 즉, 현재 위치에서 가장 최선의 선택을 하기 때문에 최적해를 보장 해주지 않는 다는 뜻이다. 가장 간단한 예시는 거슬러 줘야 할 최소한의 동전 개수가 몇..

완전 탐색 코딩 테스트를 볼 때 가장 기초적인 그리고 가장 출제 빈도가 높은 알고리즘이 그리디와 완전 탐색 알고리즘이라고 한다. 그래서 이번 주차 문제도 그리디, 완전 탐색 그리고 재귀 알고리즘에 대한 문제를 공지했다. 그렇다면 도대체 완전 탐색 알고리즘은 뭘까? 완전탐색 '모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘' 을 뜻한다. 영어로는 Exhaustive Search 라고 한다. 가능한 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 가장 강력하고 확실한 방법이지� velog.io (위 블로그에서 아주 자세히 설명하고 있다.) 위 글에서 완전 탐색 기법의 종류로 Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법 비트 마스크 : 이진수 표현을 자료구조로 쓰..