다빈이 공부

문제: https://www.acmicpc.net/problem/5086문제 접근문제에서 주어진 대로,, 풀었습니다!입력 받는 숫자를 차례로 num1, num2라고 하였을 때num1, num2가 둘 다 0일 경우: 종료num2를 num1으로 나눴을 때 나머지가 0인 경우(num2%num1==0): factor 출력num1을 num2로 나눴을 때 나머지가 0인 경우(num1%num2==0): multiple 출력아무것도 만족하지 않는 경우: neither 출력전체 코드import java.io.*;public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new Buffe..

문제: https://www.acmicpc.net/problem/10845문제 접근이 문제는 큐를 구현하는 문제였는데, 저는 자바에서 제공하는 Queue 인터페이스 및 구현체를 사용하였습니다.우선 큐란 스택과 반대로 가장 먼저 들어온 데이터가 가장 먼저 나가는 선입선출(First In Fisrt Out) 구조입니다. 큐의 활용 예시로는 최근 사용문서기록, 인쇄작업 대기 목록 등이 있습니다. 자바에서는 큐의 가장 뒤에 있는 요소를 출력하는 함수가 없기 때문에 가장 마지막의 값을 저장하는 변수 back을 만들었습니다.큐의 경우 맨 뒤에 값이 추가되므로, push 명령어가 들어왔을 때 back에 값을 저장하였습니다.전체 코드import java.util.*;import java.io.*;public class..

문제: https://www.acmicpc.net/problem/10773문제 접근스택에 있는 데이터의 합을 answer이라 할 때, 문제에서 알 수 있는 것은 다음과 같습니다:0이 아닌 수가 들어온 경우: 스택에 넣으며(push), answer에 더한다.0이 들어온 경우: 가장 최근에 넣은 값을 빼며(pop), answer에서도 뺀다.저 같은 경우에는 알고리즘 별로 풀기에서 찾은 문제라, 스택을 이용하여 푸는 문제임을 바로 알았습니다. 하지만 혹시라도 코딩테스트를 풀 때 "가장 최근에 넣은 값을 뺀다." 라는 문장이 있으면 스택을 사용해야겠구나! 라고 생각하시면 될 거 같습니다.전체 코드import java.util.*;import java.io.*;public class Main { public..

문제: https://www.acmicpc.net/problem/24264문제 접근MenOfPassion에 입력값을 넣어 수행 횟수와 시간복잡도의 최고차항 차수를 구하는 문제였습니다.(혹시라도 빅오 표기법에 대해 궁금하시다면 저번 글을 참고해 주세요!) 우선, MenOfPassion 알고리즘은 다음과 같습니다.MenOfPassion(A[], n) { sum 배열과 입력값이 주어진다.sum을 0으로 초기화한다.첫 번째 for문: i를 1부터 n까지 수행 (n번)두 번째 for문: j를 1부터 n까지 수행(n번)A[i] x A[j] 와 sum을 더하여 sum에 저장한다.for문이 끝나면 sum 반환이때 실행 결과에 영향을 미치는 것은 중첩 for문입니다.i = 1 일 때, j는 1부터 n까지 수행 i ..

문제: https://www.acmicpc.net/problem/24262문제 접근저는 바보라 처음에 문제를 이해하는 것이 어렵더라구요..?문제에 나와 있는 MenOfPassion 함수를 작성해야하는지 헷갈렸습니다. 알고보니 입력값을 MenOfPassion에 넣는다 생각하고 알고리즘의 수행 횟수와 시간복잡도(빅오표기법)의 최고차항 차수를 구하면 되는 것이었습니다. 따라서 이 문제를 풀기 위해서는 빅오 표기법에 대해서 알아야 합니다! 먼저, 빅오 표기법(Big-O Notation)이란 알고리즘의 시간 복잡도나 공간 복잡도를 표현할 때 사용되는 수학적 표기입니다. 즉, 입력 크기(n)가 커질 때 알고리즘의 실행 시간이나 메모리 사용량이 얼마나 증가하는지를 표현하는 방법입니다. 알고리즘의 정확한 실행 시간은 ..

