본문 바로가기

알고리즘

[백준] 1253 좋다 1. 문제 분석[문제 링크](https://www.acmicpc.net/problem/1253)2. 접근 방식배열의 양 끝에 포인터를 둔다. 현재 Good이 되는 수인지 검산 한다. (포인터 2개의 합이 현재 검산 중인 수보다 크면 오른쪽 포인터를 한 칸 내린다.) (포인터 2개의 합이 현재 검산 중인 수보다 작으면 왼쪽 포인터를 한 칸 올린다.)숫자는 음수도 가능하므로, 제약없이 전체에 대해서 계산 해야한다. 이는 O(n^2)의 시간 복잡도가 들지만, 계산해야할 총 데이터 수가 2000 이므로 10^3 이라 계산이 괜찮다. 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;im.. 더보기
[백준] 2018 수들의 합 5 Java 풀이 1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/2018)2. 접근 방식투포인터 문제 투 포인터 구간 안에 합을 변수 acc에 저장한다.acc acc > N 이면 왼쪽 포인터를 한 칸 움직여서 그 값을 acc에 더한다. 이렇게 오른쪽 포인터가 구간의 맨 끝에 도달할 때까지 반복하며 acc == N 인 경우를 센다.3. 코드 분석 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws IOException { BufferedRead.. 더보기
[자료구조] 배열, List, Map, Stack, Queue, Priority Queue 1. Array(1) 정의번호와 번호에 대응되는 값들로 이루어진 자료구조를 의미한다.번호만 알고 있으면, 해당 번호에 해당하는 값을 O(1)에 조회가 가능하다.(2) 특징ⓐ Index에 해당하는 값에 바로 접근할 수 있다. (값 조회에 빠르다.)ⓑ 배열은 선언할 때, 그 크기가 정해진다. 그 이후, 줄이거나, 늘릴 수 없다.ⓒ 따라서 중간에 값을 삽입하거나 삭제하기가 어렵다.만약에 그러한 구현이 꼭 필요하다면, 빈 배열을 통해 변경사항이 반영된 배열을 새로 만들어야 한다.(3) 많이 쓰 함수ⓐ Arrays.asList(T..a): 배열을 ArrayList로 변환시켜준다.ⓑ Arrays.toString(): 배열을 문자열 형태로 변경해준다. 문자열 형태: [a,b,c,d...] → 출력할 때 많이 씀ⓒ A.. 더보기
[백준] 11659 구간 합 구하기 4 쉬운 풀이 여러가지 풀이 java 1. 문제 설명문제 링크2. 접근 방식해당 문제는 주어지는수의 개수가 10^5 개이다. 이는 n^2만 해도 1억 번의 계산을 넘어서, 시간초과가 날 것이다. 만약 값을 입력 받으면서, 그 전에 받았던 입력들을 일일히 조회하여 구간합을 구한다면, 이는 n^2로 시간 초과가 난다. 누적 합 배열을 이용해 구간 합을 O(1) 안에 구한다.sum[] 이라는 배열을 만든다. sum[i]는 sum[0] ~sum[i]까지의 합이다.sum[i] = sum[i-1] + arr[i] (현재값) 으로 구할 수 있다. i ~ j 까지의 구간합을 구해야할 경우 (i 3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream.. 더보기
[백준] 구간 합 구하기 5 쉬운 풀이, 여러가지 풀이 java 1. 문제 설명문제 링크2. 접근 방식sum[i] [j] = (0,0) ~ (i,j) 까지의 합으로 나타냈다.i = 0 인 열은 이전 행의 최대 값을 저장하도록 해서, 누적합이 계속 이어지도록 만들었다.하지만 구간 합 (a,b) ~ (c,d)를 구하라 함은, a 그래서 나는 다음과 같이 구했다.다음과 같이 푸른색 형광펜에서 보라색 형광펜 값을 빼주고 그 결과들을 더 했다.3. 코드 분석import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { public static void main(String[] ar.. 더보기
백준 11720_숫자의합 Java 여러가지 풀이! 1. 문제 설명[문제 링크](https://www.acmicpc.net/problem/11720)문제N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.입력첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.출력입력으로 주어진 숫자 N개의 합을 출력한다.예제 입력 1 복사11예제 출력 1 복사12. 접근 방식숫자는 모두 한 자릿수 이다. 길이가 10인 배열을 만들어서 index -> 숫자, value -> 숫자의 개수를 저장한다.String 문자열 한 줄로 들어온 숫자들을 모두 체크한 이후에, 길이 10의 배열을 순회하면서 index* value의 총합을 구한다. 3. 코드 분석import java.io.Buffe.. 더보기
[코드 트리] 진법 변환 3 java 1. 문제 설명문제링크8진수 -> 2진수2. 접근 방식8진수 → 2진수로 변환하는 방법은 다음과 같다.ⓐ 8진수 각 자리를 떼어낸다.ⓑ 각 자릿수를 2진수로 바꾼다. (한자리는 0~8 사이의 수임으로 2진수로 바꿀 시, 2진수는 무조건 3자리 이하임)ⓒ 2진수로 바꾼 수를 이어 붙인다. (이때, 모든 2진수는 3자리를 차지해야한다. 아니면 전혀 상관 없는 이상한 수가 된다.)3. 코드 분석import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStrea.. 더보기
[프로그래머스] 42888. 오픈채팅방 JAVA 풀이 설명 1. 문제 설명문제 링크카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다."[닉네임]님이 들어왔습니다."채팅방에서 누군가 나가면 다음 메시지가 출력된다."[닉네임]님이 나갔습니다."채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.채팅방에서 닉네임을 변경한다.닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.예를 들어, 채팅방에 .. 더보기

티스토리툴바