Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43163?language=java 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 풀이 모든 경우들을 dfs로 탐색해가며 만약 현재단어가 target과 같다면 answer값을 갱신시켜주었다. 탐색하는 방법은 1. 현재 단어와 탐색하지 않은 단어들을 비교한다. 2. 1개를 제외한 알파벳이 같은 단어가 있다면, 해당 단어를 탐색했다는 체크를 해준뒤, 현재 단어로 갱신시켜준다. 3..

2021. 11. 21.

문제풀이/프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43162?language=java 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 두가지 방법의 풀이가 있다. Union-Find 알고리즘을 사용하는 방법과 BFS를 사용하는 방법 두가지가 있다. 1. Union-Find 알고리즘 인접행렬로 주어진 정보를 이용해서 i!=j && computers[i][j]==1 이라면 두 컴퓨터 사이에는 네트워크로 연결이 된것이므로, i와 j를 Union 해준다. 모든 노드..

2021. 11. 19.

문제풀이/프로그래머스

https://programmers.co.kr/learn/courses/30/lessons/43165?language=java 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 풀이 DFS를 이용해서 문제를 해결했다. 첫번째 원소부터 마지막 원소까지 탐색을 하면서, 해당 원소를 덧셈했을때와 뺄셈했을때의 경우를 모두 구해준 뒤, 마지막 원소까지 탐색을 했고 그 경우에 target과 같다면 answer를 +1 해준다. 시간복잡도 숫자의 개수는 2~20개 이고, ..

2021. 11. 19.

체크리스트

11.15 11.16 11.17 11.18 11.19 11.20 11.21 알고리즘 1문제 이상 시험준비 1일 1커밋 1일 1포스팅 ---그날 그날 푼 문제, 기록하고 싶었던 내용들을 기록--- 11.15 11.16 11.17 11.18 11.19 -[프로그래머스] 타겟 넘버 (https://programmers.co.kr/learn/courses/30/lessons/43165?language=java )[Level 2] -[프로그래머스] 네트워크 (https://programmers.co.kr/learn/courses/30/lessons/43162?language=java) [Level 3] 11.20 11.21 -[프로그래머스] 단어 변환 (https://programmers.co.kr/learn/c..

2021. 11. 19.

체크리스트

11.08 11.09 11.10 11.11 11.12 11.13 11.14 알고리즘 1문제 이상 시험준비 1일 1커밋 1일 1포스팅

2021. 11. 19.

문제풀이/백준oj

https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 말을 살짝 바꿔서 잘라야되는 전깃줄을 구하는것이아닌, 자르지 않아도되는 전깃줄의 최대값을 구해준다고 생각을 하면 쉽게된다. 그럼 여기서 자르지않아도 되는 전깃줄의 최대값은 어떻게 구해줄까? 방법은 바로 증가하는 수열의 최대길이를 구해주면된다. 이를 위해 Lower_bound함수를 구현해준 뒤, 자르지않아도 되는 전깃줄의 최대값을 구해주어 N에서 빼주면 답이 나온다. 시간복잡도 ..

2021. 11. 7.

문제풀이/백준oj

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 2번째줄에 사자를 놓는 경우를 생각해보자 왼쪽에 놓기 위해서는, 1번째줄에 사자가 오른쪽에 있거나 1번째줄에 사자가 없어야한다. 오른쪽에 놓기 위해서는, 1번째줄에 사자가 왼쪽에 있거나 1번째줄에 사자가 없어야한다. 놓지 않기위해서는, 1번째줄에 사자가 왼쪽,오른쪽,없는 3가지 경우 모두 가능하게된다. 위를 일반화 하면 다음과 같다. i번째줄의 왼쪽에 놓기위해서는 i-1번째 줄의 오른쪽에 사자가 있거나, i-1번째 줄에 사자가 없다. i번째줄의 오른쪽에 놓기위해서는 i-1번째 줄의 왼쪽에 사자가 있거나, i-1번째 줄에 사자..

2021. 11. 7.

문제풀이/백준oj

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 풀이 먼저 N명의 정보를 입력받은다음에, 모두를 조건에 맞게 비교를 했다. 이때 compareTo메소드를 오버라이딩해서 height와 weight값 모두가 자신보다 큰 경우를 추가시켜주어서 문제를 해결했다. 시간복잡도 이중for문으로 해결이 가능하기때문에 O(N2)이 된다. 코드 import java.util.*; public class Main { static Vector v=new..

2021. 11. 5.