윤프로 | 코드가 개발새발해

[문제출처 | https://www.acmicpc.net/problem/27737 ]💭접근 방식해당 문제는 Java로 먼저 풀었기 때문에 접근 방식은 이전 포스트로 대체한다.본진은 자바인데 프론트엔드 직군 코테를 위해 시작한 자바스크립트 풀이도 함께 올린다.DFS나 BFS를 자바스크립트로 풀며 느낀 조심할 부분은 재귀의 범위가 자바보다 작다는 것이다.자바에서 통과한 로직을 그대로 자바스크립트로 작성했는데 서브태스크 1만 성공하고 2는 틀렸다.뭔가 큰 수에서 탐색할 때 문제가 있나 싶어 BFS로도 풀었는데 문제는 다른 곳에 있었다. (풀이 과정에 계속..)큐에 탐색 칸을 담는 BFS 알고리즘으로 풀기 위해 visited 변수를 추가했다.📝풀이 과정변수visited : 탐색한 map 칸을 구분하기 위한 ..

[문제출처 | https://www.acmicpc.net/problem/27737 ]💭접근 방식처음 문제를 읽었을 땐 이전에 풀었던 섬의 개수, 토마토와 비슷한 느낌을 받았다.전형적인 DFS, BFS 문제로 구역을 탐색하며 흔적을 남기고 그때마다 카운팅한 어떤 결과물을 도출하는 것.문제 내용 중 한 칸에 여러 개 포자를 겹쳐 심을 경우 범위가 더 늘어난다는 예시 이미지를 보고 순간 생각이 많아졌는데..(BFS에 DFS까지 합쳐야 하는 문제인가? 해당 칸에 1개만 심을 경우, 2개 심을 경우, X개 심을 경우 퍼져 나갈 수 있는 칸은 X * K 개니까.. 헉 그럼 어떻게 풀어야하지? \(°_o)/ )이러다 날 샌다.. 일단 겹쳐 심는 경우는 제쳐두고 하나씩 심는 경우에서 풀어나가 보자.시작은 섬의 개수 ..

이 포스팅은 '누구나 자료구조와 알고리즘 개정2판' 을 스터디한 내용을 바탕으로 작성하는 공부기록이다. 알고리즘어떤 과제를 완수하는 명령어 집합어떤 자료 구조를 이미 결정했더라도 코드의 효율성에 영향을 미칠 수 있는 중요한 요인 선형 검색왼쪽에서 오른쪽으로 한 번에 한 셀씩 확인하며 값을 찾는 방식원소 수만큼 단계가 필요하다. (N개의 원소가 있을 때 검색에 필요한 단계는 N단계)이진 검색계속해서 중간 지점을 골라 남은 수 중 반을 제거해 나가며 값을 찾는 방식.정렬된 배열에서만 쓸 수 있다.원소 수를 두 배로 늘릴 때마다 검색에 필요한 단계는 한 단계만 늘어난다. (대단히 효율적인 부분)구현public static void main(String[] args) { // 이진검색 구현 실습 int[] ar..

[문제출처 | https://www.acmicpc.net/problem/1012 ] 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 기본적인 BFS 코드를 가지고 무난하게 적용해 볼 수 있는 문제였다. 단, 주의할 점은 가로길이, 세로길이, 가로좌표, 세로좌표의 순서로 받는다는 점! 보통 행->열 순으로 받는데 이 경우는 열->행 순으로 입력이 들어온다. 비슷한 문제로 백준 섬의 개수 문제가 있다. 이웃한(4방) 1의 뭉텅이가 몇개인지 찾는 문제였다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util..

[문제출처 | https://www.acmicpc.net/problem/11558 ] 구현 그래프 이론 그래프 탐색 시뮬레이션 처음에 문제를 접하고 아 쉽네~ 했다가 이상한 곳에서 파고들다가 길을 잃었다.. 처음엔 1차원 배열에 인덱스는 각 사람의 번호라치고, 값은 그 사람이 가리키는 사람의 번호를 담았다. 그리고 while문을 돌며 주경이 번호(N)가 걸릴 때까지 돌면서 주경이를 가리키는 사람의 인덱스를 출력하게 접근했는데.. 그래프 탐색인데 인접행렬이나 인접리스트를 쓰는게 낫나? 사이클이 돌면?, 주경이를 가리키는 애가 없거나, 주경이를 가리키는 애가 희현이로부터 연결되어 있지 않다면? 위의 생각들로 class Node를 만들었다가 배열리스트를 썼다가, 연결리스트를 썼다가... 삽질이란 삽질은 다 했..

[문제출처 | https://www.acmicpc.net/problem/16173 ] 구현 그래프 이론 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 깊이 우선 탐색 기본적인 BFS 로직으로 풀 수 있는 문제였다. 보통 4방 탐색인 것과 달리 오른쪽, 아래 2방 탐색이라는 점. 그리고 map에 쓰여진 칸만큼 이동한다는 것 정도만 주의하면 될 것 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 통과 124ms public ..

[문제출처 | https://www.acmicpc.net/problem/11729 ] 재귀 학부 시절 과제로 받았던 하노이 탑... 이론은 알겠는데 이걸 코드로 짜라구요..? 눈물을 머금었더랬지 재귀의 시작, 재귀의 꽃이라 할 수 있겠다. 이론은 간단하다. 문제 설명 그대로 1번 장대에서 3번 장대로 원판을 모두 옮기는 것! 단, 크기가 제일 큰 게 맨 아래로 작은 게 맨 위에 위치하도록 한다. 옮길 땐 한 개의 원판씩, 작은 원판 위에 큰 원판이 올라갈 수 없다. 먼저 장대를 시작, temp, 최종 으로 생각하고 풀어나가도록 한다. 이동하는 횟수가 최소가 되어야 한다는 점에서 여러가지 수를 가정해야 하나? 했는데 그냥 불필요한 이동을 하지 않으면 된다.. 이동 횟수를 먼저 출력하고 그 다음에 이동한 이..

[문제출처 | https://www.acmicpc.net/problem/2606 ] 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 1번 컴퓨터(정점)로부터의 인접 정점 개수를 구하는 문제라고 생각했다. 그래서 DFS를 이용해 매개변수로 1을 넘기고 그것과 연결된 노드를 찾아가며 카운트하도록 했다. 보통 for문이라고 하면 int i = 0 이 익숙하지만 int가 자료형이고 Node도 자료형으로써, 배열로 만든 Node를 반복문으로 돌리는 것도 가능하다! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; // 통과 132..

[문제출처 | https://www.acmicpc.net/problem/1325 ] 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 정답비율 안 보고 이번 주 스터디에 제시한 문제... 그래프 탐색 분류에서 실버길래 괜찮지 않을까~ 가져왔는데 일단 테케도 하나뿐이고 보아하니 시간초과나 메모리초과로 꽤나 골치아픈 문제였다.(오답)첫 풀이는 백준 바이러스 문제와 비슷해보여서 단방향 연결로 받는데 이때, 'A가 B를 신뢰할 때 B를 해킹하면 A를 해킹할 수 있다는' 부분에서 B->A 로 접근을 했다. 1. 근접리스트로 B행에 A리스트를 쌓고 ( adjList[b].add(a) ) 2. 배열을 돌며 각 행 리스트의 사이즈 값이 큰 인덱스를 찾아(=신뢰되는 경우가 많은 컴퓨터) 3. 배열을 돌며 그 인덱..