목록Algorithm (153)
다희의 코딩 성장일기
[백준] 1254. 펠린드롬 만들기 (자바 JAVA)
[ 문제 ] [백준] 1254. 펠린드롬 만들기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net # 접근 방법 및 풀이 이런 문제가 코테로 나오면 바로 풀었을까 싶은 문제다.. 대신 한번 풀어보면 쉽게 풀 수 있다. 문제대로 팰린드롬이란 "문자를 앞으로 읽어도 뒤로 읽어도 같게 읽히는 문자열"이다. 먼저, 문자열이 펠린드롬인지 확인하는 함수를 만든다. 펠린드롬인지 확인하는 방법은 "앞의 인덱스와(start)" "뒤의 ..
[백준] 1138. 한 줄로 서기 (자바 JAVA)
[ 문제 ] [백준] 1138. 한 줄로 서기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net # 접근 방법 및 풀이 구현 문제다. 아이디어를 떠올렸다면 쉽게 풀었을 수도 있지만, 약간 생각하는데 시간이 걸렸다. 먼저, 문제에서 입력으로 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇명 있는지 주어진다. 예제대로 N = 4일 때, 2 1 1 0 으로 입력을 받아 arr[] 배열에 담아준다...
[프로그래머스] level1. 없는 숫자 더하기 (자바 JAVA)
[ 문제 ] [프로그래머스] level1. 없는 숫자 더하기 (자바 JAVA) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/86051?language=java 코딩테스트 연습 - 없는 숫자 더하기 0부터 9까지의 숫자 중 일부가 들어있는 배열 numbers가 매개변수로 주어집니다. numbers에서 찾을 수 없는 0부터 9까지의 숫자를 모두 찾아 더한 수를 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr # 접근 방법 및 풀이 자세한건 코드참조 # 주의할 점 딱히 없음 JAVA 코드 class Solution { public int solution(int[] numbers) { int answer ..
[백준] 11725. 트리의 부모 찾기 (자바 JAVA)
[ 문제 ] [백준] 11725. 트리의 부모 찾기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net # 접근 방법 및 풀이 트리구조를 떠올리며 BFS로 풀었다. DFS로도 가능. 노드의 부모를 찾는 문제다. 트리라고하니 이진트리라고 한정지었는데 틀렸다. 문제에 이진트리라는 조건도 없고 그냥 연결된 노드 정보만 있다. 다만, 루트노드가 1이기 때문에 루트노드부터 연결된 노드를 탐색하며 부모노드를 찾을 수 있다. 현재 노드가 어디 노드로부터 왔는지 찾으면 된다. 예제 1번에 "1..
[백준] 5639. 이진 검색 트리 (자바 JAVA)
[ 문제 ] [백준] 5639. 이진 검색 트리 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net # 접근 방법 및 풀이 트리문제다. 문제의 조건에 맞는 이진트리를 구현하고, 후위순회를 재귀함수로 만들어 값을 프린트하면 된다. 이진트리를 구현하기 위해 Node 클래스를 만들어 "현재 노드의 값, 왼쪽 노드, 오른쪽노드" 변수 세개를 만들어 주었다. 문제의 입력에 첫번째로 입력되는 값이 root이므로 먼..
[백준] 1074. Z (자바 JAVA)
[ 문제 ] [백준] 1074. Z (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net # 접근 방법 및 풀이 분할정복 재귀 문제다. 앞서 다뤘던 "쿼드트리, 색종이 만들기" 문제처럼 그냥 재귀 돌리면 시간초과난다. 이유는 N의 범위가 최대 15이므로 2^15 사이즈의 map을 다 잘게잘게 잘라서 r, c를 하나씩 확인한다면 시간초과난다. 여기서 중요한건, R, C가 "1, 2, 3, 4" 사분면 중에서 어..