본문 바로가기

자료구조+알고리즘

[1260][java][백준]DFS와BFS 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 풀이 테스트 케이스 대로 숫자를 입력받으면 어떤 그래프가 나오는지 보겠습니다. 테스트 케이스 상으로는 노드 1 부터 시작하게 됩니다. DFS: 1 - 2 - 4 - 3 BFS: 1 - 2 - 3 - 4 * 간선들의 연결이 되어 있는지 혹은 되지 않았는 것을 판단하는 것이 인접행렬을 이용하거나, 혹은 인접리스트를 이용하는 것이 좋습니다. 1) 인접 행렬 1번 꼭지점이 n번 꼭지점과 연결이 되어 있으면 1로 처리, 연결이 되어있지 않은 선은 0으로 처리 단점> 꼭지점의 갯수(Vertex)가 적을 때만 가능하다는 점. 갯수가 많아질수록 탐색 시간이 오래 걸림 2) 인접리스트 자신의 노드에서 갈 수 있는 노드를 가지고 있다고 생각하면 쉽습니.. 더보기
[1175][Python][백준] 단어 공부 알고리즘 분류 구현 문자열 풀이 빈 리스트를 생성하고 개수를 센 수를 리스트에 추가한다 -> 리스트에서 가장 큰 수를 출력 word = input().upper() # 입력받은 문자열에서 중복값을 제거 uniq_word = list(set(word)) cnt_list = [] for i in uniq_word: cnt = word.count(i) cnt_list.append(cnt) if cnt_list.count(max(cnt_list)) > 1: # 숫자 최댓값이 중복되면 print('?') else: # 숫자 최댓값 인덱스(위치)에 위치한 문자열 출력 max_index = cnt_list.index(max(cnt_list)) print(uniq_word[max_index]) 더보기
[10809][Python][백준] 알파벳 찾기 알고리즘 분류 구현 문자열 풀이 예제를 보면 s = b a e k j o o n index = 0 1 2 3 4 5 6 7 a b c ... 순서대로 출력 : 1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 a = 1번째 순서 b = 0번째 순서 c = 없으므로 -1 ... => 알파벳 순서대로 입력받은 문자열의 인덱스 출력!! , 없으면 -1 s = input() alph = 'abcdefghijklmnopqrstuvwxyz' for i in alph: if i in s: #입력 받은 문자열에서 알파벳이 있으면 print(s.index(i), end = ' ') #입력 받은 문자열의 인덱스 출력 else: print(-1 ,.. 더보기
[프로그래머스_level1]JAVA_모의고사 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작.. 더보기
[10798][java][백준] 세로 읽기 알고리즘 분류 구현 문자열 풀이 - 5줄의 문자열을 입력받기 - 문자열을 char 2차원 배열로 하나씩 넣기 - 문자 배열이 '\0' 이라면 넘어가기 * char의 디폴트 값인 '\0'의 값 - 세로부터 출력해야하니 i j 반대로 java코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { Buffe.. 더보기
[11721][java][백준] 열 개씩 끊어 출력하기 알고리즘 분류 구현 문자열 풀이 - next() : 개행문자, 공백은 무시하고 문자를 입력받는다 - nextLint() : 한 줄 단위로 입력받기 때문에 개행문자도 한 줄로 인식한다. 이 문제에선 String 값을 받아오므로 둘 다 가능 - 열개씩 끊어서 한 줄에 하나씩 출력 입력받은 문자열 input 배열은 N개 까지 있다 ( 0부터 N-1까지 증가) 배열번호 i의 값이 10으로 나누었을 때 나머지가 0이고 and i값이 0이 아니면 한 줄 띄운다. java코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import java.util.Scanner; public class Main{ public static void main(String[] args) { Sc.. 더보기
[10808][java][백준] 알파벳 개수 알고리즘 분류 구현 문자열 풀이 - 아스키 코드 활용하면 쉬운 문제 : 아스키코드 97번 = a - 1 : Scanner 2.: StringBuilder StringBuilder 는 String과 문자열을 더할 때 새로운 객체를 생성하는 것이 아니라 기존의 데이터에 더하는 방식을 사용하기 때문에 속도도 빠르며 상대적으로 부하가 적다. - 값은 memory에 append하는 방식으로 클래스를 직접생성하지 않는다. 따라서 긴 문자열을 더하는 상황이 발생할 경우 적극적으로 사용 - StringBuilder 에는 append() 가 있는데 이는 문자열을 더하는 역할을 한다. - 만들어진 문자열을 출력하기 위해서는 StringBuilder의 인스턴스인 sb의 toString() 을 사용 java코드 - Scann.. 더보기
DFS 와 BFS 개념정리 그래프를 탐색하기 위한 대표적인 알고리즘 - DFS , BFS (이해하려면 스택,큐,재귀함수를 알아야한다) 🁢 탐색 Search 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 🁢 자료구조 Data Structure 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 🁢 스택(Stack) 박스 쌓기에 비유 선입후출(First In Last Out) ▒ java ▒ * 자바에서 스택의 최상단 원소를 출력할때 peek() 메서드사용 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import java util.*; public calss Main{ p.. 더보기
[16935][java][백준]배열 돌리기 3 알고리즘 분류 구현 문제 풀이 이번 문제는 실버2임에도 불구하고 쉬운편! 하지만 계산과정이 많아서 귀찮고 머리가 복잡하다.. 1번 연산 : 배열 상하 반전 2번 연산 : 좌우 반전 3번 연산 : 오른쪽 90도 회전 4번 연산 : 왼쪽 90도 회전 5번 연산 : 4그룹 1->2, 2->3, 3->4, 4->1 6번 연산 : 4그룹 1->4, 4->3, 3->2, 2->1 시간이 많이 걸린건 3번 부터.. 3번은 전체적으로 위치를 바꿔주면 되니까 한행이 바뀌는 위치를 보고 위치조정 해주면 된다 5번부터 한 배열을 4부분으로 나눠서 위치를 바꿔주는데 한행을 두개로 나누면 0열~m/2열 , m/2열~m열로 시작점과 끝점을 달리해서 위치를 바꿔준다 ! 하지만 여기서 주의할 점은 행과 열이 다르니 마지막 결과값이 .. 더보기
[18111][java][백준]마인크래프트 알고리즘 구현 브루트포스 알고리즘 문제 풀이 주요 문제 풀이는 1. 땅의 평탄화 2. 최소 시간 이 중요하다 그렇다면 "내가 사용 가능한 블록의 수 = 인벤토리에 있는 블록 수 + 땅에 있는 블록의 수" 이므로 N x M 크기의 집터를 나누어줘서 평탄화 했을 때의 한칸에 쌓을 수 있는 최대 크기를 구한다 ( 사용가능 블록수 / (N * M) ) 걸리는 시간을 구하고 0 미만이 되기전까지 (-1값이 나오면 안되므로) 블록의 수를 빼가면서 시간을 구하여 비교하면서 최소 시간을 판별한다. 예제 1번을 보자. N = 3, M = 4, B = 99 0 0 0 0 0 0 0 0 0 0 0 1 출력 : 걸리는 시간 : 2 , 땅의 높이 : 0 땅의 높이를 모두 같게 만들어야 하므로 내가 사용할 수 있는 블록의 수는 .. 더보기
반응형

티스토리툴바