개발자취업 35

99클럽 코테 스터디 15일차 TIL 그리디(카드문자열)

https://www.acmicpc.net/problem/13417 카드를 순서대로 하나씩 가져오면서 사전 순으로 가장 빠르게 정렬하는 것. 이때 가장 왼쪽 또는 가장 오른쪽에만 둘 수 있다.핵심 아이디어는 문자를 하나씩 보면서 맨 앞 문자보다 순서가 빠르면 (아스키코드 값이 작으면) 맨 왼쪽에 두고,맨 앞 문자보다 순서가 느리면 (아스키코드 값이 크면) 맨 왼쪽에 두어야 겠다고 생각했다.그리고 자료구조는 Deque 또는 ArrayList 중에 고민하다가 후자를 택해 구현했다.(Deque를 사용한다면 peekFirst와 addFirst / add 를 사용하면 된다) package STUDY.Week03;import java.io.BufferedReader;import java.io.IOException;..

코테/백준 2024.11.12

99클럽 코테 스터디 14일차 TIL 그리디(거스름돈)

https://www.acmicpc.net/problem/14916동전의 개수를 최소로 사용하려면 5원을 최대한 사용해야한다.그리고 2원으로 나눠져야 하므로 5원을 가지고 짝수로 만들어야 함을 알 수 있다.따라서. n이 홀수일 때와 짝수일 때를 나누어 홀수면 5를 최대의 홀수번으로 나누고, 짝수면 5를 최대의 짝수번으로 나누고자 했다. *** 5미만이 들어오면 짝수일 때는 2로 나누어지지만, 홀수일 때는 낼 수 있는 방법이 없으니 -1을 출력해야한다.package STUDY.Week02;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Day14_BOJ_14916_거스름돈..

코테/백준 2024.11.11

99클럽 코테 스터디 13일차 TIL 그리디(고양이는 많을수록 좋다)

https://www.acmicpc.net/problem/27961 이런문제는 결과값을 가지고 입력값을 만들어가는 경우를 생각해야 한다.그리고 그 과정에서 최소 연산을 할 수 있도록 해야하는데, 이 문제의 경우는 생성과 복제 중 복제이다.결과값에서 최대한 복제를 할 수 있는 한 하고 생성을 해서 입력값으로 만들어 가는 연산의 수를 구하면 된다.즉, 6일 때 -> 3(최대 2배로 복제) -> 2(최대 2배 이하로 복제할 경우) -> 1(최대 2배로 복제) -> 0(생성) => 4가 된다.이를 코드로 구현하면 아래와 같다.** 입력값이 0일 경우엔 무조건 0임을 고려해주어야 한다 package STUDY.Week02;import java.io.BufferedReader;import java.io.IOExce..

코테/백준 2024.11.10

99클럽 코테 스터디 12일차 TIL BFS(토마토)

https://www.acmicpc.net/problem/7569 익은토마토로부터 6방향에 있는 안익은 토마토가 익고, 하루가 걸린다. 동시에 6방으로 퍼져야하기에 BFS로 풀었다.안익은 토마토가 다 익는지만 확인하면 되기에 안익은 토마토 개수를 unripe 에 저장해두고 익을때마다 unripe-- 를 해주었다.3차원 배열이고, 6개의 방향 설정만 주의해주면 된다.q에는 익은토마토와 익혀진(?)토마토만 넣으면서 퍼트려준다.** 익혀진 모든 토마토의 주변을 탐색하고 cnt++을 해주어야 하는 것을 주의한다 package STUDY.Week02;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;im..

코테/백준 2024.11.08

99클럽 코테 스터디 11일차 TIL DFS(Yes or yes)

https://www.acmicpc.net/problem/25195 주어진 필수 조건은 단방향, 1번에서 출발이다.DFS로 가다가 방문했던 노드나 팬클럽이 있는 노드가 있으면 지나지 않고 진행한다.팬클럽 노드를 제외하고 방문했으면 어떻게든 만나지 않고 가는 것이니 yes, 아니면 Yes를 출력한다-> 그리고 이를 '팬클럽노드 수 s + 방문한 노드 수 = 총 노드 수' 라고 조건 걸었다하지만 이렇게 하니 예제를 넣었을 때 출력 값이 틀리게 나왔다.주어진 본문 예제가 아닌 예제 2번을 만족하지 않았다. 예제 2번을 해석해보니 '여행이 끝났다' 라는 말이 해당 노드에서 이동할 수 있는 노드가 없는 경우 라는 것을 깨달았다.양방향이 아닌 단방향 노드이니 당연히 모든 노드를 방문했을 때 여행이 끝나는 것이 아니..

