BAEKJOON

공백포함 숫자를 입력하기때문에, 공백포함해서 한줄 전체를 입력받는 nextLine()을 사용.split()을 사용하여 공백을 기준으로 숫자를 나눈 후 String배열에 저장. 분리되어 저장된것은 문자열이기때문에, 숫자로 형변환 후 덧셈연산과 동시에 출력.String i

몇 단을 출력하고싶은지 숫자로 받은 후, for문에서 받은 숫자에 곱해질 숫자를 1부터 9까지 증가시키고 곱해서 바로 출력한다.int num을 입력받아 저장하는것에서 한 번, i=1 한 번, 구구단을 출력하는것 9번, i+1 9번, 이것을 i에 대입하는 것 9번 → 2

입력을 받으면, 첫번째 while문이 반복되지않는다. 즉, 입력된 수 자체만 검사하고 프로그램이 종료되는 문제. \-> 원인 : 처음에는 입력받은 수에대한 변수를 num하나로만 사용해서 while문 밖의 변수와 while문 안의 변수가 하나로 사용되었기때문에 while

제공된 테스트케이스는 정상적으로 돌아갔는데, 채점결과는 틀렸다고 떠서 한참을 헤맸다.\-> 원인 : 내가 사용한 알고리즘에서 첫번째로 고정된 수(strArr.get(i))가 구해야하는 두수의 합보다 크거나 같으면, 두번째로 찾으려는 수(find)가 0또는 음수가되기때문

테스트 케이스를 보고, 처음 입력에 2를 넣어주자 Exception in thread "main" java.lang.NumberFormatException: For input string: "" 라는 에러가 났다. \-> 원인 : 단순하게는 주석처리해둔 int num

문제 알고리즘 문제요약 사용할 수 있는 자료구조 생각한 알고리즘 시간복잡도 예상 결과 작성한 코드 헤맸던부분과 해결방법 및 느낀점 찾아본 지식

문제 알고리즘 문제요약 각 아이들이 가져가기를 원하는 선물의 개수가있는데, 각각 다른 개수가 담겨있는 선물상자 중 한 상자로 한 아이가 원하는만큼 선물을 나누어주면서, 어떤 상자든 한 아이당 한 상자로 모든 아이들을 커버할 수 있는지 묻는 문제이다. 이전에 다른 아이

슈도코드 코드 문제 실행시 첫번째 라인에서 count를 입력받고 두번째 줄에서 sNumber을 입력받아야하는데, 첫번째 입력을 넣고 엔터를 치면 프로그램이 종료되는 문제가 발생! 원인 해결 nextLine() -> next()로 수정 처음에는 위와같이 fo

결과가 예제와 다르게 나와서 디버깅해보니, newScore에 0이 들어가서, 최대값을 제외한 나머지값들이 0으로 바뀌는현상을 발견했다.score, max가 int형이고, max가 무조건 크거나 같으므로 1.0 혹은 0.xxx가 결과일것이다. 근데 int끼리 나누면 소수

