티스토리

한발짝씩 나아가기

검색하기

블로그 홈

한발짝씩 나아가기

gayoung78.tistory.com/m

78이 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[BAEKJOON] 1153. 네 개의 소수 사용한 알고리즘 에라토스테네스의 체 (소수 찾기) 풀이 로직 소수 = 2 3 5 7 11 13 17 19 23 29,, 1부터 직접 해본 결과 8부터 4개의 소수로 표현할 수 있다. 8 = 2 + 2 + 2 + 2 / 9 = 2 + 2 + 2 + 3 => 2 + 3 + 2+ 2 n이 8이상이고 n % 2 == 0이면 '2 2'로 시작한다. -> n -= 4 n이 8이상이고 n % 2 == 1이면 '2 3'으로 시작한다. -> n -= 5 새로 갱신된 n을 기준으로 에라토스테네스의 체를 이용해 n보다 작은 소수를 찾는다. 코드 공감수 0 댓글수 0 2021. 1. 11.
[LEETCODE] 542. 01 Matrix 사용 알고리즘 DP 사용 풀이 로직 각 원소가 이웃한 가장 가까운 0과의 거리를 구해아한다. 최소값을 구해야하므로 dp를 inf로 두고 진행한다. 왼쪽 위부터 돌면서 왼쪽과 위쪽을 비교해 최소값 찾기 오른쪽 아래부터 돌면서 오른쪽과 아래쪽을 비교해 최소값 찾기 코드 어려웠던 점 처음에 matrix[i][j] == 1인 경우마다 bfs를 이용해 풀었는데, 무한루프로 잘 돌아가지 않았습니다. 공감수 0 댓글수 0 2021. 1. 9.
[SWEA] 3462. 선표의 축구 경기 예측 문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWFUsJvqAegDFAVB&categoryId=AWFUsJvqAegDFAVB&categoryType=CODE&&& 문제 경기는 3분 간격으로 30개 경기 진행 적어도 한 팀이 골을 소수로 득점할 확률 = 1 - 모든 팀이 소수로 득점하지 않을 확률 입력은 퍼센트, 출력은 소수점 5자리로 출력 로직 모든 팀이 소수로 득점하지 않는 것 -> A팀 : 1 - 소수로 득점, B팀 : 1 - 소수로 득점 결과 : 1 - (A가 소수로 득점하지 않음 = 1 - A가 소수로 득점) * (B가 소수로 득점하지 않음 = 1 - B가 소수로 득점) A가 소수로 득점한 .. 공감수 0 댓글수 0 2021. 1. 6.
[PROGRAMMERS] 최고의 집합 풀이 과정 원소의 합이 s가 되는 경우를 모두 구하고 그중에서 최대값을 찾으려했다. 하지만, n > 2인 경우, 경우가 많기도 하고, 규칙을 찾았다. 규칙 : 원소의 곱이 최대가 되기 위해서는 분산이 가장 작아야한다! 코드 공감수 0 댓글수 0 2021. 1. 4.
[BAEKJOON] 4915. 친구 네트워크 문제 출처 : https://www.acmicpc.net/problem/4195 사용한 알고리즘 Union find 문제 -> disjoint set 알고리즘 [ https://gayoung78.tistory.com/75 알고리즘 설명] 풀이 로직 친구 네트워크의 숫자를 위해 하나의 거대한 union network의 parent에 몇명의 친구가 있는지 저장하는 number 딕셔너리를 정의 1. 두 사람의 이름을 입력받은 후, 딕셔너리 parents에 없는 이름이라면 추가해준다. 2. 두 이름을 합쳐 친구관계를 만든다. 3. 현재까지 해당 친구관계를 포함하여 같은 집합에 있는 원소의 개수를 출력한다. 코드 getParent parents 딕셔너리를 참조해 부모노드를 알 수 있다. 입력받는 노드가 부모노드이.. 공감수 0 댓글수 0 2021. 1. 2.
[알고리즘] disjoint-set(union find) 알고리즘 1. union find(disjoin-set)란? 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조 다수의 노드들 중에 연결된 노드를 찾거나, 노드들을 합칠 때 사용하는 알고리즘 1~10까지 있다고 가정할 때, 아래와 같은 연결 구조를 가지고 있다고 가정하자. [ 진행과정 ] 1과 2가 연결되었으면, 원소 2의 정보를 1로 바꾼다. 1, 2, 3, 4가 모두 연결되어있어 같은 집단에 속하지만, 처음에는 각자의 부모노드를 작성한다. 3과 2는 연결되어있다. -> 3의 연결정보를 2로 바꾼다. -> 2와 1은 연결되어있다. -> 3과 1은 연결되어있으므로 3의 연결정보를 1로 바꾼다. 구현 초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화 Union(합치.. 공감수 0 댓글수 0 2021. 1. 1.
[LEETCODE] 51. N-Queens 문제 출처 : https://leetcode.com/problems/n-queens/submissions/ 사용한 알고리즘 backtracking 풀이로직 ㄴㅇㄹㅇㄴ ㄴㅇㄹ 코드 어려웠던 점 backtracking 문제를 간만에 풀어 어려웠고, 이걸 한번에 어떻게 처리하고 다시 돌릴지 고민을 많이했습니다. 제가 푼 과정이 N-Queens의 갯수를 세는 것을 빠르게 할 수 있는 코드였기 때문에 모든 경우를 넣은 후 다시 올바른 형태로 바꿔 집어넣어야했다. board를 바꿔가면서 진행하는데, answer에 넣고나면 그 board를 이용해 바꾸는 것이기때문에 최종값에 계속 초기 board값이 들어갔다 -> board가 계속 바뀌기 때문에 answer의 board도 함께 바뀌는것이다! deepcopy를 이용해서.. 공감수 0 댓글수 0 2021. 1. 1.
[알고리즘] heap 구조 1-1. 힙 자료구조 완전 이진트리 중 하나 -> 웃너순위 큐를 위해 만들어진 자료구조 여러개의 값들 중에 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않음) heapq 모듈은 이진트리 기반의 최소힙 자료구조를 제공한다. 1-2. 힙 종류 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 값보다 크거나 같은 완전 이진트리 가장 큰 값은 언제나 index = 0에 위치함 (=> 이진트리의 루트에 위치) heap[k] >= heap[2*k+1] and heap[k] >= heap[2*k+2] 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 값보다 작거나 같은 완전이진트리 가장 작은 값은 언제나.. 공감수 0 댓글수 0 2020. 12. 30.
[알고리즘] LCS 알고리즘 1. LCS 알고리즘이란? - LCS = 최장 공통부분 문자열 - Substring : 연속된 부분 문자열 ex. x = 'CCAYCKP' y = 'CCAPCAK' - Subsequence : 연속되지 않은 부분 문자열 ex. x = 'ACAYKP' y = 'CAPCAK' 2. LCS 알고리즘 구현 (LCS 길이찾기) 문제 : [백준] 9251. LCS https://www.acmicpc.net/problem/9251 [풀이과정] 0 C A P C A K 0 0 0 0 0 0 0 0 A 0 0 1 1 1 1 1 C 0 1 1 1 2 2 2 A 0 1 2 2 2 3 3 Y 0 1 2 2 2 3 3 K 0 1 2 2 3 3 4 P 0 1 2 3 3 3 4 x와 y에 가장 최근에 추가된 글자가 서로 같으면 b.. 공감수 0 댓글수 0 2020. 12. 28.
[SWEA] 1264.이미지 유사도 검사 문제링크 : swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Q_MqIvUCFAZN&categoryId=AV18Q_MqIvUCFAZN&categoryType=CODE&&& 시간복잡도 On(n^2) 사용한 알고리즘 LCS(최장 공통부분 수열) 알고리즘 풀이로직 LCS 알고리즘 사용 [https://gayoung78.tistory.com/72] 코드 어려운점 이 알고리즘을 알기 전까지 이런 로직으로 구현 x='RBKBGRBGGG', y='BGKRBRKBGB'를 비교할 때 x가 R일 때 y에 있는지 확인하고, x가 RB일 때, y의 index를 활용해서 RB가 있는지 확인하는 방식으로 가려고 했다. 공감수 0 댓글수 0 2020. 12. 28.
[LEETCODE] 17. Letter Combinations of a Phone Number 시간복잡도 O(n^3) 사용한 알고리즘 무슨 알고리즘을까요..? 풀이 로직 각 숫자가 가지고 있는 문자열을 설정한다 0 공감수 0 댓글수 0 2020. 12. 25.
[LEET CODE] 131. Palindrome Partitioning 시간복잡도 O(n^2) 사용한 알고리즘 재귀 알고리즘 풀이 로직 Palindrome인지 확인하는 함수 만들기 Palindrome인 문자라면 list에 추가하고, 그 다음 문자부터 다시 확인 -> 재귀 코드 어려웠던 점 반복되는 과정이라 재귀를 사용해야한다는 것은 파악했지만, 어떻게 처리해야 i에 따라서 추가해줄 지에 대한 고민에서 시간이 생각보다 오래걸렸습니다. 공감수 0 댓글수 0 2020. 12. 23.
[Java] 문자열 붙이는 방법 1. concat() - 합친 문자열을 String으로 생성한다. 2. + - 문자열을 먼저 StringBuilder로 변환한 후 append로 문자열을 더하고 toString()으로 문자열로 변환한다. 3. StringBuilder의 append 이용 ▶ 두개의 문자열을 더할 때는 concat이 좋고, 여러개를 더해줄 때는 StringBuilder를 이용하는 것이 좋다. 공감수 0 댓글수 0 2020. 12. 10.
[Java] String, StringBuilder, StringBuffer의 차이점 1. String, StringBuilder, StringBuffer 공통점 - 문자열을 저장하고 관리하는 클래스 2. String - 한번 생성되면 할당된 공간이 변하지 않는다 = 불변 - 객체 생성 속도가 빠르다(StringBuffer, StringBuilder -> buffer크기 초기 설정 -> 생성속도 느림) - 많은 양의 문자열 수정이 아니라면 String객체 사용이 더 효율적 - 단순 조회 연산에서는 StringBuffer, StringBuilder보다 빠름 3. StringBuilder, StringBuffer - 한번 생성되면 할당된 공간의 크기가 변함 = 가변 - buffer크기 초기 설정해야하므로 생성속도가 느림 - 문자열 연산 등으로 기존 객체의 공간이 부족하게 되는 경우, 기존의 .. 공감수 0 댓글수 0 2020. 12. 10.
[Java] 문자열 활용하기 1. String을 String배열에 한글자씩 저장하기 2. String을 단어를 char배열에 한글자씩 저장하기 3. 가운데 글자 뽑아내기 4. 단어 거꾸로 출력하기 - 궁금증?! String에 문자열 더하는거랑 StringBuilder에 문자열 더하는건 무슨 차이지? 공감수 0 댓글수 0 2020. 12. 10.
[Java] 문자열 치환하기 1. replace(기존문자, 바꿀문자) - 바꾸고 싶은 문자로 문자열을 치환한다. 2. replaceAll(정규식, 바꿀문자) - 바꾸고 싶은 문자로 문자열을 전부 치환시켜준다. ◈replace와 replaceAll의 차이점은?◈ - replace는 기존문자 -> 바꿀문자 - replaceAll은 정규식 -> 바꿀문자 3. replaceFirst(기존문자, 바꿀문자) - 바꾸고 싶은 문자열에 처음 해당하는 문자만 치환시켜준다 공감수 0 댓글수 0 2020. 12. 9.
[Java] 문자열 찾는(검색하는) 방법 1. indexOf() - 대상 문자열에서 찾고자 하는 문자의 index값을 찾고싶을때 indexOf(String str) : 대상 문자열에 String값의 첫 인덱스 값 제공 indexOf(char ch) : 대상 char의 인덱스 값 제공 indexOf(String str, int fromIndex) : 대상 문자열에 String값의 첫 문자의 인덱스를 fromIndex부터 검색 indexOf(char ch, int fromIndex) : 대상 char의 인덱스를 fromIndex부터 검색 - 이때, 주어진 문자열이 포함되어있지 않으면 -1을 리턴한다! 2. contains() - 대상 문자열에서 찾고자 하는 문자열이 포함되어있는지 여부를 알고 싶을때 - 문자열 검색만을 위하면 contains가 가장.. 공감수 0 댓글수 0 2020. 12. 9.
[Java] 문자열 값 비교 1. == - 비교하고자 하는 두개의 대상의 주소값을 비교 - 결과 : 두개의 값이 같지 않습니다. - Heap영역에 s1과 s2의 주소값은 다르기 때문에 두개의 값은 같지 않다. 2. .equals() - 비교하고자 하는 두개의 데이터값을 비교 - 결과 : 두개의 값이 같습니다. - 주소값이 아닌 s1과 s2의 데이터 값만 비교하기 때문에 두개의 값은 같다. 공감수 0 댓글수 0 2020. 12. 9.
[Java] String 문자열 자르기 1. substring - index를 이용해 문자열을 자른다. 2. split - 특정 문자를 기준으로 문자열을 잘라 배열에 넣는다. 공감수 0 댓글수 0 2020. 12. 9.
[Java] Arrays.asList() - 일반 배열을 ArrayList로 변환할 때 사용한다. - java.util.ArrayList 클래스와는 다른 클래스이다. - ArrayList : contains, add 등 메서드를 가지고 있다. -> 사이즈 변경 가능! - Arrays는 원소 추가 메서드가 없다 -> 사이즈 변경 불가! [ List (asList()로 만든 List객체) ] lst에 담겨있는 두번째 인덱스 데이터를 수정했는데 원본 배열의 데이터까지 변경이 되었다. List는 내부 구조가 배열로 만들어져있다. asList()를 사용해 List를 반환해도 배열을 가지게 된다. 이때, asList()로 만들어진 List객체는 새로운 배열 객체를 만드는 것이 아니라 원본 배열의 주소값을 가지고온다. 따라서 asList()로 내용을 수정하.. 공감수 0 댓글수 0 2020. 12. 3.
[Java] add()와 addAll()의 차이 1. ArrayList란? - 단순 배열은 객체 생성시 사이즈를 지정하지만, ArrayList는 사이즈의 제한이 없다 (동적 데이터 구조) - 배열과 같이 순서를 가진다 -> 출력시 index를 사용한다. - 데이터를 추가할 때 add()와 addAll()이 있다. 2. add() - 연결리스트에서 맨 뒤에 새 노드를 연결시키는 것과 같다. -> 뒤쪽으로 데이터가 쌓이고, 순서를 가진다. 3. addAll() - ArrayList에 다른 ArrayList의 데이터를 통째로 붙이기 위한 메서드이다. - 인자로 Collection 객체를 받고 그 Collection에 있는 아이템들을 리스트에 모두 추가한다. 공감수 3 댓글수 0 2020. 12. 3.
[Java] String에서 ArrayList로 만들기 [ 방법1 ] - car이라는 ArrayList를 만들어놓고 carInput(String)을 String배열로 변환한다. - for문을 돌면서 String배열 값을 하나씩 ArrayList에 넣는다 * IntelliJ에서 Iteration can be replaced with bulk 'Collection.addAll' -> more action으로 변경([방법2]) [ 방법2 ] - for문 돌리지 않고 addAll로 작성 * 'addAll()' call can be replaced with parametrized constructor call 뜬다 -> more action하면 [방법3] [ 방법3 ] [ 더 알아봐야하는 것 ] 1. add()와 addAll()의 차이 (gayoung78.tistor.. 공감수 0 댓글수 0 2020. 12. 3.
[JAVA] final은 언제 사용하는 것일까 final은 무엇인가? - final은 엔티티를 한번만 할당하는 것. 두 번 이상 할당하려하면 컴파일 오류가 발생한다. Final Classes Final Methods Final Variables Final 사용 경우 - 함수에 대한 final은 상속하면 절대 안되는 경우에 정의한다. - Override로 인한 실수를 최소화 하고 버그를 줄이기 위해 선언한다. Final 필드의 초기값 주는 방법 1. 필드 선언시 준다 (ex. Final Variables처럼) 2. 생성자를 통해서 주는 방법 - 복잡한 초기화 코드가 필요할 때 - 객체 생성 시에 외부 데이터로 초기화시켜야한다면 공감수 0 댓글수 0 2020. 12. 1.
[programmers] 땅따먹기 로직 - 계속 더해가면서 최대값을 찾는다. 이때, 바로 아래에 있는 값은 사용하지 못한다. - 위 -> 아래 가려면 아래 값을 "val = 아래값" 으로 지정해두고나서 더하면서 max값을 찾아야한다. - 아래 -> 위 가면 그냥 최대값을 찾으면 됨. 이때, 바로 위의 값을 제외한 리스트의 max값을 찾는다. 코드 주의할 점 1. DP사용하기! 공감수 0 댓글수 0 2020. 10. 23.
[programmers] 가장 긴 팰린드롬 로직 [방법1] 1. 팰린드롬 확인하는 함수 만들기 : 결과값은 문자열 갯수 2. i는 문자열 처음부터, j는 문자열 끝에서부터 진행해서 최대값 구하기 -> 끝에서부터 진행하려면 팰린드롬 결과가 True이면 cnt = 팰린드롬 문자열갯수 [방법2] 1. 팰린드롬 확인하는 함수 만들기 : 결과값은 [True, 문자열 갯수] or [False, 0] 2. i는 문자열 처음부터, j는 문자열 끝에서부터 진행해서 최대값 구하기 -> 끝에서부터 진행하려면 팰린드롬 결과가 True이면 cnt = 팰린드롬 문자열갯수 => 큰 값부터 나올거기때문에 더 적게 계산 코드 [방법1] [방법2] 결과 [방법1] [방법2] 확실히 2번 방법이 빠르다!! 공감수 0 댓글수 0 2020. 10. 19.
[programmers] 등굣길 로직 이 그림을 그대로 DP를 이용해 구현한다고 생각하자. 이 문제에서 puddles가 (행, 열)이 아닌 (열, 행)으로 나와있다. 이것을 조심하자!! 코드 주의할 점 1. bfs로 구현했지만, 8번 테케 시간초과 + 효율성 통과율 0%... 2. DP를 이용해서 기존에 있는 값을 활용해서 최종 값을 구한다. 공감수 0 댓글수 0 2020. 10. 17.
[programmers] 정수 삼각형 로직 1. 가쪽에서 더해지는 값은 계속 더해진다. 2. 왼쪽, 오른쪽에서 더해질 수 있는 값 중 최대값을 더해준다. 코드 공감수 0 댓글수 0 2020. 10. 14.
[programmers] 더 맵게 로직 1. 우선순위큐를 이용해서 가장 작은 값, 두번째로 작은 값을 뺀 후, heappush를 이용해서 넣으면 값의 크기를 기준으로 들어간다. 2. 이때, 값을 두개를 빼야하기 때문에 scoville 리스트에 값이 두개 이상 들어가있어야 first, second로 뺄 수 있고, heapq구조이므로 첫번째 값이랑 K랑 비교해서 크면 뒤에 값들은 다 큰것이다. heapq구조이므로, 마지막으로 값이 하나 남아 있을 때, K보다 작으면 -1을 리턴한다. 코드 주의할 점 1. heapq 이해가 필요하다. heappop, heappush를 사용하기 위해서는 우선 리스트가 heapify로 정렬되어있어야한다. 공감수 0 댓글수 0 2020. 10. 10.
[baekjoon] 15686. 치킨 배달 로직 1. 치킨집과 집을 구분한 다음에 M개의 치킨집을 combination으로 조합을 구한다. 2. 치킨집 조합과 집의 거리를 구할 것인데, 최종적으로 치킨집 조합의 최소값을 구하는 것이다. 그러면 집을 돌면서 치킨집과의 거리를 구한다. 각 집마다 최소 길이가 되는 치킨집을 택할 것이다. 그 합이 최소가 되는 거리가 답이다. 코드 공감수 0 댓글수 0 2020. 10. 9.
[programmers] N으로 표현 로직 1. 계산된 값들을 저장하면서 그 값들을 가지고와서 계산한다. -> DP사용 1번 사용 : 5 2번 사용 : 55, 5+5=10, 5-5=0, 5*5=25, 5/5=1 3번 사용 : 555, 5+5+5=15, 5+5-5=5, 5+5*5=30, 5+5/5=6, 5-5+5=5, 5-5-5=-5, 5-5*5=-20, 5-5/5=4, 5*5+5=30, 5*5-5=20, 5*5*5=125, 5*5/5=5, 5/5+5=6, 5/5-5=-4, 5/5*5=5, 5/5/5=0, 555 + 1번사용->2번사용, 2번사용->1번 사용(중복은 제거) 4번 사용 : 555 + 1번사용->3번사용, 2번사용->2번 사용, 3번사용->1번 사용(중복은 제거) 코드 주의할 점 1. num_ls에 넣을 때, x-y, y-x를 동.. 공감수 0 댓글수 0 2020. 10. 6.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.