코테/백준 2024.11.07

99클럽 코테 스터디 10일차 TIL BFS(특정 거리의 도시 찾기)

https://www.acmicpc.net/problem/18352 오늘 문제는 단순 BFS지만 고려해야 하는 조건이 많은 문제였다,,1. 양방향이 아닌 단방향 그래프2. 방문 가능한 도시를 오름차순으로 출력 -> pq에 넣어서 출력했다.3. 방문 가능한 도시가 0이면 -1 출력 -> 도시 방문 여부를 flag로 검사했다. 요 3개 조건만 잘 적용하면 되는 문제였는데, 난 여기에 방문 조건을 잘못 걸어서 출력초과와 틀렸습니다를 계속 받았다,,** 고려하지 못했던 부분1. 거리가 K를 넘어가면 q에 넣을 필요가 없다.2. q에 안넣어도 방문 처리는 해줘야 한다!!!package STUDY.Week02;import java.io.BufferedReader;import java.io.IOException;im..

코테/백준 2024.11.06

99클럽 코테 스터디 9일차 TIL BFS(나이트의 이동)

https://www.acmicpc.net/problem/7562 최소 몇 번만에 이동할 수 있는지 = BFS이동가능한 방향은 8가지 (-2, 1) (-1, 2) (1, 2) (2, 1) (2, -1) (1, -2) (-1, -2) (-2, -1) 이다.큐에 들어있는 모든 칸들이 한꺼번에 1번씩 이동하다가 목적지에 도착하는 이동 거리를 계산해야 하므로 qSize 만큼 돌리면서 cnt++ 해주고,목적지에 도착했을 때의 cnt 값이 답이된다.  package STUDY.Week02;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import jav..

코테/백준 2024.11.05

99클럽 코테 스터디 8일차 TIL DFS(촌수계산)

https://www.acmicpc.net/problem/2644 오늘은 작년에 풀었던 문제였다전형적인 DFS 문제로 시작노드에서부터 목표노드 까지의 거리를 구하면 된다!방문 순서가 아닌 노드 사이의 거리이므로 dfs 함수에 재귀로 같이 cnt를 돌려야 한다.** 도착하지 못하는 경우 -1 출력이므로, ans는 -1로 초기화 해주기!! package STUDY;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Day08_BOJ_..

코테/백준 2024.11.04

99클럽 코테 스터디 7일차 TIL DFS(모음사전)

https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제를 읽으면서 든 생각은 순열, 조합, 부분집합, DFS 어쨌든 재귀로 풀어야겠다고 생각했다문자열을 재귀에 담아 만들면서 돌리고, 원하는 문자가 나왔을 때 그때까지의 번호를 return 하는 형식.총 길이가 5이므로, 5까지만 만들고 되돌리고를 반복하면 된다.몇번째인지를 담는 변수는 함수에 넣으면 안됨!문자가 5를 넘어가면 안되니 5에서 return 조건 걸고, 5가 되기 전에 주어진 단어가 나올 수 있으니 이때도 return 조건문을 걸어줬..

99클럽 코테 스터디 6일차 TIL 이분탐색(나무 자르기)

https://www.acmicpc.net/problem/2805 이분탐색 문제를 여러개 풀다보니 이제 문제를 읽으니까 언제 이분탐색을 써야할지 감이 살짝 온다1. 변수 범위가 클 때! (1억 이상)2. 구해야하는 값이 랜덤이 아닌, 특정 기준에 맞춰 지속적으로 범위를 찾아주어야 할 때! 즉 문제에서 구하는 값이 최대, 최소인 경우큰 범위 내에서 특정 값을 범위를 통해 찾아야 할 때 => 이분탐색을 쓰자! 무튼 이 문제는 전에 풀었던 예산과 비슷하게 풀었는데 2%에서 틀려서 당황했다,,여러 테케 만들어서 넣어봐도 다 분명 정답이 나오는데,, 문제는 자료형이었다!!!나무의 길이 M이 최대 20억인데 calc 함수에서 상근이가 집으로 가져가려고 하는 나무의 길이 result가 int형 범위를 넘어가는 것이었..

코테/백준 2024.11.02