CS/자료구조&알고리즘9

• 

  [백준] 2373번 세 용액 들어가며두 용액을 이분탐색으로 풀어서 이 문제도 이분탐색으로 풀어야하나? 라는 생각이 당연하게 들었다. 근데 보통 left, right로 나눠서 3개의 포인터(?)를 가지고 답을 구해나가야하는데 이건 세가지인데? 이런 혼란이 생겼다. 그래서 아 그럼 2개씩 뽑아서 구한 조합의 합을 먼저 구하고 원본 배열 (nC2 + n) 합쳐서 이분탐색을 돌리면 3개의 합이 나오지 않을까? 라고 생각했다. 근데 3개의 원소를 어떻게 기록하지...이처럼 생각이 많았던 문제이다. 브루트포스, 조합을 거쳐갔지만 결국 이분탐색으로 풀었다.  문제 풀이우선 이분탐색이지만 주의할 점은 3개의 용액의 합을 비교해서 풀어야한다는 것이다. 그래서 2중으로 반복문이 돌아가겠지만 이분 탐색이므로 O(nlgn)이 될것으로 예상된다.1. 먼저.. CS/자료구조&알고리즘 2024. 5. 7.

• 

  [백준] 9252번: LCS2 https://www.acmicpc.net/problem/9252 9252번: LCS 2LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.www.acmicpc.net   들어가며LCS 문제를 DP로 풀어야한다는 것은 알고 있었지만 길이가 아닌 LCS 문자열을 구하는 과정에서 어려움이 있었습니다. 우선 LCS가 뭔지 간단하게 보고 예제의 결과가 어떻게 나왔는지 과정을 보고 문제 풀이 방식에 대해 설명하겠습니다! LCS(Longest Common Subsequence)란?최장 공통 부분 수열이라는 의미로, 주어진 여러 .. CS/자료구조&알고리즘 2024. 4. 26.

• 

  [프로그래머스]모음 사전 (level 2, 완전 탐색) from itertools import product def solution(word): answer = 0 word_list = generate_words() word_list.sort() # 사전순 정렬 for i, w in enumerate(word_list): if w == word : answer = i + 1 return answer def generate_words(): char_list = ['A', 'E', 'I', 'O', 'U'] words = [] for length in range(1, 6): # 1부터 5까지 길이의 문자를 만들 것임 for p in product(char_list, repeat=length): # repeat: 반복 횟수 -> 길이가 length인 조합을 생성함.. CS/자료구조&알고리즘 2024. 3. 11.

• 

  [백준] 20310번: 타노스 (25점 반례) https://www.acmicpc.net/problem/20310 20310번: 타노스 어느 날, 타노스는 0과 1로 이루어진 문자열 $S$를 보았다. 신기하게도, $S$가 포함하는 0의 개수와 $S$가 포함하는 1의 개수는 모두 짝수라고 한다. 갑자기 심술이 난 타노스는 $S$를 구성하는 문자 www.acmicpc.net 1차 시도: 25점 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buffere.. CS/자료구조&알고리즘 2024. 2. 15.

• 최단 경로 알고리즘 비교 다익스트라 알고리즘 (Dijkstra's Algorithm): 특징: 다익스트라 알고리즘은 하나의 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. 음의 가중치가 없는 그래프에서 사용됩니다. 알고리즘 사용하는 상황: 음의 가중치가 없는 그래프에서 사용되며, 최단 경로를 찾아야 하는 경우에 활용됩니다. 알고리즘 동작 과정: 출발 정점을 기준으로 초기화합니다. 출발 정점에서부터 각 정점까지의 최단 경로를 갱신합니다. 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점을 선택하여 방문합니다. 해당 정점을 경유로하여 인접한 정점까지의 거리를 갱신합니다. 위 과정을 모든 정점을 방문할 때까지 반복합니다. 벨만-포드 알고리즘 (Bellman-Ford Algorithm): 특징: 벨만-포드 알고리.. CS/자료구조&알고리즘 2024. 2. 11.

• 

  [백준] 8979번: 올림픽 문제 유형은 구현, 정렬 문제 풀이 방법 나라, 금/은/동메달 개수, 순위 등을 저장할 클래스 (Medal)를 생성한다. 이때 동점자를 계산하기 위해 score 변수를 Medal 클래스 내에 정의한다. 금메달은 10점씩 은메달은 5점씩 동메달은 1점씩 부여해 총점을 계산한다. 우선 금/은/동메달을 기준으로 정렬한다. 금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 많은 나라 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 순위를 계산한다. - 각 나라의 score를 비교해서 동일한 경우 동점 국가와 동일한 등수가 되고, 그렇지 않다면 (자신보다 더 잘한 나라 수) + 1 이 등수가 된다. 결과를 알고 싶은 국가의 등수를 출력한다. package 구현; import java.io.. CS/자료구조&알고리즘 2024. 2. 4.

• 

  [백준] 2870번: 수학문제 풀이 방법 정규식을 통해 숫자를 걸러낸다. 숫자가 아닌 문자는 " "으로 바꾼다. 빈칸을 제거한다. 이 과정에서 split(" "), isBlank()를 사용했는데 ... 먼저 공백을 기준으로 문자열을 나누기 위해 split()을 사용했다. 내가 예상한 결과는 숫자만 배열에 저장되는 것인데 예상치 못하게 빈 문자("")도 같이 저장되었다. 그래서 isBlank를 사용해서 추가 검증을 해주었다. 숫자만 골라내 리스트에 저장하고 이를 정렬한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.ArrayList;.. CS/자료구조&알고리즘 2024. 1. 24.

• 

  [프로그래머스] 문자열 다루기 기본 class Solution { public boolean solution(String s) { return isValidLength(s) && isMatchPattern(s); } private boolean isValidLength(String s) { return s.length() == 4 || s.length() == 6; } private boolean isMatchPattern(String s) { try { int n = Integer.parseInt(s); return true; } catch (Exception e) { return false; } } } 개인적으로 깔끔하게 풀었다고 생각해서 기록하는 중 ᜊʕ ྀི ܸ. . .ܸ ྀིʔᜊ CS/자료구조&알고리즘 2024. 1. 12.

• 

  [프로그래머스] 파일명 정렬 : JAVA 초기 제출 코드 import java.util.*; class Solution { public String[] solution(String[] files) { Arrays.sort(files, new Comparator() { @Override public int compare(String s1, String s2) { FileName fileName1 = exportFileName(s1); FileName fileName2 = exportFileName(s2); if (fileName1.getHead().toLowerCase().compareTo(fileName2.getHead().toLowerCase()) > 0) { return 1; } else if (fileName1.getHead().toLow.. CS/자료구조&알고리즘 2024. 1. 11.