코테준비

동빈나 코테 준비 에서 내가 배운 알고리즘 상, 최단 경로 알고리즘으로는 "디익스트라 알고리즘" 이 있다. 현재 vertex의 개수는 1<=v<=20,000 이기 때문에 개선된 디익스트라 알고리즘을 사용해야 한다. (반복하는 상황 속에서 방문하지 않은 노드중

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램 작성하기. 구현하기 문제인데 \_ 떠오르는 건 수학적인 접근법 밖에 없었다.왜냐하면 모든 경우 때마다 적어도 하나의 3이 있는지

문제조건루트 없는 트리 → Graph가 생각나는 형태.Root가 없는 트리이지만, Root를 1이라고 정하는 경우, 각 노드의 부모를 구하는 프로그램.일단 여기서는 "트리에서의 Search"개념이 필요하다.출력으로는 "각 노드의 부모 번호"를 "2번 노드"부터 순서대로

절단기에 설정할 수 있는 높이는 0이상의 정수.적어도 M미터의 나무를 얻기 위해 , 절단기에 설정 할 수 있는 높이의 최댓값 구하기.설정가능 높이로 0도 가능하기 때문에, 나무의 높이의 합이 항상 M보다 크거나 같으면, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다

priority queue나 quicksort를 사용시 O(nlogn)의 시간 복잡도를 가지며 정렬 가능.반면 버블정렬같은 경우, O(n^2)의 시간복잡도를 가짐. 따라서 cpp의 priority_queue를 사용해 보았다. cpp의 priority_queue는 max

딱히 할 말이 없는 문제.아주 쉬운 문제다. 2차원 좌표평면 문제이다. L방향 이동은 8가지의 경우를 생각할 수 있다.각 이동에 대해 row방향, column방향으로의 이동을 list로서 작성해 놓고, 이동을 할 때의 "좌표"가 어디인지를 파악(8x8공간을 벗어나지 않

character를 하나씩 받으면 된다. alphabet 정렬을 하기 위해 , < algorithm >을 사용하려함. 그를 위해서 vector 또한 사용함.

저런 식으로 정해진 재귀함수 형태가 나오는 문제의 경우, 다이나믹 프로그래밍 방식이 먼저 떠오르게 된다.

백준 1021번

삽입과 제거를 LIFO 에 따라서 한다. 즉 마지막에 넣은 object를 먼저 제거한다. Last Input First Out에 따른다는 것. JAVA interface definition는 Java에 내장된 java.util.Stack과 조금 다르다. 당연한 말이지만

부분수열에 속한 원소를 모두 합한 것이 S가 되는 부분수열의 개수를 출력.부분 수열이라는 것은 결국, 어떤 시작점부터 어떤 끝점까지 연속한 원소들의 집합.전체 탐색을 해야하는가? 시간제한이 2초고, 1<=n<=20 인 것으로보아 전체 탐색을 고려한 문제 같

\*\*\*모든 노드에서 다른 모든 노드까지\*\*\*의 최단 경로를 모두 계산한다.Floyd - Warshall 알고리즘은 다익스트라 알고리즘과 마찬가지로 “단계별로 거쳐가는 노드를 기준”으로 알고리즘을 수행한다.다만, 매 단계마다, “방문하지 않은 노드 중” “최단

부잣집 문제인듯 문제풀이 처음에 문제가 이해가 안 되었다. 하나의 공유기를 사용가능한 수평거리를 알려줘야 하는게 아닌가 생각했는데, 그게 필요없는 문제였다. 어쨋거나, N개의 집에 C개의 공유기를 설치하는

가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램 . 대,소문자를 구분하지 않는다.단어의 길이 ≤1,000,000출력 : 가장 많이 사용된 알파벳을 대문자로 출력여러 개 존재 시 ? 를 출력 이 문제는 대소문자를 구분하지 않기 때문에 a,A를 index 0으로 생각

정렬 알고리즘을 또 까먹어서 가장 기본이 되는 Bubble sorting을 하고 싶어서 풀어본 문제

코딩테스트 연습 - \[1차] 추석 트래픽초당 최대 처리량은 응답 완료 여부 상관x이 임의 시간부터 1초간 처리하는 요청의 최대 개수를 의미한다.고정길이 2016-09-15 hh:mm:ss.sss 처리시간T처리시간 T는 최대 소수점 셋째 자리까지 기록 하며 뒤에는 초

이것 참 뭔가 노드의 관계가 주어진 것 같다. 이는 Directed Graph로 풀 수 있을 것 같다풀이법 생각"정확하게 순위를 매길 수 있는 " 선수의 수..정확하게 순위를 매길 수 있다는 것은. 모든 노드들과의 확실한 관계가 있는 것을 의미하는가?????MATRIX

문자열에서 같은 값이 "연속"해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있다.그 문자의 개수와 반복되는 값으로 표현 —> "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만

"영역" —> 상하 좌우로 연결된 같은 색상의 공간.평소 풀던 BFS, DFS 문제와 같다 .구해야 하는 것 : "영역의 개수" , "가장 큰 영역의 넓이는 몇?"풀이법여기서 "연결된 같은 색상의 공간 " 에서"연결" 범위 : —> 상 하 좌우 . (대각선 포함x)보

이동 : 상하좌우로만 가능하다.(0,0) —>(m-1,n-1)까지 이동 하려 한다.높이가 더 낮은 지점으로만 이동하려고 한다.이 때 이동할 수 있는 경로의 개수 를 구하기문제 해결과정bfs를 사용하려고 한다.이 문제는 "경로의 개수" 를 구해야 하기 때문에, visi

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.Merge all the linked-lists into one sorted linked-list a

문제에서 주어지는 것은 N 밖에 없다.출석, 지각, 결석출석 : O결석 : A지각 : L문제 조건개근상에서 제외되는 경우지각을 2번 {이상}결석을 세번 {연속}💥💥💥정답을 1000,000으로 나눈 나머지를 출력한다 💥💥💥구해야 하는 것N이 주어질 때, { 개

늘지 않는 실력에 맘이 쪼끔 힘들어서 쉬운거 들고 왔다! JAVA 로 코테를 보다보니 IDE를 쓰지 못해 아주 극한의 상황이라고 느껴진 적도 있었다. 그날 이후로는 IDE를 쓰지 않고 테스트페이지에서 바로 풀어보려는게 조금은 익숙해진 것 같다. The DNA sequence is composed of a series of nucleotides abbre...

N개의 섬이 존재. 이들 중 "몇 개의 섬 사이에 다리"가 설치되어있다."두 개의 섬"에 공장을 세워 두고, 물품을 생산하는 일을 한다.a공장에서 b공장으로 물품 수송할 일이 생기곤 한다.다리마다 중량제한이 있어, 무턱대고 물품을 옮길 수 없다. 만약 중량제한 초과하는

크기가 20이기 때문에 완전탐색을 해도 괜찮다.lock이 n, key가 m 임200 x 200 x 4 가지 경우가 나올 거임. ( 각 key를 한 칸씩 이동시켜나가며 convolve시켜나간다고 생각하면 n x n x 4가지 경우가 나올 것이기 때문임)그런데 n은 최

14890번: 경사로지도의 각 칸에는 "높이"가 적혀져 있다."길" 이란 "한 행 전부 " 또는 " 한 열 전부" 를 나타낸다 → 즉, 한쪽 끝에ㅓ, 다른쪽 끝까지 지나가는 것.길을 지나갈 수 있기 위해 :"길에 속한 모든 칸 " 의 높이는 "같아야 " 한다. 또는,

50분걸림특정범위의 보석을 모두 구매하되, 특별한 목적을 달성하고 싶다.진열된 "모든 종류의 보석"을 "적어도 1개 이상"포함하는 "가장 짧은 구간"을 찾아서 구매"연속된 구간"이어야 한다.구해야 하는 것 : "모든 보석을 하나 이상 포함" 하는 "가장 짧은 구간"을

2096번: 내려가기(소요시간 : 48분..)처음 숫자 선택 : 3개의 숫자 중 하나를 고른다.첫 줄 → 마지막 줄 까면 끝나는 놀이다음 줄로 넘어 갈 때의 제약 조건바로 아래칸 OR "바로 아래칸에 인접한 칸으로만 "근데 각 줄 당 세개의 칸 만 존재.얻을 수 있는

1918번: 후위 표기식후위 표기법의 장점?중위 표기법(일상적으로 쓰는 연산식은 중위 표기법으로 표기된 것) → "덧셈"과 "곱셈"의 우선순위 차이가 있음. → 왼쪽부터 차례로 계산하면 잘못된 결과가 나온다.후위 표기법→순서를 적절히 조절하여 순서를 정해 줄 수 있다

트리는 { 사이클 없는 무방향 } 그래프다. → 따라서 node가 N개라면, edge는 N-1개Tree에서는 어떤 두 노드를 선택해도, 둘 사이 경로가 항상 하나만 존재한다.Tree에서 { 어떤 두 노드를 선택해 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우 }

1865번: 웜홀음수간선이 존재하는 문제였다. bfs로 고민하니 뭔가 cycle이 생기고 왔던 노드를 다시 지나고 하는것이 어떻게 해야할지 모르겠었다. 심지어 최단거리 문제를 푼지 오래되어 디익스트라도 생각나지 않았었지만, 디익스트라도 아니었다. 처음으로 벨만포드문제를

11657번: 타임머신이 문제는 음수간선이 존재하는 그래프에서 최소비용경로를 구하는 문제로 벨만포드알고리즘을 사용하려고 한다. 이 문제는 시작점이 1로 주어져 있다. 1로부터 각 노드까지의 최소비용경로를 찾으라고 하고 있다.문제에서 " 시간을 무한시 오래전으로 되롤릴

13460번 구슬탈출2(삼성역량)삼성역량 특성상 +이 문제의 조건" 10번 이하로 움직여 빨간 구슬을 구멍을 통해 빼낼 수 없다면 -1 출력 " —> depth제한을 주었다."N과 M이 10이하"를 보면, 완전탐색을 이용 해도 되는 문제인 듯 하다. 백트랙킹 + bfs

13549번: 숨바꼭질 3수빈이의 현재 점 : N (수평선)동생이 위치하는 점 : K (수평선)수빈이는 걷거나 순간이동 할 수 있다.수빈이의 위치가 X일 때걷는다면, "1초" 후 x-1 또는 x+1로 이동하게 된다.순간이동을 한다면 "0초" 후, 2\*x의 위치로 이동

(2:25... ㅋㅋㅋㅋㅋㅋ)버튼 종류 : 0~9의 숫자, +(현재+1) , -(현재-1) 존재채널0에서 '-'를 누름 —> 채널 변화 ❌채널은 무한대 만큼 있으니 '+'에 대한 제한은 없는 상태.목표 채널 : N번주어지는 것 : 고장난 버튼현재 채널 : 100채널 N

솔직히 풀이하는데 오래 걸렸다. (2~3시간)16637번: 괄호 추가하기수식의 길이가 N0~9까지 정수, +, -, x 의 연산자로 이루어짐.정수로 시작 —→ (연산자 → 정수) 가 반복된다. =⇒ N은 홀 수 일 수 밖에.연산자 우선순위가 모두 같다. → 수식 계산

연속된 수들의 부분합 ! 이라는 것에서 Sliding Window나 Two pointer를 사용할 것을 생각해 볼 수 있다.그 합이 S 이상 인 것 중, 가장 짧은 것 의 길이를 구하라.나에게 더 익숙한 Sliding Window방식을 사용 - 증가시키다가,

14719번: 빗물고이는 빗물의 총량은 얼마일까?빗물이 전혀 고이지 않을 경우 0을 출력한다.h → row : 1이상 500이하w → column : 1이상 500이하각 블록의 높이는 0이상 h 이하근데 이차원 세계의 바닥은 항상 막혀있다.빗물이 고이기 위해서는 움푹

백트랙킹을 생각했다.a는 index 0, e는 index1로 생각하여 ,for문을 도는데 이전의 index이상만 선택가능하게 하였고현재 호출된 함수의 an이 n과 같으면 1을 리턴하도록 하여수를 세는 방법을 하였다.나는 단순히 백트랙킹을 사용하려 했다.a,e,i,o,u

\[프로그래머스\_카카오] 메뉴 리뉴얼orders에서 각 order에 대해 모든 조합을 생성한다. 각 조합에 대해서는, 해당 조합이 등장한 횟수를 저장한다. (HashMap을 사용한다) course에 있는 각 개수만큼의 길이로 이루어진 조합중, 가장 큰 값을 저장한 조

괄호의 짝 맞추기균형잡힌 괄호 문자열 —> '('와 ')'의 개수가 같은 경우여기서 짝까지 모두 맞으면 → "올바른 괄호 문자열"균형잡힌 괄호 문자열 —> 올바른 괄호 문자열로 변환하는 과정입력이 empty string —> 빈 문자열""을 반환문자열 w를 2개의

완전탐색 → 불가능. 50000 x 100000 → 500억이다따라서 든 생각 1. Hash or Matrix(다차원 배열 형태) 2. 이진탐색(lower bound)문제를 보고 위의 생각은 바로들었는데 Hash로 삽질 했다. 다른 분들은 Hash로 잘 푸시던데 나는

코딩테스트 연습 - 합승 택시 요금양방향 가중치 그래프다끝까지 둘이서 같은 택시를 타야한다고 생각했는데 그런 문제는 아니다."출발"~ "특정지점" 까지 같이 움직인 후 ,"특정지점" ~ "각자의 목표" 까지는 각자 움직인다 . (당연하다, 계속 같이 타고 다니는게 더

Sort Colors색이라고는 하지만, 어차피 정렬 함수를 사용하면, 0,0,1,1,2 이런식으로 정렬하게 된다. 따라서 그저 정렬을 구현하면 된다고 생각했다. 단순히 pivot을 첫 번째 원소로 하는 quicksort를 구현했다. \--> 매우 좋지 않은 효율 을 가

15724번: 주지수sx,sy,ex,ey 로 테스트 케이스가 주어진다. 직사각형 영역 시작 (x,y)와, 끝(x,y)의 좌표가 주어진다.영역이 주어질 때 마다, 매번 계산하는 것은 시간초과를 부를 수 밖에 없다. 영역의 최대 크기는 2^ 20 인데 , test case

\[백준]1695번 팰린드롬 만들기이전에 풀었던 문제인데 당시에 풀지 못해서 다른 사람 풀이를 봤었다. 다시 풀어보았다. 내 머리속에 항상 먼저 드는 생각은 투포인터이다....;.1\. left, right라는 두개의 포인터를 , 주어진 수의 sequence arr의

7662번: 이중 우선순위 큐일반적인 우선순위 큐는 우선순위가 가장 높은 데이터만을 추적한다. 하지만 이 이중 우선순위 큐는 우선순위가 가장 높은 데이터우서누위가 가장 낮은 데이터두 가지를 추적한다. 연산이 두 가지 있다. 데이터를 삽입데이터를 삭제우선순위가 가장 높은

최근 문제가 더더욱 안 풀리고 이전의 좋지 않은 습관들을 계속해서 고치지 못하고 있는 것 같다. 자소서를 쓰는 기간동안은 풀었던 문제를 다시 풀며 쉬운 문제를 추가적으로 하나씩만 더 풀어보려고 한다.벨로그에 포스팅을 했었던 문제라면 추가적으로 다시 풀며 느낀 점을 적고

네이버 웹툰 3번문제의 달팽이가 생각난다. 물론 다른 문제이긴 하지만, 이런 문제를 잘 풀지 못하는 것 같기에 풀어보려 한다. (역시나 한시간 걸렸다.) 이 문제는 silver1 문제다 1074번: ZZ 모양으로 탐색하려 한다. 배열의 크기는 2 ^ Nx 2^N 이다.

https://programmers.co.kr/learn/courses/30/lessons/42888(31분) "닉네임님이 들어왔습니다.""닉네임님이 나갔습니다."채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.채팅방을 나간 후, 새로운 닉네임으로

18870번: 좌표 압축수직선 위에 N개의 좌표 X1,X2,...,Xn 이 존재함.Xi를 좌표 압축 → Xi' 의 값은 X i > X j 를 만족하는 서로 다른 좌표의 개수와 같다.N은 100만 이하이다.각각의 Xi는 -10억 이상 10억 이하다.(시간 초과로 인해 멘

2263번: 트리의 순회Inorder, Postorder가 given되었을 때!!! preOrder를 구하기 Inorder : left chlid → 자신 → right childPostOrder : Left child → Right child → 자신 =⇒ 즉,

14500번: 테트로미노정사각형 4개를 이어 붙인 폴리오미노 → 테트로미노 문제에서 , 이러한 테트로미노에 어떤 종류가 있는지 알려준다.N x M 인 종이 위에 테트로미노 하나를 놓으려 한다.종이의 각 칸에는 "정수"가 하나 쓰여 있다.테트로미노 하나를 적절히 놓아,

각 datai는 다섯 글자로 구성된 문자열 A,C,F,J,M,N,R,T -> 8 사람 datai는 조건 : N~F=0 -> 즉 다섯 글자 datai.charAt(0) ,datai.charAt(2)는 사람 datai.charAt(1)은 항상

2638번: 치즈두 변이 공기와 접촉 → 즉, 하나의 칸에서 는 총 네 가지 방향으로 갈 수 있다고 생각 할 수 있는데 ( 문제 조건 상, 가장 자리에는 치즈가 놓이지 않는다!!!! ), 이 중 세 칸이 치즈와 접촉해 있지 않으면 → 녹는다.단, 이 때, 이런경우가 있

이 문제는 백준에서도 봤던 문제같다.(0:20)하나의 노드로부터 dfs, bfs등을 통해, 이 노드와 같은 네트워크에 속해 있는 노드들을 파악할 수 있다.이 때 visit을 체크한다visit되지 않은 노드로부터 또다시 탐색을 한다.시작 할 때에만 network의 수를

n의 음이 아닌 정수 a1,a1,,..an이 주어진다. 각각은 coordinate(i,ai) 를 나타내는 것임. 그 ai에서부터 수직선을 내려 긋는다. 가장 많은 물을 담고 있을 수 있는 두 개의 line을 찾아라. container의 좌측 line을 가리키는 left

9935번: 문자열 폭발폭발하면, 그 문자는 문자열에서 사라짐 + 남은 문자열은 합쳐진다.IF, 폭발문자열이 존재 → 모든 폭발 문자열이 폭발.남은 문자열을 순서대로 이어붙여 새로운 문자열 생성새로 생긴 문자열에 폭발 문자열이 포함되어있을 수도 있다이어붙인 결과로

코딩테스트 연습 - N으로 표현이 문제는 전에 풀어봤던 문제임에도 또 다시 풀지 못했다. (25분고민.. 오늘은 다시 푸는 문제임에도 어려움이 많이 느껴져 길게 고민하기가 힘들었다)지난번과 비슷한 상태였던 것 같다 . 따라서 다른 사람의 풀이를 빠르게 보았다. 동적 프

집안에 큰 일이 있었다.다시 잘 시작해봐야지 11779번: 최소비용 구하기 2양의 간선으로 이루어진 그래프에서, 최소비용을 구하기 위해서는 디익스트라 알고리즘을 보통 사용한다.일반적인 디익스트라 알고리즘에서는 "경로"를 출력할 수는 없었다.경로를 출력하려면 어떻게 해야

12851번: 숨바꼭질 2수빈이는 현재 점 N(0이상 10만 이하)에 있고, 동생은 점 K ( 0이상 10만 이하 )에 있다. 수빈이는 걷거나 순간이동이 가능하다. x-1x+12 \* x수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는, 가장 빠른

1:163190번: 뱀사과를 먹으면, 뱀 길이가 늘어난다.뱀이 기어다니다가 벽 or 자기자신의 몸 과 부딛히면 → 게임 ENDNxN 보드 위에서 진행되는 게임이 있다.몇 몇 칸 → 사과보드의 상하좌우 끝 : 벽맨 위 , 맨 좌측에서 시작 - 뱀의 길이 : 1맨

5639번: 이진 검색 트리전위순회 : root → left → right후위순회 : left → right → root 이진 검색트리를 전위 순회한 결과 가 주어졌을 때, 이 트리를 후위 순회한 결과 를 구하는 프로그램을 작성하라 같은 키를 가지는 경우는 없다

2573번: 빙산빙산은 1년마다 녹는다.빙산의 높이는해당 칸의 동서남북 네 방향으로 붙어있는 0인 칸의 개수만큼 줄어든다.단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다.하나의 빙산 :동서남북으로 연결된 0이아닌 칸들은 하나의 빙산을 이룬다.구해야 할 것 :빙산

3020번: 개똥벌레구간은 높이 1 단위로 나누어진다. 위에서 자라는 거랑, 아래에서 자라는게 있어서.. 석순 list (아래에서 자라)종유석 list (위에서 자라 ) lower_boud(k) : k보다 크거나 같은 수가 처음 등장하는 index를 구하는 방법보통 그

이진트리 개념을 알고 있어도 빠르게 적용을 자꾸 못하는 것 같아서 이번에도 이진탐색 트리 문제를 풀어보기로 했다.역시 부족하다는 것을 많이 느꼈다Unique Binary Search Trees II - LeetCoden이 주어졌을 때 1~n 까지 유니크한 값들로 이루어

2565번: 전깃줄2011.11.10 다시 풀어 봄이 문제는 놀랍게도 LIS와 연관지어 생각할 수가 있다.사실 문제를 처음 보면 드는 생각은, a전봇대를 기준으로 모두 정렬해서, i 번째 전선의 b전봇대에서의 위치를 bx로 해서, i보다 밑에 있는 전선들 중, b전봇대

동적 프로그래밍은 정말 잘 모르겠다. 이 문제를 완전탐색으로 풀려고 한다면 O(n^3)이 나오게 될 것이다.다시 한 번 LCS 풀이를 정리한 것을 보았다.이 문제가 단순 LCS문제와 다른 점은, traceback하면서, 실제 문자열을 구해야한다는 점이다.일단 cache

1958번: LCS 3기존 LCS1,2는 문자열 두개를 대상으로 구하는 것이었다. str1i에 대하여....str2j는 같을수도, 다를 수도str3k는 같을 수도, 다를수도,기존의 LCS를 구하던 방식은 cacheidx1 :str1의 0~ idx 1 까지와str2의 0

문제를 읽는데 순간 당황했다오랜만에 다시 풀기 시작했기 때문에 웃긴 문제를 풀게 된 걸까 .. 1743번: 음식물 피하기좌표에 존재하는 그래프 들 중, 가장 큰 크기를 가진 그래프의 크기를 구하는 것과 같다. 그래프는, 좌우위아래로 연속하는 칸들로 이루어져있다.Unti

기울기를 구해서 i-1일 때 y값과 i일때 y값을 비교하며 각각의 개수를구해서 더하려고했다. 계속해서 틀린값이 나왔다. JAVA로 풀려니 type에 의하여 정말 복잡해졌다 동적타입을 가진 자바스크립트를 사용한다면 너무나 간단해진다. \[프로그래머스] 멀쩡한 사각형 in

11066번: 파일 합치기두 개의 파일을 합쳐 → 임시파일을 생성파일을 합치는 것은 다음과 같이 이루어진다.파일 + 임시 파일파일 + 파일임시파일 + 임시파일이때 이렇게 합치는 것은 연속적으로 합치는 것 을 요구하고 있다.최종적으로 한 개의 파일을 완성하는데 필요한

각 칸에는 상어가 최대 한 마리 들어있을 수 있다.상어는 크기와 속도를 갖고 있다.낚시 보드는1행~r행1열~c열낚시왕의 시작과 끝0행 0열0행 c를 넘는 순간 끝1초 동안 일어나는 일낚시왕이 오른쪽으로 한 column 이동한다.낚시왕이 있는 column에 있는 상어 중

생각 1 :규칙을 찾기 3진법과 비슷한 규칙을 찾아야할 것 같다 생각 2 :나는 규칙을 잘 못찾기에 등비수열로 풀어보려고 했었다. 그런데 이거를 못하겠어서 다시 생각1로 돌아왔다. 나는 규칙을 잘 못 찾는다.. 따라서 많은 경우를 그림으로 그려보았다.따라서3진법으로의표

Search a 2D Matrix - LeetCode 특징각 row의 integers들은 left -> right로 오름차순 정렬되어있다.각 row의 첫 번째 정수는, 이전 row의 마지막 정수보다 항상 더 크다.구해야 하는것m x n matrix 내부에서, 값을 탐색

12100번: 2048 (Easy)한 번의 이동전체 블록을 이동네 방향 중 하나로 이동(주의)한 칸만 이동하는게 아님. 예를들어 , 위로 이동을 하면 왼쪽그림 → 오른쪽 그림이 된다.이 이동에서 이미 합쳐진 블록은, 또 다른 블록과 다시 합쳐질 수 없다.그렇다면 어느

1238번: 파티N개의 마을이 존재 각 마을에 한 명의 학생이 살고 있다.단방향 도로도로의 가중치 : Ti어떤 마을에서 출발한 학생은 다시 자신의 마을로 돌아와야 함파티가 열리는 마을 → X번 마을N명의 학생들 중 , 오고 가는데 가장 많은 시간을 소비하는 학생은 누구

Longest Substring Without Repeating Characters - LeetCode문자열 s가 주어졌을 때, 반복되는 character가 없는 가장 긴 부분문자열의 길이를 구하라정답은 substring이어야 한다. subsequence는 substr

문자열의 길이를 이용하는 식으로 풀이하였다.따라서, 자르는 단위를 u로 하여, 압축된 문자열의 길이를 구하기 위해 u씩 더해가는 방식을 취했다.남는 문자열은 따로 더해준다.문자열 s에서 i ... i + u -1 과 i+u ... i +u+u-1 이 동일한지 확인

16916번: 부분 문자열문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다두 문자열의 길이가 최대 100만만약 단순한 문자열 탐색을 한다면 O(100만 x 100만 ) 이 된다 →

15686번: 치킨 배달각 칸빈칸 : 0집 : 1치킨집 : 2r행, c열1행 1열부터 시작함치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리각각의 집은, 치킨거리를 갖고 있다.도시의 치킨 거리 : 모든 집의 치킨 거리의 합두 칸 사이의 거리 : | r1-r2|+|c1

방법 1 .모든 접두사 → |S|개에 대하여, 해당 접두사가, 접미사인지 확인하기cmp과정 역시 O(|S|)총 O(|S|^2) 이 걸린다. 방법2 .일단 , 문자열 S 자신 자체가 접두사이자 접미사임을 생각하자.pi는 N...i 부분 문자열에서 접두사이자 접미사인 최대

2352번: 반도체 설계전깃줄 문제가 생각나는데, 문제 유형이 뭐였는지도 기억이 또 안 났다ㅋㅋ; 일단 이 문제를 읽고 생각 해 보면, 최장 증가 수열이 생각난다. 왜냐하면, a 번째 포트에 연결된 a’이 있다고 하자. a 포트 아래의 포트를 b라고 하면 b’은 a’보

조합으로 푼다면? → 3000C3 → 4495501000 .. 이건 절대 안된다i ≠ j ≠k 일 때, 실제 값의 합은 0 이어야 한다. 투 포인터의 연장선처럼 풀 수 있지 않을까???따라서 a,b,c 라는 포인터를 두고, a를 하나 결정하고, b c를 조합하는 방식으

(:40)각 단어당 unique한 글자를 갖지 않을 수도 있다. 그니까, 각 단어당, 어떤 글자의 개수는 1개 이상일 수도 있다. → 문제의 조건을 보면, 하나의 strsi의 길이가 최대 100도 되는 것을 보아하니, 중복되는 글자가 존재한다. Map을 사용할까arra

Merge Two Sorted Lists - LeetCode 두 리스트 list1, list2의 head를 받는다. 두 리스트를 하나의 정렬된 리스트로 병합해야한다. 순차적으로 비교해 나간다.비교 후, 둘 중 하나의 리스트는 남아있는 값이 있을 수 있다. ( 둘 다 있

Remove Duplicate Letters - LeetCode문자열 S가 주어질 때, 중복되는 글자를 제거하여, 모든 글자가 한 번씩만 나타나도록 하여라. 결과는 가능한 결과중 가장 smallest한 사전순(lexicographical order) 띄어쓰기도 있는걸까

Odd Even Linked List - LeetCode무슨 말이지? 문제이해를 잘 못 할 뻔 했다. 처음에는 노드 내부의 값이 홀수 인것, 짝수인것들을 모아서 그룹을 지으라는 줄 알았는데 그게 아닌 것 같다. 문제의 예시를 보니, index 가 홀수인 것을 그룹핑,

코딩테스트 연습 - 정수 삼각형(30:)꼭대기 → 바닥 까지의 경로 중, “거쳐간 숫자의 합”이 “가장 큰 경우”를 찾아보려 한다. 아래칸으로 이동 시, 대각선 방향 “한 칸 오른쪽 or 한칸 왼쪽”으로만 이동이 가능 ( 한 칸!)이 문제는 동적 계획법으로 풀어야 할

코딩테스트 연습 - 등굣길물에 잠기지 않은 지역을 통해 학교를 가려고 한다. 시작점(집) : (1,1) 학교 : (m,n)이동: 오른쪽, 아래쪽으로만 이동 최단 경로 개수를 1,000,000,007 으로 나눈 나머지를 return아니 💥💥 격자..격자가 너무 헷갈리

코딩테스트 연습 - 도둑질모든 집들은 동그랗게 배치되어있다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어있다 → 인접한 두 집을 털면 → 경보가 울린다.각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 리턴하도록 solut

코딩테스트 연습 - 가장 먼 노드(:30)“최단 경로로 이동” 했을 때, “간선의 개수가 가장 많은 노드즉, 이동은 “최단경로로 이동” 하되, 가장 멀리 있는 노드.문제에서는 “1번 노드로부터 가장 멀리떨어진 노드” 가 몇 개 인지 구하라고 하고 있다. 여기서 “경로”

코딩테스트 연습 - 다단계 칫솔 판매괴뤄웠다ㅠ 문제에 또 집착을 해버려서.. 에휴.. 시간이 얼마나 날아간거지 트리구조 → parent(추천인)가 존재함. parent에게 주는 것 : “자신의 이익”의 10프로10프로 계산 과정에서 소수점이 존재하는 경우 → 내림.자신

코딩테스트 연습 - 디스크 컨트롤러요청이 들어오는 시점에, 작업 소요 시간도 알고 있음한 번에 하나의 요청 만 수행 → 그러다보니, 요청이 들어오는대로 즉시 실행은 불가능함.각 작업의 “요청 ~ 종료”까지 걸린 시간의 평균을 가장 많이 줄이는 방법으로 처리하면 평균이

Design Circular Queue - LeetCode배열 기반의 큐 인 경우기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없었다. 심지어 앞쪽 요소들이 모두 빠져 충분한 공간이 생기더라도, 그쪽으로는 추가할 방법이 없었다. ( 지금 이렇게 말하는 건

Letter Combinations of a Phone Number - LeetCode2-9까지의 숫자로 이루어진 문자열이 주어질 때,각 숫자에는 어떤 letter들이 매핑되어있음 2에는 a,b,c3에는 d,e,f조합을 만들라는 것은.. 예를들어 “23”이 주어지면23

Course Schedule - LeetCodenumCourses 개 만큼의 코스가 존재한다. 0 ~ numCourses-1 의 라벨이 매겨져 있다. prerequisitesi 는 int2 짜리 배열로, prerequisitesi 은 prerequisitesi 인 과목

16724번: 피리 부는 사나이앞서 풀었던 LeetCode 207. 코스스케줄 문제와 비슷한 유형으로 찾아본 문제다 (00:23)방향U : 위D : 아래L : 왼쪽R : 오른쪽최소 개수의 safe zone을 만드려고 한다.지도 밖으로 나가는 방향의 입력은 주어지지 않는

트리는 “순환 구조”를 갖지 않는 그래프다. (acyclic)트리는 부모 → 자식 노드를 가리키는 단방향 뿐이다.트리에서 “부모노드는” 하나만 존재한다.트리에서 “루트노드” 는 하나만 존재한다.먼저 트리에서 각 노드가 m개 이하의 자식을 갖고 있으면 m-ary 트리 (

이 문제는 “이진트리”의 직경이다. 최대길이를 갖는 path는 마치 어떤 노드를 루트로 하는 트리의 모습을 띨 것이다. 즉, 어떤 노드의 Left Subtree의 “maxDepth” + Right subtree의 “maxDepth” 와 같다.재귀적으로 파고들어가 lea

1068번: 트리(:30)주어진 트리에서 노드 “하나”를 지웠을 때 남는 리프노드의 개수를 구하라어떤 노드를 지우면 → 그 노드의 subtree까지 모두 제거된다.노드의 개수는 최대 50각 노드의 부모노드가 주어진다. ( 순서대로 주어짐. 즉 0번 노드의 부모노드, 1

Longest Univalue Path - LeetCode이진트리의 root가 주어졌을 때, “같은 값을 가진 노드로만 이루어진 가장 긴 경로” 의 길이를 리턴하라두 노드 사이의 path의 길이는, 그 둘 사이의 엣지의 개수로 나타낸다.노드의 개수는 최대 1만개(0:

엄청난 징조가 보였다.케이스 나누기가 너무힘들었다.브라이언..고민할만해..6시간정도 붙잡고 있다가 미련해서 그만뒀다. 풀이를 찾아볼 수 없었던 것은 남의 풀이 봐도 ...이건 ..참 이해가 어려웠기 때문..ㅠ ㅠ 구현나오면 틀리지뭐..멘탈 잡고 다른거 공부해야겠다..

코딩테스트 연습 - 삼각 달팽이규칙row 를 내려간다. 이는 row를 증가시키는 것cr,cc에서 cr만 증가 언제까지?값이 0이 아니고range 범위내col 을 증가 시킨다.이는 col만 증가시키는 것cr, cc에서 cc만 증가 언제까지?값이 0이 아니고range

Invert Binary Tree - LeetCode이진트리가 주어졌을 때 이를 역전시켜라 ( 좌 우를 ) (50)leaf node 바로 위 노드부터 시작 ( level 이 depth -1 인 노드에 도달 ) 하여 좌우를 swap한다. 나는 “👏아래 → 위”로 올라가

Merge Two Binary Trees - LeetCode두 이진트리 root1, root2가 주어졌을 때 , 둘을 머지하는데 머지규칙은만약 두 노드가 겹친다면 → 두 노드이 합을 새로운 노드의 값으로 한다.Otherwise → null 이 아닌 노드들을 사용한다.m

Serialize and Deserialize Binary Tree - LeetCode직렬화는, 어떤 자료구조 or 객체를, 일련의 bits로 변환하는 과정이다. 이렇게 하면, 파일이나 메모리 버퍼에 저장될 수 있거나, 네트워크 connection link를 통해 전송

21923번: 곡예 비행상승비행 → 하강비행으로 변경 할 때에는, 다른 칸으로 이동 할 수 없다.즉, 상승 비행이 끝난 칸에서, 하강비행을 시작해야 한다.상승 비행 중에는, 앞or위로만 이동하가 비행중에는 앞 or 아래로만 이동이 대회에서 얻을 수 있는 최대 비행 점수

1339번: 단어 수학단어수학 문제는, N개의 단어로 이루어짐. 단어의 , “각” 알파벳 대문자를 0 ~ 9 의 숫자 중, 하나로 바꿔, N개의 수를 합하는 문제다.무슨 말이냐면“GCF” 라는 단어와 “ACDEB” 라는 단어가 있을 때, A = 9, B = 4, C =

1715번: 카드 정렬하기책 합치던 문제랑 비슷한 것 같다.차이점 : 그 문제는 붙어있는 것 끼리만 합치는거였음. 이게 훨씬 더 쉽다가장 적게 비교하는 경우의 횟수를 구하라. (20)현재 가장 작은 두 묶음끼리 합쳐나가면 되는 문제였다.이 때 주의할 것은, 카드 묶음이

2437번: 저울무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용해 측정할 수 “없는” 양의 정수 무게 중 “최솟값 구하기정확하게 측정해야한다.그러니까, 예를들어 3, 1, 6, 2, 7, 30, 1 의 저울 추가 주어지면,1은 가능( 1)2도 가능 (

1744번: 수 묶기길이가 N인 수열이 주어졌을 때, 그 수열의 합 구하기. 수열의 두 수를 묶으려 한다.위치에 상관 없이 두 수를 묶을 수 있다. ( 자기 자신과 묶을 수는 없다 )어떤 수를 묶게 되면, 묶은 수는 서로 “곱한 후” 수열의 합에 더해준다.예시로는, 어

코딩테스트 연습 - 행렬 테두리 회전하기(1:00)회전도 시켜야하고최솟값도 구해야 한다.먼저, 회전의 수(쿼리의 개수 ) 는 최대 1만개 행,열은 최대 100이다. → 하나의 횐전당 이동의 개수는 최대 약, 400개 \* 회전의수(최대 1만개)→ 400만즉, 브루트 포

1655번: 가운데를 말해요지금까지 값중 “중간값”짝수개 → 더 작은 값 .“지금까지” 라는게 문제임1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야하나를 외칠 때 마다, 동생도, 지금까지

바로 직접적인 친구 → 1점 이라는 건가?한 다리 걸쳐서 아는 친구가 있다면 → 2점이고두 다리 걸쳐서 아는 친구 → 3점 세 다리 걸치면 → 4점네 다리 걸치면 → 5점 이 때 , 만약 A - B 는 직접적인 친구이면서 A-C-B 이기도 하면 → A-B인 것으로 보는

14891번: 톱니바퀴12시 방향부터, 시계방향 순서대로 주어진다. N(0), S(1)회전시킨 톱니바퀴 번호, 회전시킨 방향1 : 시계방향, -1은 반시계방향상태는 8개의 정수로 주어진다. 12시방향부터 시계방향 순서대로.LinkedList를 사용해야할텐데, 이를 사용

Course Schedule II - LeetCoden이 2000이기 때문에 전체탐색으로도 풀 수 있다.매 번 다음에 수강할 노드를 탐색하여 선택할 수 있다. 이 경우 O(n^2) 의 시간복잡도 코스스케줄 1 은 dfs 로 풀었던 기억이 있었으나 코스 스케줄 2를 df

“순서가 정해져 있는 작업” 을 “ 차례로 수행 “해야할 때 , 그 순서를 결정해주기 위해 사용하는 알고리즘. 그래프의 “흐름”은 “조건”으로 해석할 수 있다.다양한 조건들이 얽혀 있을 때,즉 순차적으로 어떤 그래프가 형성되어있을 때, 모든 조건이 만족하는 경로를 일

n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다.첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.이 동전을

2n 개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.9465번: 스티커이런건 보통 dp 였던 기억이 있는데 방향을 잡지 못했다. bottom - up 방식으로 풀이하려고 하니, 다음 인접한 칸들에 대한 영향을 고려하

2470번: 두 용액산성용액 특성값 : 1 ~ 10억 ( 양의 ) 정수알칼리 용액 특성값 : -1 ~ -10억 (음의) 정수같은 양의 두 용액을 혼합한 용액의 특성값 : 각 용액의 특성값의 합. 특성값이 0에 가장 가까운 용액을 만들려고 한다. 둘 다 알칼리성 이거나,

4485번: 녹색 옷 입은 애가 젤다지?동굴의 각 칸에는 도둑루피가 있다. 도둑루피가 있는 칸을 지나면, 해당 도둑루피의 크기만큼 소지금을 잃게 된다.즉, 비용이 든다는 것으로 생각하면 될 듯 하다.따라서, 최소비용으로 출구 까지 가는 것으로 생각 할 수 있다.이동 가

코딩테스트 연습 - 괄호 회전하기일단, 올바른 괄호 문자열 : 짝이 맞는 것 \_ 스택에서 짝이 맞는 것회전 : 한 칸씩 왼쪽에서 빼내서 오른쪽에 붙이는 것.주어진 s 에 대해, 한 바퀴 돌리려면 최대 1000 개의 경우가 나온다. 이 때 하나의 경우에 대해 매 번 스

2110번: 공유기 설치하나의 좌표 위에 여러개의 집이 존재하는 경우는 없다 집에는 공유기 C 개를 설치하려고 한다.최대한 많은 곳에서 와이파이를 사용하고 싶다.따라서, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.한 집에는 공유기를 하나만

코딩테스트 연습 - \[1차] 뉴스 클러스터링J(A,B) 에서 A,B 모두 0인 경우 → 1이다. 한 집합에서 원소가 중복되는 경우{a,a,a,a,a}, {a,a,a} 인 경우 A교B , A합B → min(3,5) (즉, ,a,a,a ) max(3,5) (a,a,a,a

코딩테스트 연습 - 하노이의 탑한 기둥에 꽂힌 원판들을 “ 그 순서 그대로 “ 다른 기둥으로 옮겨 다시 쌓는 것.원래 상태도 : 작은 원판이 위에 쌓여있는 상태임.1번 기둥에만 원판들이 존재함한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어선 안

피곤..스터디 쉬고 싶은 하루다 🥲코드가 개판 새판이지만응시자가 앉아있는 자리 사이가 파티션으로 막혀 있는 경우가 잘 이해되지 않는다. 맨해튼 거리가 2 이하인 경우 “ 어느정도 막혀있어야지" 허용되는걸까?두 응시자 사이에, 경로 길이 2인 path 가 존재하지 않

전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여, 만들 수 있는 가장 큰 숫자를 제출하는 것 ! 같은 순위의 연산자는 없어야 합니다 ( 2개 이상의 연산자가 동일한 우선순위를 가질 수는 없습니다 )수식에 포함된 연산자가 두개라면 → 연산자 우선순위 조합은

https://www.acmicpc.net/problem/10054번을 위해선, 2번 3번이 완료되어야 한다. 2번,3번은 “동시 진행이 가능" 하다 → 결국 나중에 완료되는 건물에 걸리는 시간이 측정된다 특정 건물만 짓는다면 게임에서 이길 수 있다.매 게임마

코테 모의고사 치는데.. ㅋㅋ 레벨 1만 풀 수 있었다.. 매우 좌절 스러운 상태 같다. 아무튼..앞에 두문제를 25분만에 풀고 3번을 1시간 30분을 붙들고 있다가 그냥 나왔다.그리고 다시 해당 문제를 찾아서 풀었다. 내 문제점은 다음과 같았다수를 뽑는 기준을 잘못

https://school.programmers.co.kr/learn/courses/30/lessons/118667길이가 같은 두 개의 queue하나의 queue (pop) -> 다른 queue (insert)목적: 각 큐의 원소 합이 서로 같도록 한다.구해야

원래 지난주에 정리하려고 했는데, 개인적인 이슈로 인해 오늘 적는다처음에는 이 문제가 디익스트라 문제라고 생각했다. 모든 노드 각각에서 부터 “하나의 노드" 까지의 최소거리들을 모두 알아야 하는 것 이라고 생각했기 때문이다. 하지만디익스트라로 하니까 시간초과가 나왔다ㅏ

bfs 는 depth 기준으로 먼저 탐색하다보니 "최소 경로" 문제에 은근 많이 사용되는 것 같다. 이번에는 디익스트라 문제였던 것 같았는데 bfs 가 사용된 경우가 있어서 한 번 정리(?) 해 본다. 안전한걸 선호해서 그런지, 나는 위에서부터 차근 차근 모두 살펴보

정리 정리 시즌... 다시 다시 하는 시즌..자주 나오진 않는 거 같지만, 꼭 까먹었을 때 나오길래..ㅎㅎ합 집합 찾기 == 서로소 찾기 여러개의 노드가 존재할 때, 두 개의 노드를 선택해, 현재 이 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 이다.

https://school.programmers.co.kr/learn/courses/30/lessons/77885이 문제 계속 틀리고 있었는데..하나를 빠트렸던 ㅓ경ㅆ다. 이 문제는 문자열로도 충분히 풀 수 있다.1 ≤ numbers의 길이 ≤ 100,0000

뭐였더라..

Longest Consecutive Sequence - LeetCodeGiven an unsorted array of integers nums, return the length of the longest consecutive elements sequence.You mu

이 문제는 다음과 같은 순서로 풀었다.코스 별로 조합을 만들어야 한다. 이 때 “코스” 는 각 코스를 구성하는 “메뉴의 개수”다. 주문 별로 조합을 만들어야 한다. 만들어진 조합들은 Map 을 통해 조합의 개수를 관리한다. 이 때, 주어진 orders 의 각 문자열들

총 노드의 개수는 200개 , 간선은 n\*(n-1)/2 이다. 이 문제는 중간지점 X 를 거쳐 가거나 or 거쳐가지 않거나 의 두 경우이다. 중간지점을 거쳐가지 않는 경우sa + sb중간지점을 거쳐가는 경우sx + xa + xb이다. 처음에는 디익스트라인 줄 알았는데

이 문제는 DP 문제다. 왜냐하면 문제는 비용의 최솟값을 구하라고 하고 있는데i 번째 순에서 최솟값을 특정할 수가 없기 때문이다. 뭔 말이냐면5개 집이 존재 할 때 1 번째 → 2 번째 → 3번째 순으로 각 순서에서 현재까지 최소인 비용이라고 생각하고 색을 선택하면,

카드 팩은 다양하다 → 각 카드 팩은 다양한 개수의 카드가 포함되어 있다카드 팩에 담긴 카드 개수가 적고 비싸면, 좋은 카드팩 아닌가?? 라고 생각한다고 함카드 N 개를 사기 위해 “가장 큰 비용” 이 드는 경우를 찾고 싶다개수를 딱 맞춰야 한다.카드팩을 “중복해서 선

백트랙킹 문제로 매번 1 ~ N 의 수가 그 대상이 되므로 N^M 의 시간복잡도가 걸릴 듯 하다. 수열에서는 순서도 고려하기 때문에, 이렇게 해도 유니크한 수열을 뽑을 수가 있다. 사전순으로 출력해야하므로, 그냥 1~N 순서로 방문하고, 생성한 순서대로 정답으로 넣으면

이 문제는 거의 매 Idx 마다 Pn 인지 확인하는게 필요하다 생각되었다. 현재 idx 에서 Pn 임을 검증하는 것이 성공한 경우 -> idx + 2 위치부터 이어나간다실패한 경우 -> idx + 1 위치부터 이어나간다. 따라서 매 idx 마다는 매번 최대 2 \* n

https://leetcode.com/problems/subarray-sum-equals-k/합이 k 가 되는 subarray 의 개수를 구하기contiguous element 들로 이루어져 있는 것을 구하기 때문에연속한 원소들로 이루어진 subarray 이니

class Solution { /\* 정수 배열 nums 과 정수 k 가 주어졌을 때, (nums 의 모든 원소는 자연수 이다) 해당 배열을 , sum 이 동일한 k 개의 subset "들" 로 분리하는 것이 가능한지 여부를 알려주는 프로그램을 작성하라