Algorithm & Data Structure

[JAVA, 백준] 16947. 서울 지하철 2호선

문제는 아래 링크를 참고해주세요. https://www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 더보기 문제 풀 때 기억하기 술술 풀린 문제보다 술술 풀리지 않은 문제에 집중한다. 문제 풀 때 지키기 1. 30분 타이머를 재고 고민한다. 2. 고민할 때는 주석 혹은 필기를 하며 본인 생각을 정리한다. 3. 30분이 지나고도 아이디어가 떠오르지 않으면 다른 사람 풀이를 찾아본다. 4. 오답노트 적듯이 나의 전개와 다른 점을 찾아서 부..

[Concept/Algorithm] 이분/이진 탐색 (Binary Search)

이분 탐색 알고리즘은 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다. 이분 탐색 알고리즘은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 변수 3개 시작, 끝, 중간 값(start, end, mid)을 사용하여 탐색합니다. 찾으려는 target과 중간 위치 값 mid를 반복 비교하여 원하는 데이터를 찾아가는 과정입니다. 시간복잡도는 단계마다 범위를 절반으로 줄여나가므로 O(logN) 입니다. ex) 32개 데이터-> 16개 데이터-> 8개-> 4개 이분 탐색은 반복문과 재귀 호출 방식으로 구현할 수 있습니다. public classBinary_Search { //재귀 호출 방식으로 구현 private static intbinary_search_recu..

[JAVA] 프로그래머스 - 행렬 테두리 회전하기 LV2

문제는 아래 링크를 통해 확인해주세요. 조건 rows, columns가 주어지면 규칙에 맞게 matrix를 초기화한다. (+1씩 증가하는 규칙! i행 j열의 수는 ((i-1) x columns + j) 이라는 규칙이 있다고 지문에 나와있기도 한다.) rows와 columns는 2 이상 100 이하 queries의 각 행은 [x1, y1, x2, y2]로 이루어지고, 행(회전)의 개수는 1 이상 10,000 이하 x1과 x2는 1 이상 rows 이하, y1과 y2는 1 이상 columns 이하 회전을 한 값들 중 최솟값을 구하여 배열에 담아야 한다. 시계방향으로 회전한다. 회전 시 테두리의 값들만 변화가 있다. 시작위치(왼쪽 위)는 x1, y1이고 끝(오른쪽 아래) 위치는 x2, y2이다. 설계 1. 좌측..

[JAVA] 프로그래머스 - 다트 게임 LV1

문제는 아래 링크를 통해 확인해주세요. https://programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 조건 및 설계 점수 : 0~10 보너스 : S(1), D(2), T(3) 옵션 : 옵션은 존재하지 않을 수도 있다. * : 위치 기준 i와 i-1를 2배 한다. (만약 i=0이라면 i만 2배한다.) *와 * 중첩 : 위와 마찬가지로 진행하면 된다. (결국 i-1의 score는 4배가 된 셈이다.) #와 * 중첩 : i-1에 대해서 -1배가 적용된 값에 그대로 2배를 적용한다. (-2배) # : 위치 기준 i에 -1배 한다.(즉 마이너스) 내 생각 길이 3인 int형 배열 score에 값을 넣어주..

[Concept] 인접행렬과 인접 리스트(LinkedList, ArrayList)

DFS와 BFS 문제를 풀기위해서는 무조건 알고 있어야하는 개념이 그래프입니다. 그리고 그래프를 구현하는 방법으로 인접행렬과 인접리스트가 있습니다. 이번 글에서는 각각의 장단점과 Java로 구현하는 것으로 마무리하겠습니다. (+LinkedList와 ArrayList의 장단점) 그래프 그래프란 요소들이 서로 복잡하게 연결되어 있는 관계를 표현하는 자료구조입니다. 그래프에서 쓰이는 용어는 정점 (vertex) : 노드라고도 하며 데이터가 저장되는 원소 간선 (edge) : 링크라고도 하며 정점 간의 관계 그외에도 인접 정점, 차수, 경로 등의 용어가 있습니다. 그래프 구현 그래프를 구현하는 방법은 배열(Array)을 사용하는 인접 행렬, 리스트를 사용하는 인접 리스트가 있습니다. 그리고 인접 리스트를 구현하..

[JAVA] 프로그래머스 - 전화번호 목록 LV2

문제 이해 및 제한 사항 프로그래머스의 해시 문제, 전화번호 목록 LV2 https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. 매개변수로 주어지는 전화번호 목록에서 어떤 번호가 다른 번호의 접두사인 경우가 1개라도 있으면 false를, 그렇지 않다면 t..