코딩테스트

안일한 생각 덕분에 코테에서 광탈당한 상처가 매우 쓰라리다ㅎJS로 코테 부시기 시작! 푼 문제들을 정리해서 블로그에 올리자ㅎ 자신감이 생기는 그날까지!!화이팅!

https://www.acmicpc.net/problem/10026 구하는 값 상하좌우에 같은 값을 가지고 있는 연결요소 쌍의 개수 주어진 graph, R === G로 했을때 graph 핵심 아이디어 N * N 크기이고 N < 100이므로 DFS, BFS 가능

간선을 없앴을 떄 두 개 또는 그 이상으로 나누어지는 간선 나는 위의 구하는 값이 => 사이클에 포함되지 않은 노드의 간선 과 동일하다고 생각했고 구현했다. 사이클을 판별하고 사이클에 사용된 노드의 인접리스트를 빈배열로 만들어 주는 것을 반복하여 남아있는 리스트의 개수

내리갈굼 비용을 출력자신 아래 노드들에 모두 값을 더해주는 것이므로 인접리스트를 만들어서 트리를 만들어주고 input갚으로 호출된 노드부터 leaf노드까지 싹다 더해주면 될 것 같았다... 테케는 맞는데 어떤 반례가 있나..?graph를 n+1 크기로 이차배열을 만들어

구하는 값 0,0 -> n-1,n-1로 갈 수 있는지 근데 지그재그는 안되네...왜 그걸 안 적어줘요ㅡㅡ 핵심 아이디어 dx=[1,0], dy = [0,1]로 잡고 for문돌릴떄 step만큼 곱해서 다음 dfs로 넘겨준다. 코드

https://www.acmicpc.net/problem/1743 구하는 값 가장 큰 연결요소 구하기 핵심 아이디어 입력받은값으로 이차원 배열을 만들기 이중for문으로 각 위치 탐색하며 방문하지 않은 위치에서 DFS DFS에서는 상하좌우로 DFS하며 DFS들 탈때

구하는 값 나이트를 이동해서 도착점까지의 최소거리 핵심 아이디어 가중치가 없는 그래프이므로 BFS를 통해서 최단 거리를 구해줌 구현방법 나이프가 이동할 수 있는 4방향 총 8가지의 경우를 dx,dy로 표현 que를 구현해서 시작점을 que에 넣고 deque하며 다음

