Algorithm/문제 풀이

[Programmers - JAVA] 타겟 넘버

programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 풀이 요새 프로젝트로 알고리즘을 한동안 안했더니 감을 잃어서 되찾으려 기초부터 다시 시작. 문제에 덧셈/뺄셈으로 타겟넘버를 만든다는 문구 존재. 더하는 방법 & 빼는 방법을 구현하기 위해 DFS를 활용. 과정 매개변수로 numbers 배열 , target이 넘어온다. DFS호출 (배열, 타겟번호, 인덱스번호, 되는 경..

2020. 8. 31. 05:11

Algorithm/문제 풀이

[BAEKJOON_2493 - JAVA] 탑

문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net 풀이 예전에 풀다가 못풀었던 문제를 다시 시도.(다시보니 처음보는 느낌) 오른쪽에서 왼쪽 방향으로 레이저를 쏘기 때문에 오른쪽부터 시작한다고 생각할 수 있지만, 최악의 경우 n!의 복잡도가 발생할 수 있다. ( 풀이 풀가능) 역으로 가장 좌측의 탑부터 계산하는 방법 사용(stack 활용). 다음 탑이 스택 최상(가장 최근의 탑)의 높이보다 큰 경우, 이전 탑의 정보를 pop한 뒤 pu..

2020. 7. 2. 04:09

Algorithm/문제 풀이

[BAEKJOON_3109 - JAVA] 빵집

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴� www.acmicpc.net 과정 DFS를 활용. 우상, 우, 우하 순서대로 3방 탐색을 진행. 파이프가 연결된 경우(끝열에 도착) static에 위치한 boolean type의 root 변수를 true로 변경. if문을 타고 root를 활용해 재귀 탈출. root = flase 초기화. 출발가능한 행만큼 반복후 출력. 풀이 별도의 방문관리 없이 해당 값을 변경해주었다. 만약 해당 자리를 지나는 파이프가 연결되지 않더라도 그 길을 ..

2020. 6. 27. 11:15

Algorithm/문제 풀이

[BAEKJOON_10026 - JAVA] 적록색약

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 과정 4방탐색을 활용한 완전탐색. 정상인의 구역을 확보한 후, 적록색약이 보는 그림으로 변형. (기존 그림을 다시 사용하지 않기 때문에 값을 변형) (주의 : 만약 복사를 한다면 2차원 배열은 clone으로 깊은 복사가 되지 않는다. 직접 만들어서 사용해야한다.) 이후 변수들의 초기화에 신경을 쓰고 다시 똑같은 완전탐색을 실행. 풀이 정상인과 적록색약이 보는 구역을 각각 출력하는 어렵..

2020. 6. 27. 07:25

Algorithm/문제 풀이

[BAEKJOON_11724 - JAVA] 연결 요소의 개수

문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net 과정 ArrayList를 활용한 정점 및 간선 관리. visit 관리를 통한 연결 요소 개수 확인. 풀이 연결 요소란 나누어진 각각의 그래프로 고립된 부분을 생각하면 된다.(연결 요소 = 연결 성분) DFS, BFS 모두 사용가능. 2차원 배열을 사용해도 무관하지만, ArrayList를 활용해보고자 진행. BufferedWri..

2020. 6. 27. 06:33

Algorithm/개념 정리

[Algorithm] 연결 성분(Connected Component)

연결 성분(Connected Component) 나누어진 각각의 그래프 그래프는 여러개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수있다. 즉, 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 연결 성분이라고 부른다. 연결 성분의 특징 연결 성분에 속한 모든 정점을 연결하는 경로가 있어야 한다. 또, 다른 연결 성분에 속한 정점과 연결하는 경로가 있으면 안된다. 연결 성분을 찾는 방법은 DFS,BFS 탐색을 이용하면 된다. 연결 성분을 찾는 방법 연결 성분을 찾는 방법은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)을 이용하면 된다. BFS,DFS를 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 된다. 다음에 방문하지 않은 정점을 선택해서 ..

2020. 6. 27. 05:24