mondegreen

[Part1-Chapter04-Clip09] - 백준 2817 ALPS식 투표 우선순위 큐나 set을 써야하나라는 고민이 들었던 문제였다. 아직 강의 순으로는 해당 자료구조를 배우지 않아서 최대한 배열을 사용하려고 했고 하지만 시간 복잡도를 고려했을 때 가장 높은 점수 순으로 칩을 부여하기 위해서는 적어도 리스트에 담아 정렬할 수밖에 없다는 생각이 들었다. 참가자들의 수가 250만이지만 스태프 수는 10명으로 제한되어 있고 나누는 값도 최대 14까지 적은 수가 반복문을 여러번 돌아도 시간 초과는 나지 않을 것 같았다. 또 칩을 부여하는 과정에서는 내림차순으로 정렬된 수를 각 스태프의 기본 점수로 나누었을 때 나머지가 0.0이면 칩을 부여하는 방식으로 처리했었는데 왜인지 찾을 수 없는 경우가 있어 모든 점..

[Part1-Chapter04-Clip08] - 백준 2840 행운의 바퀴 자료구조를 사용하지 않고 배열로 처리하고자 했다. 문제에서 요구하는 제한이 좀 있어서 애를 먹었다. 시계방향이지만 결국 반시계 방향으로 값을 꺼내야 한다는 점이나(반시계방향으로 넣었으면 시계방향으로 꺼내면 된다) 같은 알파벳이 같은 자리에 들어가는 건 가능하지만 같은 알파벳이 다른 자리에 들어가게 된다면 존재할 수 없는 바퀴이다. 이번 문제를 풀면서 복잡한 조건은 어떻게 잘 이해하고 구현했지만 아직 인덱스를 활용하는데 어려움을 겪었다. 내가 작성한 코드와 아래 리팩토링 코드(다른 분의 인덱스를 참고했다)를 비교해보면 결국 같다. 모드 연산한 값이 경계를 벗어나면 다시 배열의 범위로 들어오게 하는 것. 나의 경우는 순서대로 값을 넣..

[Part1-Chpater04-Clip06] - 백준 10250 ACM호텔 배열을 그리지 않고 계산으로 풀었다. 손님에게 방 배정하는 방식이 명료해서 n번째 손님을 층으로 나누면 어느 라인에 배정받을지 알 수 있다. 나머지가 0이라면 해당 정수 나눗셈의 몫인 라인에 배정받고 층은 최상층이다. 나머지가 0이 아니라면 몫에 1을 더한 라인에 배정받고 층은 나머지와 동일하다. package BaekJoon.simulation; import java.util.Scanner; public class BJ10250 { public static int t, h, w, n; public static void main(String[] args) { solve(); } private static void solve() {..

[Part1-Chapter04-Clip05] - 백준 3085 사탕게임 시간이 많이 걸린 문제였다. 처음에 시간 복잡도를 최대한 줄여보겠다고 한 행과 열에 등장하는 색을 체크하고 수가 적은 행열만 반복하려다가 행과 열을 구분해서 작성하게 되고 오히려 코드가 길어져서 포기했다. 다시 고민해보니 차라리 사방탐색을 하며 경계 체크하고 다르면 바꾸고 해당 요소가 속한 행렬에서 최대 연속 수를 구하는 방식으로 구현했다. 오히려 코드가 명료해졌고 인접한 사탕이 다른 경우에만 바꾸고 시간 복잡도를 고려해 그 사탕이 속한 행렬만 체크하도록 구현했기 때문에 추가로 원래 배열인 경우에도 최대 연속의 수를 구하도록 했다. 이 글을 작성하다 보니 이렇게 풀면 안되었나.. 바꾸고 모든 행렬을 보아야했을까? 라는 생각이 든다. ..

[Part1-Chapter04-Clip02] -백준 10448 유레카 이론 아무리 생각해도 재귀가 아니라면 반복문을 3중으로 돌리는 수밖에 없다고 생각해서 아래와 같이 3중 반복문을 구현하여 돌렸다. 불필요한 순회를 줄이기 위해 찾으면 바로 반복문을 빠져나오도록 처리했다. package BaekJoon.bruteforce; import java.util.Arrays; import java.util.Scanner; public class BJ10448 { public static void main(String[] args) { solve(); } private static void solve() { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); S..

[Part1-Chapter03-Clip04] -백준 10989 수 정렬하기 3 위 문제는 시간 제한과 메모리 제한이 비교적 있는 편이라 단순히 삽입 정렬을 할 수는 없었다. 최악의 경우 모든 숫자를 배열에넣고 단순히 sort 매서드를 쓰기에는 메모리 제한에 걸리기 때문에 그렇게 풀 수 는 문제는 아니었고. 정수배열의 경우 인덱스 하나당 4바이트 인데 모든 수를 배열에 넣는다면 4천만 바이트로 메모리 제한에 걸리기 때문에 불가. 주어지는 수의 갯수는 천개 이지만 수의 종류가 최대 10000이기 때문에 카운팅 배열을 활용하고자 했다. 입력을 받으며 해당하는 인덱스에 갯수를 늘려주고 입력되는 수의 최대값을 구해 놓으면 반복문을 돌 때 그 수를 줄일 수 있을 거라고 생각했다. 카운팅 배열에 오름차순으로 값을 넣..

[Part1-Chapter03-Clip01] 각 연산의 시간 복잡도는 다음과 같다. 1) 원소 반환: 배열의 주소를 알고 각 인덱스가 정수 배열의 경우 4byte씩 차지하기 때문에 주소 계산이 바로 가능하다. 따라서 시간 복잡도는 O(1)이다. 2) 원소 변경: 1)과 마찬가지로 동일하게 접근해 변경하기 때문에 시간 복잡도는 O(1) 이다. 3) 맨 뒤 원소 삽입: 마찬가지로 인덱스를 지정해 삽입하는 것이기 때문에 시간복잡도는 O(1)이다. 4) 원소 삽입: idx 원소 앞에 원소 삽입하는데 원하는 인덱스부터 마지막 원소까지 한 칸씩 뒤로 이동시켜야 하기 때문에 반복문을 수행하게 되고 이 때문에 시간 복잡도는 O(n)이다. 5) 원소 삭제: 1)~3) 연산과 마찬가지로 특정 인덱스에 접근해 값을 지우는 ..