구하는 값 누가 이기는지 핵심 아이디어 리프노드까지의 깊이를 다 더해서 홀수면 이기고 짝수면 짐 구현방법 양방향그래프에서 연결리스트의 길이가 1인경우는 루트,리프노드뿐이므로 길이가1일때 cnt에 dep를 더해준다 (시작을 0으로하기때문에 루트노드를 제외해줄 필요없음

구하는 값 -1, 1, 2 를 통해 원하는 곳까지 갈 수있는 '최단거리'* 핵심 아이디어 visited를 루트로부터 거리로 하여 BFS 구현방법 먼저 BFS를 구현하기 위해 Queue clss를 만들어주고 루트값을 queue에 넣고 queue가 빌때까지 while문

여러개의 노드가 연결된 하이퍼 튜브(이것도 그냥 여러개 연결된 노드로 보자)를 이용해서 1번 노드에서 마지막 노드까지 가는 ‘최단거리’최단 거리이고 각 간선의 길이가 같으므로 BFS를 이용BFS를 이용하기위해 입력받은 번호로 연결된 노드들을 이어줘야함노드에는 하이퍼 튜

구하는 값 루트부터 dep가 1, 2인 노드 개수 구하기 핵심 아이디어 bfs로 dep 1, 2인 노드들 카운팅 코드

구하는 값 왼쪽 맨 밑에서부터 오른쪽 맨 위까지 K 번만에 가는 경우의 수 핵심 아이디어 DFS로 상하좌우를 훑으면서 범위밖 || 벽 인경우는 제끼고 방문안한곳이면 방문처리하고 DFS 탄 후 빠져나오면 방문취소, DFS탈때는 Dep를 1씩 늘려가며 Dep 가 K이면서

구하는 값 -, | 의 개수 핵심 아이디어 연결된 것은 1개로 본다. 구현방법 DFS풀이 DFS파리미터로 item을 받아서 동일한 값인지 검사 후 그 방향으로 DFS탐색함 이중for문 for(가로){ for(세로) } 를 돌며 - 개수를 세고 for(세로){

구하는 값 연결요소별 w,b의 제곱값들의 합 핵심 아이디어 상하좌우 dfs를 돌면서 w, b각각 카운팅 구현방법 dfs파라미터 dfs에 파라미터로 cnt값을 넘겨주면서 return 받아 더하는 방법으로 구현 전역변수로 전역변수를 만들고 dfs돌때마다 w,s의 제

구하는 값 남아있는 양, 늑대 수 핵심 아이디어 순차적으로 DFS돌면서 연결요소안에서 양과 늑대 수 세고 누가 더 많은지 비교 후 많은 수만 출력할 값에 더해줌 구현방법 인접리스트 만들고, 같은크기로 visited배열만들기 현재 연결요소의 양, 늑대 수를 담을 변수

구하는 값 6개 숫자를 썼을 때 만들 수 있는 수 핵심 아이디어 상하좌위 DFS돌며 dep가 6일때 정지, 000111도 가능하도록 string로 합치기 구현방법 인접리스트 만들고 : graph 숫자담을 배열 만들고 : arr 현재상태 str만들고 : cur 이중

구하는 값 노드의 방문순서(인접 노드는 오름차순으로) 핵심 아이디어 인접리스트 만들고 sort 후 DFS 구현방법 인접리스트로 입력값 받고, sort로 오름차순정렬 방문처리할 visited 배열을 0으로 초기화 DFS돌며 dep를 1씩 증가, 방문하지 않은 노드로

구하는 값 시작 노드부터 특정dep를 가지고 있는 노드수 핵심 아이디어 특정 dep를 구하는 것이기 때문에 bfs로 풀이가능 que에 dep를 같이 넣는 방법과, visited에 dep를 기록하는 방법 두가지 풀이가 생각남 아래는 후자풀이 코드

구하는 값 바이러스의 종류 핵심 아이디어 상하좌우로 바이러스가 퍼지고 더 작은 숫자 바이러스가 기록되므로 큐에 작은 바이러스 순서대로 넣는다면 작은 바이러스가 기록될 것이고 기록된 곳에는 방문을 하지 않는 방식으로 bfs를 돌리면 해결됨 코드

시작 노드부터 특정dep를 가지고 있는 노드수특정 dep를 구하는 것이기 때문에 bfs로 풀이가능 que에 dep를 같이 넣는 방법과, visited에 dep를 기록하는 방법 두가지 풀이가 생각남아래는 후자풀이

구하는 값 이분 그래프인지 판별 핵심 아이디어 bfs를 돌면서 visited에 0,1 두가지 타입으로 저장을 함 그리고 반복문으로 그래프를 돌면서 현재노드와 다음 노드가 타입이 같다면 이분 그래프가 아님 tip) 이중 for문 탈출할 때 레이블문 사용하면 간편

구하는 값 동생을 찾는 가장 빠른 방법 핵심 아이디어 수빈위치부터 동생까지 bfs 아래방법은 array로 방문처리를했지만 set으로 하는게 더 간편해보임 코드

구하는 값 4칙연산으로 최소연산횟수구하기 핵심 아이디어 최소연산횟수 → bfs que안에 넣을 때 연산자들을 같이 넣어줌 코드

구하는 값 dfs, bfs를 탔을때 방문하는 노드 순서 핵심 아이디어 dfs, bfs 순차적으로 구현하면됨 코드

구하는 값 나이트의 최소 이동횟수 핵심 아이디어 최소이동횟수이므로 bfs ㄱㄱ 코드

x문제를 풀기 위해 이전에 풀어야 하는 문제 수이전에 풀어야하는 문제를 거꾸로 graph에 넣어서 dfs를 돌며 ans++를 해줌(제발.. 문제를 잘 읽자…)

t보다 큰 연결요소쌍개수3개씩 짤라서 새로운 graph 만들고 상하좌우 훑으며 dfs 돌려 연결요소 카운팅하기

구하는 값 dfs 깊이 핵심 아이디어 dfs 돌리기 코드

구하는 값 dfs 깊이 핵심 아이디어 dfs 돌리기 코드

낮은 높이로만 이동해서 목표지점 도달하는 경우의 수 DFS로만 풀면 시간초과가 생긴다. 다른사람들 풀이를 보니 DP로 메모이제이션을 해줘야 한다고 한다. DP학습 후에 다시 풀어봐야겠다.

트리의 지름이 가장 큰 값처음에는 각 노드마다 첫번째로 다른 노드 가능 경로에서 dfs를 돌며 가장 큰 값을 저장하고 그 값들이 2개 이상인 값들 중 내림차순 정렬을 하여 idx 0,1 인 값을 더해줬다.답은 맞지만 시간초과가 발생하는데 모든 노드에서 다음 경로로 간

구하는 값 노드를 삭제했을때 남은 트리 중 리프노드 개수 핵심 아이디어 dfs로 리프노드 카운팅 방법 삭제하는 노드의 부모에서 삭제하는 노드를 제거 삭제하는 노드에서 dfs로 자손들을 모두 방문처리함 루트노드에서 dfs를 돌며 더이살 갈 곳이없는 노드(graph

구하는 값 나이트가 이동해서 원하는 칸에 도달하기 위한 이동횟수 핵심 아이디어 다른 dfs기본문제랑 크게 다를것 없지만 입력값에서 testcase 별로 나눠서 처리하기 나이트의 이동 경로가 dx = [-2, -2, -1, 1, 2, 2, -1, 1], dy =

구하는 값 수빈이가 동생을 찾는 가장 빠른 방법 핵심 아이디어 수빈 이동 경로 -1, 1, 2 3가지 인데 주의점이 2 는 시간 카운팅이 없다는 것이다. 이거를 놓쳐서 계속 틀렸다. 코드 헤맨 이유가 크게 2가지가 있다.. 수빈 이동 경로 -1, 1, 2

구하는 값 3차원 창고에서 토마토가 다 익는데 걸리는 시간 핵심 아이디어 que안에 익은 토마토를 넣어놓고 상하좌우위아래로 bfs를 돌림 코드1 코드2 3차원을 다루는 방법을 처음해봤다. 시험때만나면 당황했을듯.. 그리고 처음방법으로 삼중for문은 너무 역

구하는 값 토마토 다 익을때까지 걸리는 시간 핵심 아이디어 익은 토마토를 que에 넣고 bfs를 돌린 후 가장 마지막 dep를 출력 만약 0이 남아있다면 0을 출력 코드

구하는 값 VIP좌석을 기준으로 나눠져있는 좌석에 인원 배치하는 경우의 수 핵심 아이디어 각 그룹의 묶음의 경우의수를 곱해주면 됨 근데 이 묶음의 경우의수가 피보나치 수랑 동일함 코드

구하는 값 한개 이상의 연속된 수들의 곱의 최대값 핵심 아이디어 dp[i]를 i를 마지막 인덱스로 하는 연속곱의 최대값이라 정의하자 주의할 점은 i번째 인덱스 값을 무시하고 넘어갈 수 없다. 즉, d[i-1], d[i-1] * arr[i], arr[i] 를 비

구하는 값 포도주 가장 많이 마시는 방법 근데 연속해서 3개는 마실 수 없다는 조건이 있음 핵심 아이디어 점화식을 구해보면 n번째 포도주에 도달할 수 있는 경우의 수는 3가지로 그 중 가장 큰 값이 DPtable[n]이 된다. n번째를 안마시는 경우 → n-

구하는 값 00, 1 을 이용해서 표현할 수 있는 n자릿수의 2진수 개수 핵심 아이디어 n에 1,2,3,4,5, … 넣다보면 규칙이보임 이거 피보나치다..! 그 뒤는 스무스하게 피보나치 구현 코드

구하는 값 피보나치 구할 때 0, 1 번째 값 몇번 사용하는지 핵심 아이디어 피보나치 1,2,3,4,5 하다보면 규칙이 보임 fibo[1] = fibo[1] , fibo[2] = fibo[0] + fibo[1] 이고 그 이후는 이전 값을 사용하기 때문에 피보나

구하는 값 데스 나이트로 갈 수 있음? 핵심 아이디어 데스 나이트 이동경로를 array로 만들고 상하좌우 돌릴때랑 똑같이 하면됨 (주의, y,x 주의할 것) 코드

구하는 값 점프해서 원하는 곳 까지 몇번만에 가는지 핵심 아이디어 que에 idx와 step을 같이 넣어서 bfs로 돌림 코드

구하는 값 원하는 층까지 이동하는데 걸리는 횟수 핵심 아이디어 F+1길이의 arr를 만들어서 각 자리에 몇번째에 방문했는지 기록 초기값은 -1로 해서 방문하지 않았으면 -1 그대로임 bfs를 통해 시작점에서부터 +U, -D 두가지 경우로 다음 층으로 이동 arr

구하는 값 케빈 베이컨 단계 합의 최소값 핵심 아이디어 양방향 인접리스트를 만듬 길이 n+1의 visited 배열을 -1로 초기화하고 각 자리에 방문시 몇번째로 방문했는지 기록할거임 1~n까지 각각 bfs를 돌며 visited배열을 만들어주고 배열의 총합 -1을

구하는 값 bfs로 접근하는 노드 순서 핵심 아이디어 bfs 기초^^ 주의할점은 인접리스트 오름차순정렬부터 해야함 코드 class로 구현이 훨씬 빠름 코드

구하는 값 (0,0)에서 길따라 (n,m)까지 가는 최단거리 핵심 아이디어 간선 같은 최단거리 ⇒ BFS graph에 방문하면 0으로 바꿔주면서 방문체크 que에 좌표랑 dep 같이 저장 코드

구하는 값 범위 내에서 자리 값만큼 점프하며 방문할 수 있는 자리 수 핵심 아이디어 dfs, bfs로 탐색함 3가지 방식으로 풀어봤음 BFS-array 코드 BFS-que 코드 DFS 코드