본문 바로가기

분류 전체보기

 (403)
프로그래머스 - 등굣길(C++) 처음 봤을 때는 응? 이거완전 BFS인데... 라고 생각했으나 일단 (왜인지는 몰라도) 테케 정확도도 통과하지 못했다. 이후에는 문제 분류인 DP로 풀어나갔다. 그러나 얼추맞는 것 같은데 이상하게 통과가 안되서 알아보니 학교의 위치는 m,n 이었다 ! 이 때문에 테스트 케이스를 어느정도 통과했으나 아직 예외가 존재했고 예외를 찾는데는 얼마안걸렸지만 구현이 좀 걸렸다. 일단 풀이 방법은 다음과 같다. 1. x, y 에서 x가 0이거나 y가 0이면 모두 DP[x][y] 는 1이다. 최소로 갈 수 있는 값이 1개 밖에 없다. 2. DP[x][y] 는 현재 위치의 왼쪽과 위의 합이다. 왜냐면 집이 왼쪽 위에 있기 때문이다. 여기까지가 기본이다. 3. 1번에서 [0,1], [0,2] , [0,3] 중 0,2 가 ..
프로그래머스 - 징검다리 건너기(C++) 문제를 보고 든 생각은 이번에도 구현보다는 효율성 문제겠구나 싶었다. https://school.programmers.co.kr/learn/courses/30/lessons/64062 첫번째 생각 : 한 번씩 돌려보면서 -1 하고 돌이 0이되면 0의 갯수확인 -> 당연히 시간초과다. 돌의 최대가 2억이다. 두번째 생각 : 주어진 배열을 오름차순으로 정렬한다. 그리고 0번부터 n번까지 돌려보며 0의 갯수를 확인한다. 이때 첫번째와 달리 정렬된 0번부터 바로 stones를 0으로 정해서 숫자를샌다. 이러면 시간복잡도가 O(N^2) 이기때문에 정확도테스트에선 통과하지만 효율성 테스트를 한개도 통과할 수 없다. 세번째 생각 : 드디어 이분탐색이 떠올랐다. "어 설마.." 하면서 생각은 났지만 구체적으로 구현방법..
프로그래머스 - 단속카메라(C++) 탐욕법으로 분류된 문제이지만 사실상 그냥 구현이라고 봐야할 것 같다. 우선 항상 이런 문제를 보면 정렬을 떠올려야한다. 결과는 같지만 차가 들어오는 순서에 따라 연산이 달라지기 때문이다. 먼저 이 문제는 들어오는 첫번째 들어오는 시간을 기준으로 오름차 정렬하고 푸는게 가장 편하다. 1. i번 차의 나가는 지점을 기준으로 정해둔다. 2. i+1번 차가 들어오는 지점이 현재 기준점보다 오른쪽이다. 즉 기준 카메라로 커버할 수 없으면 카메라를 한개 추가하고 현 i+1번 차의 시작점으로 기준을 다시 잡는다. 3. i+1 번 차가 나가는 지점이 기준점보다 왼쪽이거나 같다. 즉 기준 카메라로 커버할 수 있다. 그럼 카메라의 위치를 i+1번이 나가는 지점으로 바꾼다. 왜냐하면 카메라로 많은 차를 커버해야하기 때문이다..
백준 7490번 0 만들기 (C++) 중복순열로 모든 가능성을 탐색해야한다. 물론 1 2 3 같은 연산은 아에 안하는게 좋지만 그건 너무 어렵고 완전 탐색해도 시간이 오래 걸리지않는다. Time complex 가 O(3^9) 이기 때문에 시간은 널럴하다. 백트래킹 완전탐색으로 중복순열개의 코드들을 검사하면 된다. 조금 어려웠던 건 문자열로 수식을 받아서 처리하는 일이었다. #include #include #include using namespace std; string opbox = ""; char op[3] = { '+', '-', ' ' }; int opSize; int N; int cnt = 1; vector answer; bool check(string str) { for (int i = 0; i < str.size(); i++) {..
객체지향 프로그래밍 - Singleton Pattern 개념/예제 싱글톤 패턴이란, 객체의 인스턴스가 오직 1개만 생성되는 패턴을 의미한다. 그리고 이 생성된 객체를 프로그램 어디서나 접근하여 사용할 수 있는 패턴이다. 여러개의 인스턴스를 생성하지 않고 위험한 전역변수를 사용하지 않고도 전역적인 접근이 가능한 객체를 생성할 수 있다. 싱글톤 패턴을 사용하는 이유 1. 자원의 낭비를 막는다. 2. 전역 변수의 오용을 막는다. 전역변수는 어디서든 접근할 수 있다. 3. 동기화 문제를 해결한다. 단점 1. 커플링이 높아져 객체지향을 해칠수있다. 2. 테스트하기 어렵다. 싱글톤 패턴의 3가지 스텝 1. 생성자를 private로 선언 2. 클래스 내부에서 유일한 인스턴스 생성 private static 3. 유일한 인스턴스에 접근할 수 있는 메서드 제공 그렇다면, 전역변수와 싱..
Java - 문자열 자르기, 문자열 교체, 문자열 카피 1. 문자열 자르기 split : 문자열을 기준에 따라 자른다. 원본 문자열은 바뀌지 않는다. 새롭게 문자열 배열을 구성해야한다. String str = "Java is very hard,C++ is very hard"; String[] splitstr = str.split(","); for(String spl : splitstr) System.out.println(spl); subString : 문자열을 범위에 따라 자른다. 원본 문자열은 바뀌지 않는다. 즉 반환형이다. String substr = str.substring(0, 3); System.out.println(substr); 이 함수의 특징은 0~3부터가 아니라 0~2 까지이다. 2. 문자열 확인, 교체 contain : 포함하고있는가 확인...
Java - Primitive Type / Reference Type Primitive type은 우리가 흔하게 알고있는 int, float 등을 뜻한다. Reference type은 자료구조이다. Arruy, class , interface 등이 속한다. 다른 점은 value 자체를 가리키는 것과 달리 레퍼런스는 주소를 가리키는 포인터형식이다. Java 에는 포인터가 없다. 그러나 포인터가 없다는게 사용자 입장에서 없다는거지 Java는 활발하게 사용중이다. 컴퓨터구조적으로 들어가면 벨류는 스택에서 관리된다. 그러나 Reference들은 크기를 가변적으로 할당해줘야하기 때문에 동적 메모리 Heap에 저장된다. 이러한 형태로 포인터값들이 힙의 값을 가리키고 있다. Runtime Data Area : 런타임에 저장되는 데이터들. 컴파일타임에 정해지지 않고 런타임에 정해지기 때..
멀티코어 컴퓨팅 - Introduce Moore's Law : Doubling of the number of transistors on integrated circuits roughly every two years Clock Speed is not. Currently, CPU clock speed is not increasing rapidly becuase power comsumption and heat genaration is too high to be tolerated in high clock speed CMP : Chip MutiProcessor SMP : Symmetric MultiProcessor Amdahl's law : Potential program speedup is defined by the fraction of code ..

티스토리툴바