꾸준한 개발일기

포인터란 메모리에서 메모리를 가리키기 위한 개념이다. 선언부 &: ~~의 주소 *: ~~의 주소를 저장하는 포인터 변수 #include int main(void) { int n = 50; int *p = &n; //&: 's address int p2 = &n; // compile erorr: 주소값을 포인터변수가 아닌 변수에 저장 printf("n: %d, n's address: %d", n, p); printf("n: %d, n's address: %d", n, (int) p); // compile error: 포인터변수:8byte. int:4byte 서로 다른 크기의 자료형 } n의 주소(&n)는 반드시 포인터변수 (자료형 *)에 저장해야 한다. 포인터가 아닌 일반 변수에 저장하면 (ex. int ..

리뷰 소요시간: 55분 오래걸린이유: 1. 문제를 잘못 파악함 다음칸이 벽인 경우 다음 칸으로 이동하는 것이 아니라, 현재방향 기준 다다음 칸으로 이동하도록 구현해야함. 2. 잘못구현으로 인한 디버깅 3차원배열로 visited 체크를 해야하는데, 위 1번의 이유로 2차원배열로 visited 체크를 진행하였음. (로직에 따라 2차원배열도 가능할 것으로 보임) ※ 어떤 상태에서 최단거리로 방문하는지 고민할 것 ※ 이 후의 탐색에 영향을 미치는 상태가 무엇인지 고민할 것 제한 1. 세로길이R, 가로길이 C: 1~100 → O(R^4) 유형 Goal: (1, 1) → (R, C) 최소시간 구하기 이동시간이 모두 동일하게 1이고, 최소시간을 구하는 문제이므로 0-1BFS BFS 설계 BFS는 방문한 당시의 "상태..

