코테 문제들

📝\_0️⃣ 입력1️⃣ 출력2️⃣ 예시힌트 A와 B의 경로는 무조건 만난다.3️⃣ 나는 어떻게 문제를 풀었을까❔ 풀이 4️⃣ 코드 알고리즘 분류 : 탐색, 문자열

📝\_0️⃣ 입력1️⃣ 출력2️⃣ 예시힌트 A와 B의 경로는 무조건 만난다.3️⃣ 나는 어떻게 문제를 풀었을까❔ 풀이 4️⃣ 코드 알고리즘 분류 : 탐색, 문자열

📝\_2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×17 직사각형을 채운 한가지 예이다.0️⃣ 입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주

✅ 키워드

` ✅ 키워드

✅ 키워드

| 코드 1 | 코드 2 | | :---: | :--- :| | | | | | |

✅ 키워드 ✅ 코드

사용할 부분 문자열 길이 : 8 이라면,가장 처음 시작하는 ( 0-8 ) 구간과 ( 1-9 ... 끝 ) 구간까지로 나눠준다.처음 반복까지두 번째 부터 마지막 반복까지👾 주의할 점업로드중..

아래 두 개의 while 문은 완전 다르므로 주의하자 !첫 번째 루프는 num 이 currentNum보다 작거나 같을 때 숫자를 스택에 추가한다.두 번째 루프는 num 이 currentNum과 정확히 같을 때 만 수행한다.

✅ 큐

들어오는 두 개의 값 o1, o2o1 의 절대 값이 o2 의 절대 값보다

입력 n 의 최대가 1,000 이므로 n제곱 알고리즘 ( 버블 정렬 ) 으로 풀어도 되는 문제인 걸 인지하자. ( 1,000,000 < 1 억 )직접 손으로 그려보는 게 가장 좋으므로 한 번 그려보자.

map에 잘 저장된다.크키가 2일 때, map.get(0), map.get(1) 하면 key값이 0인 것의 value, Key 값이 1인 것의 value를 가져오기 때문에 인덱스로서의 접근은 불가하다.map 사용이 불가하다.

앞의 입력은 단순히 결과 확인을 위해 넣은 데이터이다.사용했던 코드는 solution 함수안의 코드이다.

✅ 문제 이해 이 문제는 양방향 연결 리스트인 것을 주의하자. [ 원본 그래프 ] 그래프 1: 1-2-5-1 그래프 2: 3-4-6 [ 인접 리스트 ] 1 -> 2, 5 2 -> 1, 5 3 -> 4 4 -> 3, 6 5 -> 1, 2 ✅ Dfs 과정을 이해

이 문제는 최대 데이터 크기가 100 으로 작기 때문에 시간 제한을 별도로 생각하지 않아도 된다.문제의 요구사항은 지나야 하는 칸의 수의 최솟값을 찾는 문제이다.이는 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 발견하는지를 구하는 것과 동일하다.dfs, bfs를

✅ 이진 탐색 (binary search) ✅ 코드

업로드중.. ✅ 자료형 범위 업로드중.. 업로드중.. ✅ 코드

이 문제에서는 1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수 라는 조건이 있으므로 탐욕법을 선택해도 반례가 존재하지 않는다.for-each문에 주의하자.

이 문제는 '-'로 문자열을 한 번 나눈 후, 나눈 문자열을 한 번더 '+'로 나누어 +끼리 모두 더한 후 - 연산을 실행하면 된다.String 문자열을 + 기호로 나누고 싶을 때,java.util.regex.PatternSyntaxException: Dangling

업로드중..배열 안의 값은 조합의 경우의 수이다!i=2 부터 n까지j=1부터 i보다 작을 때 까지배열은 n+1 크기5C2 => 0번부터 5번째 행 2번째 열 인덱스!그려서 이해해보자.업로드중..업로드중..

링크 : https://www.acmicpc.net/problem/2747 업로드중.. ✅ 탑 다운 코드 업로드중.. ✅ 바텀 업 코드

문제 링크 : https://www.acmicpc.net/problem/11726 업로드중.. ✅ DP 이 문제는 4를 다 채웠다고 가정하고 5를 구하는 부분 문제로 나눌 수 있다. dp로 풀 수 있다는 판단이 선다. 그러면, 점화식을 구해야 한다. 점화식 D[

https://www.acmicpc.net/problem/1929 이 문제는 일반적인 소수구하기로 풀면 시간 초과가 발생한다. (나머지 연산을 사용) ✅ 에라토스테네스의 체 원리르 손으로 따라가보자. 1은 소수가 아니므로 값에 0이 들어가야 한다. 업로드중.

세 개 노드 사이의 최단 거리를 구하는 알고리즘이다.다익스트라벨만-포드플로이드-워셜업로드중..

그래프를 표현하는 3가지 방법 엣지 가중치가 없는 그래프 가중치가 있는 그래프 엣지 리스트는 벨만포드나 크루스칼 알고리즘에서 사용한다. 특정 노드와 관련되있는 엣지를 탐색하기란 쉽지 않다. 즉, 노드 중심 알고리즘에서는 사용하면 전체 노드 중에 해당 노드를 탐색

노드 = 동그라미 수 (정점) 엣지 = 선의 수 (간선) ✅ 구상 ✅ 코드

합집합 연산 -> union 연산 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산 -> find 연산 ( 대표 노드 찾기 ) 입력이 크니까 경로 압축이 필요한 전형적인 유니온 파인드 문제이다. ✅ 유니온 파인드 손으로 따라가보자 ✅ 문제 어려운 문제일수

✅ 위상 정렬 ✅ 코드

너무 간단한 문제이다.각 사람의 인출시간 + 각 사람의 대기시간의 최소갑을 구하면 된다.내림차순 정렬해주면 쉽다.

문제들을 풀면서 느낀 점이 있다.생각한 풀이를 속으로 따라가면서 그에 맞게 구현을 하면 쉽다. ( 무슨 말인지 아는 사람은 알거다! )처음에 구현한 코드는 아래와 같은데 반례가 있다.처음에 들어올 때 (3,3) (2,3) (1,3) 이 들어온다면(3,3) (2,3) (

✅ 코드

리터당 기름 값이 '내림차순'일 경우에 주유하면 된다.즉, 5 2 4 1 에서 5 다음 2는 내림차순 이므로 5와 2가 선택되고, 그 다음의 수 4는 내림차순이 아니기 때문에 마지막에 선택되었던 내림차순 수인 2로 계산되어야 한다. (1은 더이상 갈 도로가 없기 때문에

입력값이 너무 크다 (4,294,967,295)아이디어는 -1, -2 씩 빼주면서 만약에 뺀 값이 i 값보다 크거나 같으면 계속 반복을 해준다.테스트 케이스는 잘 통과하는 데 문제가 뭐지..!아 입력값을 long으로 받아야 하는 구나!int 형이 몇 자리까지 되는지 한

b의 값이 2로 나누어지면 나누고, 안 떨어지면 마지막 1을 지우는데각 과정에서 계산한 값이 a랑 같으면 그 즉시 cnt를 출력하고 return;다르면 -1 출력애초에 2로도 안 나누어 떨어지고 1로도 못 지우면 -1아래 while문의 시간 복잡도는 O(log b)입니

각각 입력하면 결과값이 잘 나오는데 같이 입력했을 때 결과값이 안나온다 -> 초기화 안해줌아이디어 다 떠올렸는데 실제 구현에서 막혔다 -> 누가 이기나 해보자 😤바보다. 각 테스트 케이스마다 리스트를 초기화줘야한다.자바에서 ArrayList와 같은 동적 배열은 한 번

업로드중.. 업로드중.. 슬라이딩 윈도우는 이중 반복문이 필요없다. 알아두자

https://www.acmicpc.net/problem/2531 ✅ 바로 앞에서 풀었던 문제에서 더 구현이 더해진 문제였다. 앞에꺼를 완전히 이해하고 풀어서, 이번 문제는 스무스하게 풀었다. 레벨을 차근차근 풀면서 느낀 점이 있다면, 낮은 레벨에서 풀었던 문제가

탐욕법 문제를 풀 다 보니까 내림차순 오름차순으로 푸는 문제가 상당히 많은 것 같다. 그리고 min, max를 사용해서 이중 반복문을 사용하면 silver 3이상 정도, 그냥 반복문을 사용하면 silver 4 정도 되는 것 같다. 반복문 + 제약조건이 있다면 si

\++, -- 연산은 자칫하면 실수할 수 있으므로 주의하자.

내가 머릿속으로 생각한거 구현하려다 도저히 못 할 것 같아서 풀이를 봤는데, 보길 잘 한 것 같다.아이디어가 이렇게 참신할 수가;!!진짜 빡 1시간 30분 정도 생각, 풀어보고 머리가 뱅글뱅글 돌면서 '와 이건 구현하기 너무 빡센데?' 싶으면 풀이 보자.참신한 아이디어

✅ 윈도우 for문 for문이

✅ 코드

이때까지 푼 문제에서 틀렸던 이유들 생각나는 거구현 실수 빼고메모리 초과시간 초과자료형(int) 초과부분 구간이 전체 구간보다 더 커서 인덱스 초과한 번 틀렸었는데 바로 int를 long으로 고칠 수 있었다.이번 문제는 한 5분만에 푼 듯.long,max는 웬만하면 l

✅ 구간 N(1 ≤ N ≤ 100000)개의 얼음 양동이들이 xi(0 ≤ xi ≤ 1,000,000)좌표마다 놓여 있고 1 ≤ K ≤ 2,000,000 이므로 슬윈을 할 때 k의 최대를 조건을 걸어주어야 한다. 구간이 (2*k)-1이면 4,000,000인데 좌표는

✅ 이어지는 구간 이 문제는 위의 회전초밥 문제의 쉬운 버전같다. 원형탁자에서 k개를 고르는 문제이므로, 배열의 마지막이 끝난 게 아니고 앞의 배열로 연결해서 연속되게 설정해줘야 하는 문제다. 회전 초밥에서 한 것처럼 배열을 늘리지 말고 나머지 연산을 사용해서 구해

소수점이 문제인가 싶어 힌트에서 처럼 소수점 3째자리만 나오도록 했다.근데 왜 틀렸지???????????값을 그냥 정수로 바꿔줬는데 맞았다.실수 연산을 하면 나눌 때 오차가 조금씩 생격서 그런 거 같다.

int, long 보다 더 큰 수를 저장하는 class리스트처럼 값을 초기화해주는 과정이 필요하다.

각 케이스에 대해서 { 입력받은 경우의 수 + null(선택안함) } 의 갯수를 구한다. 케이스들 끼리 곱한다. 알몸인 경우인 1을 뺀다. 종류가 겹치지 않는다고 했으므로 각 키는 고유한 성질이 있는 hashmap을 사용하면 된다. ✅ HashMap Hashm

조합문제라고 생각하면 nCr= n-1Cr-1 + n-1Cr 이 떠올라서 이걸로 어떻게 풀지? 라고 생각을 무의식적으로 하게 되는 것 같다.조합 공식을 쓰는 문제도 있고 아닌 문제도 있다.그래서 조합 공식이 적용이 안되면 빨리 다른 방법을 떠올리는 게 좋다.오름차순인 숫

✅ 코드

이 문제를 딱 보자마자 뽑는 갯수가 더 많다고?그러면 뽑는 갯수를 n으로 생각하고 문제를 접근해보자. 라는 생각이 들었다.

교차점 1개 -> 선분 2개 필요선분 3개 -> 꼭짓점이 4개 필요6각형 => 꼭짓점 6개 중에 4개를 뽑는 개수 (교차점 1개가 몇개 나오는지 알 수 있다.)

✅ 방법

✅ 세팅 ✅ DFS ✅ BFS dfs와 달리 bfs는 재귀 함수로 구현할 수 없으므로 큐를 이용하여 구현한다.

bfs로 구현하였다. ✅ 트리의 지름을 찾는 알고리즘 참고 링크 : https://blogshine.tistory.com/111 **임의의 정점(예: 정점 2)에서 최장 거리의 정점(예: 정점 5)을 찾고, 그 최장 거리 정점(예: 정점 5)에서 가장 최장 거

✅ 방문 배열 초기화 각 노드들이 dfs를 실행하기 전에 방문 배열을 false해주는 것과 dfs가 끝난 후에 방문 배열을 false해주는 것의 차이가 뭘까.! -> dfs가 끝난 후에 방문 배열을 false해주면 밑에서 한 칸씩 위로 올라오는 코드이고, 각 노드

초기화를 하지 않으면 null로 setting된다.배열 정렬

총 2문제인데 2문제 다 맞아야 PASS임! 세 시간에 두 문제, 경험상 못 뚫을 정도는 아닌 것 같다. 그래도 실버 상위권에서 골드 정도는 풀어야 하는 수준이다. ✅ 1번 문제 ✅ 2번 문제 [ check ] 문제 이해 ok. 배열이나 리스트에 입력받고 저장하기

✅ 그리디와 DP 동전0 을 풀 때 그리디로 풀었는데, 그리디로 풀려면 반례가 없어야 한다고 했다. -> 동전이 배수, 약수 등의 어느정도 규칙이 있을 때 접근 가능한 알고리즘인 걸 빨리 눈치채고 그리디가 아닌 다른 방식으로 접근해야 함. -> DP를 사용함 (아이

파스칼의 삼각형을 2차원 배열로 만들 수 있으면 된다. 바텀 업 방식을 사용했고, 바텀 업은 재귀와 달리 이중 반복문으로 2차원 배열을 채워야 한다. ✅ 코드

1) 주어진 입력까지 dp 배열 생성2) dpi = i에서 1로 만드는 데 걸리는 최소 연산 횟수3) 기저 사례 : dp0 = 0, dp1 = 04) 점화식동전 2와 달리 if 문을 사용하므로 배열의 범위를 벗어나는 것에 대해서는 고려하지 않아도 된다.구하지 못하는 경

예제가 많다. 탑 다운이랑 뒤에서 부터 접근하는 문제랑 같은 말인가.?! ✅ 점화식 ✅ 코드

이 문제는 경우가 2가지다.자리에 0을 두는 경우와 자리에 1을 두는 경우앞에서는 1차원 배열 dp를 계속 생성했기 때문에 1차원 배열로 어떻게 점화식을 세워야 할지 고민했는데2차원 배열로 두면 2가지 경우의 수에 대한 점화식을 생성할 수 있었다.y축은 0과 1이다.이

✅ 코드

✅ 코드

✅ 세팅 ✅ 코드

✅ 코드

방문 확인은 for-each문에서

모든 bfs에 대해서 실행하므로 visited배열을 bfs선언할 때 앞에 선언해주어야 함!왜 나는 거지!??찾아보니,,이 문제는 할 때마다 시간 초과가 나올 수도 있고 아닐 수도 있다고 한다.이 경우는 시간 복잡도가 코드 제한시간에 걸쳐서 제출했을 때, 되는 경우도 있

✅ 이전과 다른 점 bfs(0,0)에서 시작하면 다른 0을 만나면 끊긴다. 같은 단지가 다 다른 숫자로 바뀐다. bfs(i,j)에서 시작하면 전체 탐색은 된다. 하지만, 같은 단지가 다 다른 숫자로 바뀐다. ✅ 필요한 것 ✅ 코드 제일 처음 시작점 (1) 을

✅ StringBuffer 사용

✅ Long 선택 기준 ✅ 틀린 코드 ✅ 코드

하다가 맞왜틀 이틀 동안 한 것 같은데, 해탈하고 정답인 코드 따라서 그냥 쳐보고 결과 확인하면서 동작원리 파악하다보니까 틀린 부분을 알 수 있었다. 맞왜틀이 너무 시간이 오래 걸린다 싶으면 정답인 코드 따라쳐보고 파악해보자! ✅ bfs가 한 번만 실행되는 이유

ArrayList에 x,y를 저장하고 겹치는 부분을 제거하는 방식으로 구현하려고 했는데, 구현이 어려워서 도대체 어떻게 푸는 걸까 싶었다.다른 사람들은 0부터 100까지 이중 배열을 만들고 색종이가 들어오는 x,x+9와 y,y+9까지를 채우고 만약에 채워졌다면 방문하지

점화식을 세우는 게 가장 중요한데, 내가 세운 점화식은 그 전 dp의 값에서 +1을 해주는 거였다.근데, 한 번 더 깊게 생각해서 풀어야 하는 문제였다.그래서 골드구나!일단 DP는 1차원 배열 아니면 2차원 배열인 걸 염두에 두고 1차원 안되면 2차원으로 두는 게 좋을

check함수를 따로 빼서 구현해주는 게 더 좋다.

일단 바보 같은게 max는 i마다 갱신이 필요하므로 for문 안에 들어가야 했다!!변수 위치 놓는 거에 신경쓰자..!dpn = n 번째 일 때 들어갈 수 있는 가장 긴 부분 수열계산은 0에서 n-1번째 중에서 n번 째보다 큰 수 중에서 가장 길이가 긴 부분 수열 + 1

이 문제는 0과 1이 서로 같은지 비교해주어야 하므로 문자열로 입력받는 것이 equals를 사용할 수 있어서 편리하다. ✅ 규칙 그리디 (탐욕법, greedy) 하나의 규칙을 적용해 최선의 답을 도출해낸다. 규칙을 찾아보자. ✅ 코드 substring은 다 소

✅ 코드

주어진 문제에 대해 제한된 시간과 메모리 내에서 문제를 해결하는 행위를 일컫는 말 Cpu 는 1 초간 약 1 억의 수를 연산할 수 있다고 가정하고 문제를 접근하는 것이 좋다.입력 N에 대해서 시간 복잡도가 O(n) 이라면 입력 N은 0 <= N <= 100

0101 출력 -> %04d

✅ 구현 ✅ 코드

그리디가 앞에서 부터하는 그리디가 있구뒤에서 부터하는 그리디가 있더라

거스름돈이 잔돈의 단위보다 큰 금액이라면, 거스름돈에서 잔돈의 단위를 뺀다.거스름돈이 잔돈의 단위보다 작다면, 잔돈의 단위를 감소시킨다.거스름돈이 0이 되면 while문을 탈출해야 하므로 while문의 조건식이 change > 0 이 되어야 함에 유의하자

이렇게 푸는 방법은 생각지도 못했다.어렵게 푸는 방법 생각하고 있었는데,, 빨리 알아서 다행이다.

✅ 코드

현재 꽂아져 있는 플러그가 (2,3)이고 현재 1번 기기를 사용하기 위해 플러그를 하나 빼야한다고 하자. 2번 기기는 5차례 이후에 다시 사용하고 3번 기기는 10차례 이후 다시 사용한다고 하면, 2번 기기를 선택할 경우 5차례 이후에 다시 플러그를 빼야 하는 경우가

✅ 점화식 ✅ 코드

✅ 점화식 ✅ 코드

생각보다 쉬웠는데!! 반복문에서 j를 변수로 써놓고 i++를 하고 있었다..ㅎ이런 경우에 j말고 i랑 다른 k나 p같은 변수로 둬야겠다!

위에 푼 카드 구매하기에서 한 번 더 생각해여하는 게, 0일 때 최소값은 항상 0 이므로 반복문에서 dpi = pricei 로 먼저 설정해두자!

완전 탐색의 기초는 3중 for문 부터 시작하는 것 같군!

테스트 케이스는 맞게 나오는데, 시간 초과가 나네?아...! n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력하라고 되어있었군!이 코드의 문제가 뭘까테스트 케이스 마다 dp배열을 계산하게 된다. 만약에 테스트 케이스가 10

자리수 계산을 할 때 substring으로 할려고 했는데, 100이나 10으로 나눈 나머지를 사용하는 방식이 더 좋은 것 같다.이 아이디어 외우자!그리고 boolean 배열 사용하는 것도 익숙해져야 한다.

이 문제는 dpn-1의 값이 가장 긴 증가하는 부분 수열이 아니다!dpn-1 은 n번째 숫자가 가질 수 있는 가장 긴 증가하는 부분 수열이고,우리가 구해야 할 것은 전체 경우의 수 중 최댓값을 찾는 것이다!그리고 하나 더 유의해야 할 게 max 값을 찾는 것으로 dp

구분자들 사이에 |(파이프라인)을 넣어주면 된다.예시

켘 어려워,,구현하기 정말 빡세다.simple한 오름차순은 sort로 해결가능한데,hard한 오름차순은 queue로 해결해야 할 것 같다.이거 출력하는 것도 빡세고ㅠ

이 문제는 1 : ArrayList, System.out.print -> 시간초과2 : LinkedList, sout -> 시간초과3 : ArrayList, sout, Iterator -> 시간초과4 : LinkedList, sout, Iterator -> 시간초과5

업로드중..switch-case문 break랑 default 조심!

FILOFIFOFIFO + LILO

퀸은 상 하 좌 우 대각선으로 움직일 수 있다. 즉,* 같은 행 같은 열 대각선*에 놓을 수 없다는 것이다. 1차원 배열은 board를 선언했고 인덱스 번호는 각 행의 번호를 의미하고, 배열의 값은 각 행의 열의 번호를 의미한다. 시작 ) 0,0 부터 시작한다. b

처음에 떠오른 방법은 열,행,대각선 각각 비교한 후자리에 넣을 수 있는 숫자 후보들을 구한다.그 후보들이 1개이면 그 자리를 먼저 채운다.그리고 나머지 자리에 대해서 비교하면서 채운다.보통 나는 스도쿠를 위와 같은 방식으로 푸는데 코드로 로직을 짤 때는 고려사항이 너무

문제 링크 https://www.acmicpc.net/problem/14620

참외밭https://www.acmicpc.net/problem/2477

문제 링크 : https://www.acmicpc.net/problem/16401처음에는 과자의 수가 조카 수보다 크면 마지막 인덱스에서 조카 수만큼을 뺀 인덱스가 최대 길이가 되는 줄 알았는데2 61 1 1 1 1 100라는 반례가 있었다. 내가 생각한 것처

visitedi = 0 이라는 코드를 놓치면 안된다!!!