문제: https://www.acmicpc.net/problem/1764문제 접근처음 문제를 봤을 때는 List를 활용해서 하면 되겠구나! 라고 생각하고 다음과 같이 생각했습니다.사람의 이름을 담을 리스트(names)와 듣보잡을 담을 리스트(nm) 생성input값이 names에 없으면 names에 추가input값이 names에 이미 존재한다면 듣보잡으로 판단하여 nm에 추가nm 정렬한 후 출력근데 시간초과가 뜨더라구요..! ㅠ.ㅠ 그래서 사람의 이름을 담는 것을 리스트가 아닌, HashMap으로 구현하였습니다!HashMap은 조회할 때 일반적으로 O(1)의 시간복잡도를 갖기 때문에, 리스트보다 훨씬 빠릅니다.그래서 Key는 사람 이름으로 두고 Value는 입력된 됐는지 안됐는지만.. 확인하는 용도..로...

문제: https://www.acmicpc.net/problem/9012문제 접근이러면 안되지만 알고리즘 분류가 자료구조, 문자열, 스택으로 되어 있어서.. 스택을 사용하여서 풀면 되겠구나 라고 생각했습니다 ㅎㅎ;; 먼저 스택이란 데이터를 하나씩 쌓아 올린 형태의 자료 구조로, 가장 나중에 들어온 데이터가 가장 먼저 나가는 후입선출(Last In Fisrt Out)을 구조입니다. 스택의 활용 예시로는 웹 브라우저 뒤로 가기, 문서 작업에서 ctrl+z 등이 있습니다. 그래서 이 문제에서는 다음과 같이 스택을 적용했습니다:문자가 '(' 이면 스택에 넣는다.문자가 ')' 이면 스택이 비어있는지 검사한다.만약 비어있으면 ')'를 스택에 넣고 break를 사용하여 for문을 빠져 나간다 (스택이 비어있으면, '..

문제: https://www.acmicpc.net/problem/8958문제 접근입력 받은 문자열에서 charAt() 을 통해 이전 문자랑 현재 문자를 비교해야겠다고 생각했습니다.그래서 저는 다음과 같이 조건을 나눠서 생각했습니다.이전 문자는 'X'인데, 현재 문자가 'O'인 경우이전 문자랑 현재 문자가 'O'인 경우나머지 경우 (즉, 현재 문자가 'X'인 경우)1번의 경우, 점수가 1이 됩니다. 연속 되는 'O'의 개수만큼 점수를 더 얻는데, 이 경우에는 'O'문자의 시작점? 이니까요!2번의 경우, 원래의 점수(score)에서 1을 더해져서 점수는 score + 1이 됩니다.3번의 경우, 현재 문자가 'X'이니 점수는 0이 됩니다. 그리고 점수를 다 더한 후, 출력하면 되겠죠?엄.. 제가 설명을 잘 못..

문제: https://www.acmicpc.net/problem/1427문제 접근문제를 보자마자(?) 리스트에 넣고 Collections.sort() 사용해야 겠다고 생각했습니다리스트 생성 (Character형이든, Integer형이든 상관없음)input값을 charAt()으로 하나씩 리스트에 넣음Collections.sort() 로 정렬전체 코드1) 리스트를 Integer로 생성한 경우import java.io.*;import java.util.*;public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamR..

문제: https://www.acmicpc.net/problem/1181문제 접근문제에 나온대로 다음과 같이 생각했습니다:문자열을 담을 리스트를 생성한다. (만약 이미 list에 있는 단어면 넣지 않는다)문자열이 짧은 것부터 오름차순으로 정렬 (길이가 같으면 사전순으로 정렬)사실 처음에는 Map에 문자열과 문자열길이를 넣을까 했는데, 리스트로 선택했습니다. (이유는 정렬할 때 리스트가 더 쉬운 거 같아서 입니다.)리스트 생성하고 오름차순으로 정렬하는 것까지는 쉬웠는데... 문자열 비교하는 함수 equals 말고는 도저히 생각이 안 나더라구요 ㅎㅎ;; 그래서 바로 구글에 문자열 사전순 비교하는 법 찾아봐서 코드를 완성했습니다 ㅋㅋ..이번에 오답노트 느낌으로 정리하고 나중에 이 문제가 생각 안 날 때 한 번..