[Part1-Chapter02-Clip01] 시간복잡도란 입력 크기와 알고리즘 간의 관계를 나타내는데 우리는 주로 Big-O 표기법으로 나타낸다. 문제에서 정의된 입력 데이터 중 가장 최악의 상황을 포함한 시간의 상한선을 말한다. 입력된 값과 연산을 고려했을 때 도출되는 시간복잡도 중 상수는 제외한다. 즉, O(3N+2)일 경우 3과 2는 제외하고 시간 복잡도는 O(N)이라고 말할 수 있다. 이는 입력된 값에 비례하는 시간복잡도를 가졌다는 것을 의미한다. 이를 통해 우리는 입력 크기에 대해 우리가 작성한 프로그램의 동작시간을 가늠해볼 수 있다. 아래 그래프는 n의 크기에 따른 실행속도 N을 보여주며, 표는 입력값의 범위에 따라 최대 허용되는 시간 복잡도를 대략적으로 유추한 참고 값이다. 코딩테스트에서 시..

[Part1-Chapter01-Clip06] - 백준 13223 소금폭탄 첫번째 풀이에서 놓친 점은 바로 로봇이 소금을 투하하는 데 걸리는 시간이 최대 24시간이 될 수 있다는 점이다. 즉, 현재시각과 컵을 이용할 시각이 같은 시각으로 주어질 수 있다는 것이다.(꼬박 1일이 지난 때) 이 부분을 조건문으로 추가하여 맞힐 수 있었다. 그런데 조건문이 난무해서 다른 방식이 없는지 추가로 고려해봐야겠다. 왼쪽은 시각을 입력받는 코드인데 6개의 변수를 선언하는 대신 2차원 배열로 입력 받았다. 여기서 split을 활용했지만 substring 매서드로도 가능하며, 각각의 string을 character 하나씩 떼어내서 앞자리에는 10을 곱하는 방식으로 추출할 수도 있다. 오른쪽은 풀이인데 아무래도 시, 분, 초 ..

[Part1-Chapter01-Clip05] - 백준 1153 문서검색 첫번째 풀이는 String의 패키지의 replace 메서드를 이용해 해당하는 타겟 단어가 존재하는 경우 영문자가 아닌 기호로 변경하고 그 기호 수를 세어 타겟 수를 반환했다. 가장 단순하게 풀 수 있는 방법이었다. 이렇게 풀고 말기에는 아쉬워 투포인터 방식으로 타겟 단어 탐색을 진행했다. 주의해야 할 점은 단어 탐색이 처음부터 틀렸을 때, 중간부터 틀렸을 때 어디서 부터 탐색을 다시하게끔 조정하냐는 것이었다. 생각하지 못한 테케가 왕왕 있어서 구현에는 조금 시간이 걸렸다. 아래 케이스가 오답을 잡아준 케이스였다. ababaa abaa 이 경우 aba까지 일치하고 그다음 a에서 틀리는 경우 시작점을 틀린 인덱스가 아닌 두번째 글자부터 ..