오늘 처음으로 BufferedReader, BufferedWriter, StringTokenizer를 사용해봤다.1\. 입력은 제대로 들어가는데, 콘솔에 출력이 안되는 현상이 발생했다.(사진에서 '1 3', 다음줄 출력, '2 4', 다음줄 출력, '5 5', 다음줄

슈도코드 Troubleshooting 문제 처음엔 이처럼 코드를 짰는데, 아래처럼 출력이 이상하게 나왔다. 원인 배열 변수의 이름은 배열의 시작 주소인데, 출력부분에서 저렇게 로직을 짜서 배열의 시작 주소가 출력된것으로 보인다. 해결 solution호출의 리턴값

🙋정렬 + 투 포인터 알고리즘 사용콘솔 결과가 주어진 예시와 다르게 0으로 찍힌다.sum == Ai 혹은 end == start 일 때, check = false를 하고 되돌리지 않는게 문제였다. while을 한 번 돌고 나간 후에는, 다시 그 다음 원소로 while

DFS를 처음 다루어보고, 너무 어려워서 이 문제를 다시 풀었다.그런데,, 또 틀렸다!실행하며 예제 입력 1의 두번째 줄 '1 2'를 입력할 때,java.lang.NullPointerException이 발생했다.이 에러는 null값을 가지는 객체 참조를 사용하려할 때

합을 구해야하는 횟수 최악의 경우가 100,000이므로 각각 합을 매번 구한다면 1024\*1024의 배열을 10만번 순회하게 될 것이다.시간제한이 1초이므로, 구간합을 이용해야한다!1차원 구간 합 배열만 다루었었는데, 2차원으로 확장된 것으로 생각하여 구간 합 배열을

문제 분석 N의 최대값이 106으로 작은편이지만, 이에 대한 모든 구간합을 구해야하므로 제한시간 1초안에는 해결하기 어려울 수 있다. 따라서 합 배열을 이용해야한다. 슈도코드 Troubleshooting 문제점 시간초과가 났다. 원인 수학적인 사고 없이, 그냥

투포인터 이용! O(N)N이 10,000,000으로 꽤 크다.시간제한은 2초이므로, O(NlogN)까지만가도 2초가 넘는다.따라서 O(N)으로 해결해야하며, 투포인터는 이에 해당한다.IDE에서 돌리고 예제(15)를 입력했을 때 결과가 0으로 나왔다.우선 for문의 증감

크기를 비교하는문제(두 숫자의 합..)는 값을 정렬하면 문제를 더 쉽게 풀 수 있다!시간제한은 2초이고, N의 최대범위가 15,000이므로 O(NlogN)시간복잡도 알고리즘을 사용해도 괜찮다. 일반적으로 정렬 알고리즘의 시간 복잡도는 O(NlogN)이다.즉, 정렬을 사

문제 분석 P,S의 최대가 1,000,000으로 매우 크기때문에 O(N)의 시간 복잡도 알고리즘으로 문제를 해결해야한다. 부분 문자열의 길이가 P로 정해져있으므로 슬라이딩 윈도우를 사용하자. 슈도코드 Troubleshooting

참고로 동일한 코드에서 한번은 시간초과, 한번은 성공의 결과가 나왔다.(백준)알아본결과 이 문제는 이슈가있는것같다.N의 최대값이 5,000,000이고 시간 제한이 2.4초 이므로 시간복잡도 O(n)안에 해결해야한다.일정 범위 안에서 최솟값을 구하는 문제이므로, 정렬과

슈도코드 Troubleshooting 1 Troubleshooting 2

슈도코드

N의 최대는 1000, M의 최대는 10000이다.DFS or BFS사용시 시간복잡도는 O(11000)인데, 각각 수행하므로 O(22000)이다. 이는 시간제한 2초안에 해결 가능하다.작은 노드의 번호부터 탐색 = 인접 노드를 오름차순으로 정렬한 후 재귀 함수 호출 예

🙋🏻‍♀️BFS 이용! 문제분석 N,M 최대가 100으로 매우 작기때문에 시간 제한은 별도로 생각안해도된다. -> 따라서 DFS, BFS 둘 다 사용해도 됨 지나야 하는 칸 수의 최솟값 = 완전 탐색하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지 구하는것 -

🙋 재귀함수(DFS) + 자릿수 개념 + 가지치기DFS는 재귀함수의 형태를 띄고있다!재귀함수를 사용해야할 것 같으므로 DFS를 이용하는것이다. 재귀함수에 자릿수 개념을 붙여 구현한다.문제 조건에 맞도록 가지치기도 한다.처음에 내가 생각한대로 한건 결국 틀리기도했고,

🙋🏻‍♀️DFS 이용! N,M의 최대범위가 2000이므로 인접리스트를 썼을 때 시간복잡도는 O(4000)이다.이를 모든 노드에 진행했을때 2000 \* 4000 = 8000000이므로 DFS를 사용해도 된다.주어진 모든 노드에 DFS 수행재귀의 깊이가 5이상(5개의

🙋 퀵 정렬 이용!제한시간은 2초인데, N의 최대는 5,000,000이다.퀵정렬은 O(NlogN)의 시간복잡도를 가지는데 계산하면 100,000,000. 즉 1억이므로 2초 시간내에 가능하다고 판단된다.<pivot 정하는 법>pivot == K : K번째 수를

🙋🏻‍♀️큐 이용!가장 위의 카드를 가장 아래에 있는 카드 밑으로 옮기는 동작은 큐의 선입선출 성질을 이용하면 구현할 수 있다.(보통 큐를 표현하는 그림에서 가장 아래에서 값을 빼고, 가장 위에 값을 넣는 그림을 보기때문에 헷갈렸다. 하지만 그 그림을 뒤집어서 생각

🙋🏻‍♀️기수정렬 이용! (구간합 사용) N의 최대가 10,000,000으로 매우 크기때문에 O(nlogn)보다 빠른 알고리즘이 필요하다. 기수정렬의 시간복잡도는 O(kn)인데, 숫자의 크기가 10,000보다 작으므로 이 상황에서는 O(10,000 \* 10,000

🙋🏻‍♀️이진탐색 이용!java.lang.NullPointerException이 났다.find배열을 초기화하지 않았다.M을 입력받은 후, find = new int\[M];를 추가했다.예제1에 대한 결과가 이상하다.게다가 예제 1 입력 복붙했는데, '1 3 7 9

N의 최대가 100,000이므로 O(nlogn)의 알고리즘을 쓰면, O(10^6\*5.xx)이므로 가능할것으로 판단된다. \-> 자바의 대부분 정렬알고리즘이 O(nlogn)람다식

🙋🏻‍♀️이진탐색 사용!블루레이의 크기가 모두 같고, 녹화순서가 뒤바뀌지 않아야 한다는 조건에서 이진탐색 알고리즘을 선택할 수 있다.보통 이분탐색은 정렬된 곳에서 찾는게 보통인데 해당 문제에서는 강의의 순서가 뒤바뀌면 안된다라고 적혀있다. 따라서 정렬을 하지 않고

🙋🏻‍♀️에라토스테네스의 체 이용! M이상 N이하 사이의 숫자 사이에 소수를 구하는 문제이다.N의 최대범위가 1,000,000이기때문에 일반적으로 제곱근범위까지 나누어보면서 소수를 구하는 방법은 O(sqrt(10^6) \* 1,000,000) = O(10^9)이다.

전형적인 그리디 알고리즘 문제그리디 알고리즘을 풀 수 있도록 뒤의 동전 가격 A(i)가 앞에 나오는 동전 가격 A(i-1)의 배수가 된다는 조건을 부여했다.가장 가격이 큰 동전부터 차례대로 사용하면 된다.가장 가격이 큰 동전부터 탐색을 시작하고, K보다 가격이 작거나

문제분석 N의 최대값은 10^5이므로 배열의 최대크기는 10^10이고, 따라서 브루투포스로 탐색하기에는 너무많은 시간과 메모리가 든다. 따라서 다른 접근방법을 알아봐야한다. 아래의 예시를 보자. K=11이면, B[11]=8이다. 보통은 'B행렬의 11번째값은 8이다

🙋🏻‍♀️그리디 알고리즘 사용!처음에 선택하는 데이터셋의 크기가 작은것이 중요하다.따라서 카드 묶음 크기를 오름차순으로 정렬한 후, 가장 작은것 2개를 선택해서 합치고, 합친것을 다시 배열에 넣은 후 오름차순으로 재정렬하고... 이 과정을 원소가 1개 남을때까지 반

🙋🏻‍♀️이진탐색 사용!엄청엄청 많이 헷갈렸고, 고민했던 문제다.정상이라면 '0 200 701 800 1000'이 들어가야하는데, index 1에 값이 제대로 안들어가고 하나씩 밀려들어갔다. 그래서 마지막값도 1000으로 덮어써졌다.양 끝값 제외한 값들을 먼저 넣고

🙋🏻‍♀️그리디 알고리즘 그리디 관점에서 생각하면 쉽게 풀 수 있다.결과를 최솟값으로 만들기 위해서는 가낭한 한 큰 수를 빼야한다.덧셈, 뺄셈 연산만으로 이루어져있기때문에, 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 뺄셈을 실행한다.아이디어가 생각나

문제분석 N의 최대값은 1,000,000으로 O(NlongN)으로도 풀이가 가능할것으로 보인다. 계수정렬은 O(n+k)인데, 이를 활용해보자. 슈도코드 Troubleshooting 문제 예제의 결과는 다 맞게나왔는데, 백준에서 런타임에러가 났다. 원인 해결

🙋🏻‍♀️에라토스테네스의 체 이용!A이상 B이하의 거의 소수 개수를 출력하는 문제다.에라토스테네스의 체를 이용해 B의 제곱근까지 소수를 구하고, 제곱했을 떄 A이상 B이하인 수의 개수를 출력하면 될 것 같다.에라토스테네스의 체를 이용하니, 시간제한 2초안에 가능할

최대공약수가 1이라는 이야기는 두 수가 서로소의 관계에 있다는 이야기이다.n과 서로소 관계에 있는 k의 개수를 구하면 되는 문제이기때문에, 오일러 피를 이용해서 n일때 값을 구하면 된다.백준에서 '런타임에러'가 났다.A,B의 최대크기가 10^12이기때문에 int타입으로

🙋🏻‍♀️ 유클리드 호제법 이용 a,b의 최소공배수는 a\*b/최대공약수로 구할 수 있다.따라서 유클리드 호제법을 이용해 최대공약수를 구한후 진행하면된다.A,B의 최대값은 45,000이므로 유클리드 호제법을 이용하면 한 번에 O(log45,000)이고, 이것을 T번

입력되는 수가 2^63보다 작은 자연수이면, 최대가 2^63 자리수인데.. 너무 큰 수라서 유클리드호제법으로도 가능할지 모르겠다.입력받은수중 하나가 2^63일 경우, 유클리드 호제법을 정말 gcd(10^(2^63-1)+1 % B)로 해야할지.. 조금 막막해서 찾아봤다.

모든 도로의 거리가 1이므로 가중치가 없는 연결리스트로 이 그래프를 표현할 수 있다.도시개수의 최대가 300,000 도로 개수의 최대가 1,000,000이므로 BFS탐색을 수행하면 시간 복잡도 안에서 해결할 수 있다.BFS의 시간복잡도 = O(V+E)또한 일정한 거리에

문제분석 Troubleshooting 문제 예제1에 대해서 '1 2'가 답으로 나와야하는데 '5'가 나왔다. 원인 해결

이분그래프모든 꼭짓점을 빨강과 파랑으로 색칠하되, 모든 변이 빨강과 파랑 꼭짓점을 포함하도록 색칠할 수 있는 그래프트리의 경우 항상 이분 그래프가 된다는것을 알 수 있다.사이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정하면 되기 때문이

🙋🏻‍♀️ BFS이용 (보통의 방법과 다름!)너무 어려워서 책 보고 따라 풀었다. 지금까지 접해봤던 그래프 데이터를 저장하고 저장한 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제!A,B,C의 특정무게 상태를 1

🙋🏻‍♀️ 유니온 파인드 활용!도시의 연결 유무를 유니온 파인드 연산을 이용해 해결할 수 있다는 아이디어 떠올리기!일반적으로 유니온 파인드는 그래프 영역에서 많이 활용되지만, 이 문제와 같이 단독으로도 활용할 수 있다.도시간 연결 데이터를 인접 행렬 형태로 주었기

🙋🏻‍♀️ 프림알고리즘을 사용!크루스칼알고리즘을 사용할 수 있지만, 다른 알고리즘 연습을 위해 프림알고리즘을 사용했다.예제 1의 정답이 8인데, 나는 12가 나왔다.마을을 2개로 분리하지않고 MST를 만들었다. 문제에서 마을을 2개로 분리하면서 비용을 최소한으로 한

🙋🏻‍♀️ 프림알고리즘 이용!이 문제는 특정 간선들의 정보를 주는게아니라, 각 별들의 위치를 주기떄문에 결국 모든 별들이 다 직접적으로 연결되어있다고 가정하고 푸는거나 마찬가지이다.꼭 이렇게 양방향으로 그래프에 정보를 다 넣어야할까?그럼 우선순위큐에 들어가는 정보가

시간복잡도나 공간효율성측면보다는 코드를 조금 더 간결히 사용하는 방법으로 수정했다.이전에는 반복문을 돌며 distance\[i] = Integer.MAX_VALUE;이렇게 원소 하나씩 접근해 값을 최대값으로 초기화 했었다.\-> Arrays.fill(distance,

🙋🏻‍♀️ 위상정렬 이용!각각 건물이 지어지기까지의 시간을 구하는게 헷갈렸다.처음에는 q.poll()을 하면 해당 건물을 들리는(완성하는)것이라서 그때마다 답 배열의 해당 건물인덱스에 '답 배열속 해당 건물의 값 + 해당 건물을 짓는데 걸리는시간'을 더했었다.나름

🙋🏻‍♀️ 위상정렬 +에지 뒤집기 사용!처음에 문제를 이해하기 너무 어려웠다..결국 포인트는 이거다.1\. 위상정렬로 최장거리를 구하고2\. 다시 도착점 기준으로 거꾸로 돌아오며, 최장거리 루트에 속하는 간선인지 체크한다. (중복되지 않게 체크해야함)\-> 여기서

🙋🏻‍♀️다익스트라 알고리즘 사용!다른건 괜찮은데, k번째 최단경로를 어떻게 구할지가 큰 의문이었다.도저히 생각나지않아 해설을 보고 공부했다.최단 경로를 표현하는 배열을 우선순위 큐 배열(크키K)로 변경한다.여기서 나는 우선순위 큐 배열이라는 것을 처음 접했다.Pr

🙋🏻‍♀️벨만-포드 알고리즘 사용!예제의 출력은 다 맞았는데, 틀렸습니다를 받았다.벨만포드 로직이 문제인것같다.이렇게 작성하면, 결국 1번 노드부터 N번 노드까지 차례대로 진출간선을 수행하며 거리배열 업데이트하고 끝나버린다.즉 음수사이클을 검사하는 로직이 없다.N-

🙋 벨만-포드 알고리즘 사용! 틀렸습니다를 받았다.에지를 체크할 때 시작 노드가 양의 사이클에 속하면, 도착 노드도 양의 사이클에 속하도록 해야한다. (무수히 많이 반복되면, 양의사이클이 결국 영향을 미치기때문이다)값을 업데이트하는 수식으로 검사하기 전에 if(di

🙋🏻‍♀️ 벨만-포드 사용!벨만-포드 알고리즘을 이용해 코딩을했는데, 예제 1의 결과가 "YES NO"가 나와야하는데 나는 둘 다 YES로 나왔다.그러고 생각해보니, 문득 의문이 들었다.벨만-포드는 최소거리를 구해주는것이기때문에, 출발 노드의 거리를 0이라 가정하면

완전탐색은 너무 오래걸리며, dp의 사용조건인 '겹치는 부분 문제'와 '최적 부분 구조'가 다 성립하므로 DP를 사용해 풀었다.💁‍♀️ DP 사용!테케는 다 맞았는데, 틀렸습니다를 받았다.질문게시판에서 나와 답이 다르게 나온 예외 테케를 발견했다!내 코드대로라면 pa

💁‍♀️ DP 사용틀렸습니다를 받았다.타입의 범위문제였다....int -> long으로 변경했다.어이없어할게아니다! 아주 중요한 이슈다. 결국 이것도 실력이다.

💁‍♀️ DP이용! - LCS 유형전형적인 LCS 대표문제위 코드를위 코드로 수정할 수 있다.즉, String을 받은 변수를 따로 지정하지않고, 받는 동시에 toCharArray()를 이용해 배열에 문자를 각각 넣어 문자 배열로 만들 수 있다.

💁‍♀️ DP 사용!틀렸습니다를 받았다.반례를 발견했다.dp의 이중for문 속 첫번째 조건문 조건이 잘못됐었다.1일때에 실행할 수 있도록 아래와같이 조건문을 짰었는데,if(lcs\[i]\[j] == lenChar) 생각해보니 숫자가 업데이트되므로 2,3...의 수가될

💁‍♀️ dp이용!이 문제는 dp로 접근하는것을 몰랐으면 못풀었을것같고, 또 dp인걸 알고있음에도 점화식을 어떻게 세워야할지 감이오지않았던 문제이다.📌점화식을 구하기 막막할 때는 동적 계획법의 특징을 다시 한 번 떠올려보자!📌부분 문제를 구해 큰 문제를 해결하는

💁‍♀️ 비트마스킹 + dp(TSP) 사용! 이 문제는 어떻게 풀어야할지 감이오지않았다.시간초과를 받았다.다양한 블로그 코드도 돌려보고 질문게시판도 찾아본 결과 다양한 사람들이 시간초과문제를 겪고있으며, 1년전 코드도 시간초과가 뜨고 해결되지않은 케이스가 많은걸로 보

💁‍♀️ dp 사용!너무 어려워서, 다시 공부해야할 것 같다시간초과를 받았다.최악의 경우에 약 250000000000 + ... 의 시간복잡도가 나오기때문에 3초는 훨씬 넘는다.매번 dp수행때마다 queue에 값을 저장하고, dp가 끝난 후 또 for문을 돌며 이 값

💁‍♀️ 스택 이용!N의 최대크기가 1,000,000이므로 반복문으로 오큰수를 찾으면 제한 시간을 초과한다.스택에 다음 아이디어를 추가해 이 문제를 풀어보자이 문제는 아이디어를 알고나서도 잘 이해가 안됐던 문제이다.스택에 새로 들어오려는 수가 현재 스택의 top에 존

💁‍♀️ DP 사용DP를 사용한다지만 처음에 규칙발견하기가 조금 힘들었다.가로의 길이만 변해서 그 안에서 규칙을 발견하려했는데, 처음에는 1,2,3을 조합해서 가로길이가 되는 경우의수를 구한 후 1,2,3에 해당하는 값을 가지고 어떻게하려고접근했었다.예를들어 가로가

💁‍♀️ DFS 사용!"임의의 노드에서 가장 긴 경로로 연결돼있는 노드는 트리의 지름에 해당하는 두 노드 중 하나다."우선 임의의 가장 긴 경로를 찾은 후, 해당 경로의 끝에서 반대로 다시 한 번더 탐색을 수행결국 처음에 임의의 긴 경로를 찾는것은 정확한 출발노드를

한 번에 맞았지만, 테스트케이스에서 결과가 달라서 조금 헤매기도했고, 처음에는 Queue를 이용해서 풀려고했는데 트럭이 얼마나 이동했는지를 큐 안에서 어떻게 표현할까를 고민하다가 배열 2개 사용하는 방식으로 바꾸었다.그래서 다른 풀이를 찾아보고 공부한다. Queue를

🙋🏻‍♀️ 우선순위 큐 사용! 골드4라서 조금 어렵겠다 생각했는데, 아니다.생각해보면, 파일은 무조건 2개씩 합쳐지기때문에 어떻게 합치든 횟수는 고정이다! 동일한 횟수에 최소비용을 구하려면, 각 횟수마다 합이 최소가 되도록하면된다.따라서 우선순위 큐를 이용한다! 테

테스트 케이스는 맞았는데, 틀렸습니다를 받았다.를 넣으니, ]만 출력됐다.즉 isNone()이 true로 동작해서 error를 출력했다는말이다.근데 문제를 다시 살펴보니,, 조건을 헷갈렸다.값이 비었을 때 (isNone == ture) error를 출력하는게 아니라,

테케 하나 돌려보고 맞았길래, 그냥 제출했는데 2,3번 테케에서 다른답이 나왔다.visited\[head.x]\[head.y] = true; 에서 '행'이 y, '열'이 x이어야하는데, 그 반대로 적어뒀다.visited\[head.y]\[head.x] = true;이것

https://www.acmicpc.net/problem/2179예제 입력1예제 출력1