리뷰 소요시간: 1시간 입력값의 크기가 매우 작음에 힌트를 얻고, 완전탐색으로 방향성을 잡음 재귀로 순열을 자유롭게 구현할 수 있느냐가 관건인 문제 State Space Tree를 그려놓고 접근하면 훨씬 편리하다) 나머지 구현은 하드코딩으로 구현해주면 됨 제한 1초, 512MB 세로N, 가로M (1 ~ 8) CCTV 최대개수: 8개 O(8!) 완탐 가능 유형 Goal: CCTV의 방향을 정하고, 사각 지대의 최소크기 구하기 → 완전탐색, 시뮬레이션 시뮬레이션 설계 0. 관리대상 격자: 빈칸(0), CCTV(1~5), 벽(6) CCTV: 위치, 방향유형, 방향 1. 완전탐색: 순열구하기 State Space Tree 설계 private static void permutation(int idx) { // b..

리뷰 제한된 시간복잡도 O(N)을 만족하기 위해 정렬을 사용해야하는 문제. 제한된 시간복잡도를 만족하기 위해 어떻게 시간복잡도를 줄일 수 있는지 생각하는게 중요. 소요시간: 1시간 오래걸린이유: 합쳐지는 경우 인덱스 갱신 부분에서 코드 오류. 디버깅에 시간 소요. 문제 풀이 제한 배열의 개수: 1~10,000 → O(N)까지 가능 유형 Goal: 겹치는 배열들을 모두 합치고, 최종적으로 겹치지 않는 모든 배열 i들의 [Si, Ei]를 출력 → 시간복잡도를 고려한 구현문제 설계 1. Intervals 배열 start 오름차순 기준 정렬 ∵ 한 번의 배열 탐색으로 O(N)만에 끝내기 위함 2. 배열 합치기 합쳐지는 경우 갱신 (targetStart 기록 answer.add(new int[] {targetSt..

리뷰 소요시간: 1시간 오래걸린이유: 문제에 대한 설계는 끝냈지만, 10진수 → 2진수 변환을 몰라서 못푼 문제. Integer.toString() 메소드나 Integer.toBianryString() 메소드 등 기본 메소드 숙지할 것. 문제 풀이 제한 지도 한 변 크기 n: 1 ~ 16 각 원소 x를 이진수로 변환 시, 길이는 n 이하. 0 ~ 2^n-1 유형 Goal: 비밀지도의 암호를 해독하기 → 구현문제 설계 1. 보드만들기 int[] arr1, int[] arr2 정보를 바탕으로 10진수 → 2진수 변환 [row][col]이 하나라도 1이면 board[row][col]에 '#', 아니면 ' ' 구현 import java.io.*; import java.util.*; class Solution {..

리뷰 소요시간: 40분 30분정도에 끝낼 수 있었는데, 테스트케이스 2개가 틀려서 디버깅을 조금 진행함. 문제풀이 제한 캐시크기 C: 0 ~ 30 도시 수 N: 1 ~ 100,000 → O(N) 유형 Goal: 캐시 크기에 따른 실행시간 측정. 입력된 도시이름 배열을 순서대로 처리할 때의 총 실행시간 * hit = 1, mis = 5, 캐시: LRU → 도시들을 한 번씩 순회하며, 캐시 hit/miss에 따른 실행시간을 측정하면 되므로 그냥 구현문제 설계 1. Cache는 List로 사용 LRU이므로 Queue를 사용할까 했지만, hit된 도시를 최신으로 갱신하기 위해서 remove를 해야하므로 List를 사용 2. Cache Hit / Miss 에 따른 구현 구현 import java.io.*; imp..

리뷰 소요시간: 1시간 10분 오래걸린 이유: 문자열 점수|보너스|[옵션]에 대한 parsing작업이 오래걸림. for문으로 직접 구현하는 방법은 번거로울 것 같고, 정규식을 이용하면 될 것 같은데 잘 떠오르지 않았음. 문제풀이 제한 점수|보너스|[옵션]으로 이루어진 문자열 3세트 점수 N: 0~10 → O(N!) 보너스: S, D, T중 하나 옵션: *, #중 하나, 없을 수도 있다. 유형 Goal: 문자열에 대한 총점수 구하기 → 구현문제 설계 1. 문자열 3세트의 다트게임 문자열로 Parsing하기 점수 Parsing: 정규식 이용 보너스 Parsing: 정규식 이용 옵션 Parsing: 정규식 이용 2. 라운드별 다트게임 점수 계산하기 보너스 적용하기 옵션 적용하기 코드 import java.io..

리뷰 해당 문제는 완전탐색 → 완전탐색 조합 → 이분탐색으로 이어지기까지 시간복잡도를 어떻게 단축시킬 수 있는지, 접근 방법에 대해 생각해본 좋은 문제였다. 1. 조합을 구하는 시간복잡도가 너무 크면 가지치기가 큰 의미가 없을 수 있다. 완전탐색으로 조합을 모두 구하는 경우는 O(3000 C 3)으로 TLE가 발생한다. 하지만, 다른 풀이가 생각나지 않았고 promising (유망함)으로 가지치기를 시도하였으나 TLE가 발생하였다. 이럴 경우, 시간 복잡도를 만족하는 다른 풀이를 생각해보자. 2. 시간복잡도를 줄여나가는 과정: 시간복잡도를 쪼개고 어느 부분의 시간을 단축시킬 수 있을지 고민하자. 시간복잡도를 줄여나가기 위해선 처음에 완전탐색부터 시작할 것이다. 완탐의 시간복잡도에서 정확히 어느 부분의 계..

리뷰 공간복잡도를 고려하지 못해 틀린 문제 제한 - 시간: 1초, 메모리: 128MB - 표의 크기 N: 2 ~ 10,000 - 이동시키려는 숫자의 수 K: 1 ~ 1,000 - O(N^2), O(K*N)까지 가능하며 완전탐색의 경우는 아닐 가능성이 크다는 결론을 내릴 수 있다. - 이동시키려는 숫자당 O(N)을 넘지않는지 주의하자. 유형 Goal: 숫자 K개를 이동시키는데 필요한 회전의 수 표가 수행할 수 있는 행 회전, 열 회전 연산이 있으며 문제에서 주어진 방식 그대로 구현하는 시뮬레이션 문제임을 파악할 수 있다. Worst Case N = 10,000, K = 1,000 공간복잡도: 표를 직접 구현하면 N^2 * 4byte / 1024 / 1024 = 약 381MB로 공간복잡도가 터지게 된다. 표..

제한 시간: 2초, 메모리: 512MB 참가자수 N : 1 ~ 5,000 → O(N^2) 까지 가능하며, 완탐은 안되고, 시간 복잡도를 고려해야하는 문제임을 파악할 수 있다. 유형 Goal: 어떤 티셔츠를 입고 있는 사람이 기념품을 받는지 구하라 게임을 통해서 기념품을 받을 사람을 정하고, 그 게임은 정해진 규칙에 따라 진행하면된다. → 시뮬레이션 문제 Worst 시간복잡도 1. 한단계 씩 한 명씩 제거된다. → 4999번의 단계를 거쳐야한다. 2. 리스트 또는 배열의 원소를 하나씩 순회하는 방식은 약 5000^3번 순회해야하므로 TLE이다. → 순회없이 O(1)만에 다음 제거대상을 찾아야한다. 시뮬레이션 설계 1. 다음 제거대상을 찾는다. 2. 제거한다. 3. 게임 종료조건이면 종료한다. 다음 제거대상..