우선적으로 연결되어있는 번지수를 체크하는 문제이다. DFS,BFS가 가능하다. 나는 DFS로 접근.제일 먼저, solution함수를 이용해 board를 순회하면서 ch배열 체크하면서 1이 나오면 cnt를 증가하면서 ArrayList인 arr에 저장하는 식으로 구현.DF
우선, 어려운 문제는 아니다. 조금 헷갈렸던 건 문제의 출력과 똑같이 답을 내야한다고 생각했는데 그냥 늑대가 양에게 접근만 못하게 하면 무엇이든 정답이된다.입력받을 때 유의.입력받은 arr을 탐색하면서 "W" 늑대를 만나면 상하좌우로 "D"울타리를 쳐주면된다.이때 늑대
백준은 항상 느끼지만, 프로그래머스와 달리 입력받는게 제일 귀찮고 깐깐하다. ㅋㅋ 신경쓰자.1\. k개수 만큼 사각형인 부분을 boarda에 1로 입력해둔다. 그러고 이제 나머지 영역을 구해야한다.2\. solution()함수로 board를 탐색하고 여기서 0이나오면
문제 풀이 일단, 결론부터 얘기 하자면 max변수를 이용해 최고높이를 구하는 과정에서 max=0으로 선언했더니 런타임 에러가 떳다. 최댓값을 구할 땐 INTEGER.MIN_VALUE로 선언하자. 각 높이 별로 solution을 돌려줘야한다. 또한 체크배열을 이용해
풀이큐는 원래 FIFO성질을 가진다. 이 문제는 양방향 큐를 요구하는 문제이다.이 문제를 해결하기 위해서는 Index를 알아내는 메서드가 필요한데 Q에는 없어서 LinkedList<인티저> list = new LinkedList<>(); 를 선언해서 문제를
이 문제는 기본적으로 생각을 좀 하고 접근해야했다.일단 문제에서 묻는 건 시간이 정해져있는 강의들을 하기 위해서 강의실을 몇개를 빌려야하는지 찾는 문제.우선 이런 문제는 무조건 정렬부터 시작해야한다. Comparable<객체>를 이용해서 시작시간 기준으로 정렬해준
우선 백준 브론즈 문제다,, 구현/시뮬레이션 문제인데 생각보다 많이 헤맸다,, 브론즈 문제인 걸 생각해보면 참 갈길이멀다. ㅎ우선 시간은 1~100시간 까지 주어지므로 arr을 선언. truck은 무조건 3대가 입력되며 주차시작시간과 주차끝나는시간을 담는 int3로 선
브론즈 문제. 헤맸다 ㅎ 우선 13문자씩 밀면된다. 근데 여기서 소문자 대문자 구별을 해준다. 왜냐면 아스키 코드 값이 달라서 한번에 묶어서 하면 이상한 값이 나오더라. 그리고 N,n보다 큰 문자는 13문자씩 앞으로 못밀기때문에 13문자씩 빼주면 된다.
최단거리를 구하는 문제. 처음에 DFS로 문제를 해결하려했는데 잘 안돼서 BFS로 해결.최단거리 문제는 BFS로 푸는게 깔끔하다. 앞으로도 그렇게 풀자.거리체크 배열을 하나 더 파서 체크해주는게 좋은 방식.
이 문제는 몇 가지의 옷 종류를 통한 옷입는 방법의 조합을 물어보는 문제이다.조합을 이용해서 해결한다.headgear : hat, turban, NULL eyewear : sunglasses, NULL이렇게 구성된다. 옷을 안입는 경우도 경우이다. 이렇게 해서 모든 경
dy0=1을 해줘야한다. 0원을 만드는법 1가지.동전의 종류별로 dyj=dy\[j-arri]를 해준다. 그러면 해당 동전의 경우와 다른 동전으로 만들수있는 경우의 수가 중첩되면서 증가한다. 어렵다,,다이나믹 프로그래밍 문제 많이 풀어보자.
2번째 줄의 '\*'을 기준으로 앞문자와 뒷문자가 일치하면 "DA" 불일치하면 "NA"를 출력하는 문제이다.핵심은 split을 이용한 분할법.split() 함수를 이용해 '\*'을 기준으로 문자를 나눠준다.만약에 비교할 문자의 길이가 '\*'을 기준으로 나눈 문자보다
팰린드롬은 임의의 문자열을 앞으로읽어도 뒤로읽어도 같은 문자를 만드는 것이다.각 문자의 수는 26개 이기 때문에 alp\[]를 만들어 각 문자의 개수를 구한다.갯수가 홀수인 문자의 위치와 수를 구한다. 그리고 그 문자를 center로 저장이때 이 홀수인 문자의 수는 무
이진 트리(Binary Tree)는 자식 노드를 2개씩 갖는 트리였다면 쿼드 트리(Quad Tree)는 쉽게 말해서 자식 노드가 4개인 트리 자료구조를 의미한다. 결과는 이런식으로 나온다. 상하좌우 영역을 나누어서 0 혹은 1 로 이루어지면 하나의 문자로 압축하여 출력
문제를 보자마자 HashMap으로 풀어야겠다는 생각을 했다. 근데 이 문제에서 요구하는 것은 value값이 같을 때 먼저 입력받은 key를 출력하라고 제시했다. 그래서 LinkedHashMap이라는 자료구조를 사용했다. LinkedHashMap의 장점은 저장되는 순서를
문제는 쉽다. 그냥 보고 풀면된다. 중요한 것.계속 런타임 에러가 떠서 알아봤더니 각 줄의 문자의 길이가 100까지라서 Integer,Long 으로는 안된다. 중간에 거쳐도 안된다.. 그래서 찾아보다가 BigInteger라는 자료형을 찾았다. 이 자료형으로 해결! 외우
문제 풀이 우선 각 경우에 맞는 최솟값을 구하는 문제이다. 보자마자 재귀(DFS,BFS) 혹은 DP로 푸는 문제임을 알아야한다. 지금 내가 풀이한 방식은 DP 동적프로그래밍 방식이다. DP 문제를 풀 땐 3가지 단계를 생각한다. 테이블 정의 점화식 찾기 초기값
이 문제는 정렬하는 핵심만 알면 될것같다.일반 arr\[] 배열이 있다고 하자. 일반 배열은 Arrays.sort()를 이용해서 정렬한다.여기서 좀 더 세부적으로 정렬할수있는 기능이있다. 바로 Comparator이다.위 방식대로 선언한 후에 @Override를 통해서
무방향 그래프에서의 연결된 요소의 개수를 구하는 문제이다. 한 그래프를 네트워크 연결이라고 치면, 연결되어있는 네트워크의 개수를 구하는 문제라고보면된다.무방향 그래프 특성상 입력받은 간선을 1로 표시할때 반대로도 1을 표시해줘야한다.그거 말고는 어려운 점이없었다. 핵심
계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다
문제 풀이 DFS 시도 결과는 제대로 나오나 , 시간초과로 인한 런타임에러! 이럴 경우엔 --> 무조건 DP 확정 주어지는 값들의 범위가 100단위가 넘어가면 DFS는 재귀호출방식이라서 효율이안좋다. 이런 경우들에는 DP로 해결해보자. DP 시도
일단 문제를 읽어보면 DFS,BFS로 풀 수 있을 것 같은 느낌이 든다. 하지만 문제 조건을 보면 미로 조건이 최대 1000까지 주어진다. DFS,BFS로 풀면 백빵 런타임 에러가 뜬다. 그러면 뭐냐? -> 무조건 DP!! 바로 점화식을 찾아야한다.주인공은 우측 , 우
문제 풀이
이 문제는 쉬워보여도 굉장히 까다로운 문제다. 우선 n값의 범위는 100만 까지 주어진다. 그리고 하나 배운 점dp = new intn+1; 이렇게 선언하면 미리 dp0,dp1,dp2 등에 값을 선언해두면 배열 할당문제가 발생한다. 이거 몰라서 한참 헤맸네;;;; ㅋㅋ
테스트케이스만 보면서 구현. 테스트케이스는 통과한다만 실패. 막구현 하지말자 제발.아아 DP어렵다... ; 인터넷 풀이를 봐도 이해 안되는게 대부분 이 문제의 핵심결과적으로 각 집의 최솟값을 찾아 누적합을 구하는 것이 아닌, 모든 경로의 경우의 수를 찾아서 최종적으로
우선 문제를 봤을 때 당연히 DFS가 생각난다. 하지만 제한사항 보면 n값이 너무 크기 때문에 자동으로 DP알고리즘으로 분류된다. 하지만 이 문제는 간단해서 그냥 풀 수도 있다. 그래도 DP를 공부하기 위해서 DP방식으로 진행했다.테이블 정의규칙찾아서 점화식 구현출력우
DP 문제다. 계속 반복된다. -> DP문제에서 한번 클릭하면 A->B로 B->BA로 된다고 한다.테이블을 만들어 기본값을 정의하고 식을 찾아보자.0 -> A1 -> B2 -> BA3 -> BAB4 -> BABBA5 -> BABBABAB이렇게 된다. 우선 A의 수를 d
매우매우매우매우 중요한 문제다. Comparable , Comparator 인터페이스를 이용한 정렬의 핵심 문제.문제 설명이렇게 정렬하면 된다.근데 처음엔 Comparable 정렬함수를 이런식으로 정렬하려고 시도했다.입력 후에 출력값을 대충 봤는데 제대로 정렬이 안되는
임의의 위치에서 시작할 수 있으며, 4방향으로 이동가능하다. 5번 더 이동이 가능하고 6문자가 만들어지면 중복없이 몇가지 경우의 수가 나오는지 구하면 되는문제이다.임의의 위치를 위해서 이중for문으로 DFS()를 호출한다. 그리고 tmp에 다음 좌표 문자들을 더해서 L
문제 1 풀이
처음에 일반 정렬로 문제를 해결하려고 시도.. 해결이 되지않아서 다른 방법을 찾아보니 PriorityQueue를 이용해서 풀어야하는 것 같더라. 이 우선순위 큐는 그냥 선언하면 최솟값을 먼저 출력해주기 때문에 먼저 끝나는 강의 시간과 시작하는 강의의 시간을 비교하기 좋
처음에 정렬로 문제 풀이 시도.. 근데 답을 찾아가는 과정에서 비교가 필요한 거 같아서 풀이 방식에 의심을 가졌다.. 그래서 다시 생각해본 결과 이 문제는 DP로 해결해야하는 문제였다. k강의가 있다고 치면 이 강의는 k+1,k-1 강의와 겹친다. 강의 시간이 겹치면
정렬 , 그리디 문제다. 원생들을 k 만큼의 그룹으로 나누고 거기에서 원생들의 최소 키차이을 다 더해서 구해주면된다. 우선 원생들을 키순으로 오름차순 정렬시킨다. 그리고 각 원생들의 키차이를 각각 arrayList를 만들어서 담아준다. 그리고 최소한의 키차이를 구해야
우선 예제 입력 1번을 보자.이렇게 입력받는다. 근데 최소거리는 131인데, 131이 나오려면 내림차순 정렬을 한번하고 가장먼거리인 -39거리는 마지막에 가서 그대로 끝내야하고, 큰거리순으로부터 m만큼의 책의 자리에 책을 한번에 가져다놓고 0의 위치로 돌아와야 최소거리
위에서 아래로 전류를 흘려보내야한다. 0으로 입력된곳이 전류가 흐를 수 있다. 1행을 훑으면서 DFS()를 호출해주고 4방향으로 다음좌표로 DFS()를 재귀호출한다. 지나온길은 다시 돌아가지 않기 위해서 임의로 2로 바꿔준다. 이런식으로 진행하다가 재귀가 마지막행에 도
이 문제는 파일 확장자 수를 세고 확장자 수가 여러개 일때는 사전순으로 정렬해서 출력하는 문제다. '.'이 나오면 flag를 true로 바꿔주고 true일때는 문자를 전부 ex라는 String 변수에 담는다. 그러고 map에 담아주고 초기화!!map을 사전순으로 정렬하
DFS 골드문제이다. 일반적인 DFS구조를 문제인 것 같아서 도전해봤다. 처음에 문제를 풀때는 해당 끝 도착지까지 문자를 String에 담고 한방에 계산해서 max,min을 나누려고 했다. 근데 계산을 어떻게 해야할지 고민을하다가 , 이 방식이 아닌 것 같아서 다른 방
농장의 봉우리 수를 찾는 문제이다. 주변에 대각선포함 8방향 기준으로 자신보다 높은 봉우리가 없어야 봉우리로 취급한다. 기본적인 DFS 템플릿을 가지며, flag를 이용해서 주변에 높은 봉우리가 없으면 true를 유지시켜 answer++해주고, 만약 주변에 높은 산이
처음에 그냥 무지성으로 풀었는데 시간초과. 그래서 우선순위큐로 풀었다. 역순으로 우선순위큐를 선언하면 큰수부터 나오는 자료구조이다. 그렇게 해서 답 이전까지 다 poll해주고 답도 poll해서 출력해주면되는 문제이다!!
이 문제는 2중 for문 , ArrayList의 contains() 등등 일반적인 방식으로 풀면 전부 다 시간초과가 발생한다. 이럴 때 원하는 값을 찾고자 할때 그 값이 배열안에 있는 지 없는 지 효율 좋게 찾는 방법은 이분탐색이다. 일반적인 탐색 알고리즘 중에서 가장
처음 문제를 봤을때 Hashmap으로 푸는 법과 이분탐색 두가지로 푸는 법이 생각났다. 근데 이분탐색으로 해결하는 게 더 공부가 될 것 같아 그렇게 풀었다.우선 탐색해서 존재유무를 파악하는 것보다 한발 더 나아가서 갯수를 구하는 법이다.이런 경우는 해당 문자를 정렬된
처음에 빡구현으로 풀다가 이건 아닌거같아서 인터넷 참고후 Comparator 참고함.원래 나는 Comparator 커스텀 클래스로 파서 할 줄만 알았는데, 이번 문제를 계기로 그냥 단일 요소에 대해서 바로 Comparator를 호출해서 정렬하는 법을 배웠다.길이가 짧은
접두사는 어떤 단어의 앞에 붙어 뜻을 첨가하여 하나의 다른 단어를 이루는 말을 이른다. 예: ‘맨주먹·덧버선·풋사과·군소리’ 등에서 ‘맨―’·‘덧―', '풋-', '군-' 따위중요 내용1\. s2.indexOf(s1) : s1이라는 문자열이 s2에 있는 위치 반환, 없
이 문제 풀이 방식은 되게 신기했다. 색다른 자극,,백신 접종이 한 번 가능한데, 접종 이후에도 두 board,compare가 다른 정보를 가지고 있으면 정답은 "NO"가 출력되어야한다.처음에 compare를 입력받을 때 board와의 정보 차이를 diffInfo\[]
인접리스트를 활용한 방향(무방향x) 그래프 문제! 오랜만에 보니까 좀 헷갈렸다.1정점부터 ~ n 정점 까지 for문 돌려서 DFS()를 호출하려니까 잘 안돼서 그냥 한방에 되게끔 x정점부터 역으로 DFS()를 호출시켰다.그러면 x정점과 관련된 곳은 전부 체크배열에 걸려
BFS 필수 선언커스텀 클래스 -> 좌표 저장용거리 저장용 dis 배열board 에다가 체크할수있으면 숫자바꿔가면서 체크하면서, 만약에 board 배열 없으면 따로 boolean ch 배열 만들어서 방문체크 배열오랜만에 BFS 풀었다. 나는 극 DFS 주의이긴 한데,
오랜만에 DFS 기본이 되는 문제! 원샷원킬!DFS의 핵심. 기본 DFS 템플릿 구조를 이해해야하며, DFS() 호출 전에 탐색하는 solution() 함수를 잘 작성해야한다.이 문제의 경우 한 곳의 울타리를 찾아서 그곳에서의 살아남는 양과 늑대의 현황을 종합해서 출력
인접리스트를 이용한 경로를 탐색하고 끝으로가는 거리를 구하면된다. 단순한 문제이면서, 인접리스트 DFS의 기본이자 핵심 문제이다. 이 유형을 문제를 오랜만에 풀었는데, 헷갈렸다. 연습하자. ........ DFS은 크게 기본 미로탐색같은 템플릿구조를 띄는 문제와 인접리
글 목적이 문제는 한번에 맞췄다! 근데 이 글을 쓰는 목적은 기본적인 문제라 나중에 복습을 하기 위함.우선 기본적인 BFS 템플릿 구조를 가진다. 하지만 주의할점은 8방향으로 대각선 포함 이동이 가능해야하며, 각 위치(좌표)에서의 상어까지의 최소거리를 구해서, 모든 좌
시작 시간 , 종료 시간 기준으로 최소로 사용되는 회의실 개수를 구할 때는 무조건 해야하는 것들이 있다.무조건 종료시간 기준으로 오름차순 정렬.PriorityQueue를 이용해서 최소회의실 개수를 구해야한다.암기 필수.미팅의 시작시간보다 작은 회의실이 있으면 빼주고,
이분 탐색은 풀 때마다 헷갈린다. 그냥 문제 보고 종이에 쓱쓱 쓰다 보니까 이분탐색 문제인거를 바로 알았다.좌표의 정렬mid 값 구하기 -> mid 값을 기준으로 로직 실행.만약 mid값 기준으로 더 작은 값이 필요하다면 rt = mid - 1; 그 반대라면 lt =