출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
DFS 풀이 - python에는 recursion limit 이 존재해서 런타임 에러 발생 가능성 있음.BFS 풀이
n 값이 10^6 이기 때문에 이중 for문(O(n^2))으로 풀면 시간 초과가 날 확률이 매우 높다.O(n)으로 쭉 순회하면서 해결된 값은 stack(스택과 같은 역할을 하는 리스트) 에서 바로 제거, 해결 되지 않은 값은 stack에 남겨둔 채로 계속 진행.
조건을 복잡하게 달기에도 로직이 너무 꼬이고, dfs/bfs로 구현하기에도 복잡하다.DP를 응용해서 해결한다. \- 어느 값에 도달하는 최소 횟수를 구하는 것이기 때문에 계산한 값과 배열에 저장된 값을 비교해서 더 작은 값으로 바꾸고 \- 이를 계속 반복해서 수행하
조합을 이용해서 풀려고 했으나 N이 10^5 이기 때문에 시간초과.무게의 종류는 901가지이기 때문에 우선 중복 제거 후 접근해야 했음.Counter 를 이용해 종류와 개수 뽑기.
출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges
처음 문제를 읽고 binary search를 생각해내기 쉽지 않았다.그러나 n이 생각보다 너무 크다면(10^9) binary search로 풀 수 있는지 먼저 생각해보자.
조건에 맞게 복잡한 구현을 하려고 하다보면 무조건 시간초과가 난다. (그리고 구질구질 너무 복잡해진다)최대한 일관성을 유지하는 단순한 풀이법을 생각해보자.cap 과 비교하면서 배달한 상자를 매번 빼고 업데이트 할 필요 없이 한번에 cap을 빼준다.그리고 만약 값이 음수
DP 기법으로 간단히 풀 수 있다.최종결과에 도달하기 전, 어떤 상황이 있을 수 있을지 생각해보면 간단하다.iteration을 하며 리스트에 저장한 값들을 저장해놓고 필요할 때 다시 계산할 필요없이 쓰면 O(N).Tabulation 기법출처
BFS/DFS 로 접근하는 것은 너무 깊어져서 시간초과가 유력해 보인다. (특히, DFS)각 자리 숫자 마다 판단 + 이전 자리 숫자 고려해서 조건을 잘 만들어 푼다.출처: 프로그래머스 연습
문제는 매우 쉽지만, 완전탐색이 가능하다는 조건을 캐치하는 능력은 필요하다.출처:
lambda function 으로 sort를 하는 방법에 대해서 아는지 물어보는 문제이다.기준이 1개일 경우: 기준이 여러 개일 경우:참고) 오름차순, 내림차순 변환은 기준 컬럼에 (-)를 붙이면 됨.참고 사이트: https://blogboard.io/blog
defaultdict 선언 시 초기화를 lambda로 하는 법 알아두기.
가장 큰 수를 유지할 때 쓰기 좋은 자료구조: Max Heap(최대힙)!문제의 세부 조건을 따져 엣지 케이스 판별능력 중요무적(k)의 수가 도출한 결과값(cnt) 보다 클 경우 k가 정답.enemy 배열의 길이가 무적(k) 보다 작을 경우 작은 쪽이 정답.출처:
이중 for문으로 돌리면 반드시 시간초과가 날 것이다. (n=10^6)반복문을 굳이 2번 돌릴 필요 없이, 한번만 돌려도 된다.반복문 안에서 더하는 값은 양의 정수의 배수로 커지기 때문이다.
최소 힙(min heap) 자료구조를 알고 있으면 매우 쉬운 문제.만약 최소 힙을 안쓰더라도, 구현 능력으로 풀 수 있어야 하는 문제.그러나 일반적으로 이런 쉬운 구조는 코딩테스트는 나올 확률이 적기 때문에 실전에서는 시간초과가 날 수 있음.따라서 연습에서는 항상 좋은
가장 먼저 defaultdict 이 떠올랐다.괜찮은 아이디어지만, 그 전에 Counter로 원소 별 개수를 간단히 세주는 작업이 필요했다.
소수 개수 구하는 공식(N=a^x \* b^y (a,b는 소수)일 때, (x+1) \* (y+1)) 을 먼저 생각했음. 그러나, 시간 초과.복잡하게 생각하지 말고, 오히려 순회하면서 공약수 개수만 구해주는 것이 더 나은 풀이.
내림차순 정렬하면 min value를 유지할 필요가 없음.조건 잘보고, 쓸데없는 로직 추가하는 것을 조심하자.
최대공약수로 접근할 생각을 처음에 하지 못했음.만약 큰 수가 조건을 만족하지 않을 때, 그의 약수도 따져보아야 한다고 생각했기 때문.그러나, 조금만 더 생각해보면 k로 나누어지는 배열의 수들은 k의 약수들로도 나누어지는 것이 당연하므로 신경쓰지 않아도 된다.
조건에 맞는 도서와 저자 리스트 출력하기없어진 기록 찾기있었는데요 없었습니다오랜 기간 보호한 동물(1)보호소에서 중성화한 동물상품 별 오프라인 매출 구하기상품을 구매한 회원 비율 구하기그룹별 조건에 맞는 식당 목록 출력하기출처: https://school.pr
스트링 역순 표현을 이용한 깔끔한 구현 풀이.출처: 프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges
문제 조건이 복잡해 보여서 그렇지, 차근차근 조건만 따라가면 쉽게 풀리는 문제였음.조건에 나온 예외처리 상황들도 꼼꼼히 체크해주는 것이 필요.출처: 프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges
먼저 생각한 풀이는1\. list를 str으로 변환시켜서2\. 패턴에 맞는 스트링을 find3\. substring을 이어붙여서 기존 배열을 고치고 반복하는 것이었음.하지만 테스트 케이스 2개에서 계속 시간초과가 남.기존 배열에 substring으로 이어붙이고 새로 a
알파벳을 한개씩 통과시키면서, 패턴이 맞는 단어를 만나면 지우는 풀이.prev를 저장시키고 비교하는 과정이 있어야 함.연속된 단어를 처리하는 로직이 내 풀이보다 더 나은 풀이라 생각됨.스트링의 replace 메서드에서 바꿀 단어가 없으면 그냥 아무 일 없이 스무스하게
조건대로 더하고 빼기만 하면 되는 간단한 문제였는데, 답을 더할 때 b를 곱해주지 않아서 한참 헤맴.예시 테스트 케이스에서 b=1인 경우만 나와 있어 실수한 것 같다. 더 꼼꼼하게 문제를 풀어야겠음.프로그래머스 연습문제, https://school.progra
한 번 순회 O(n)이 시간적으로 널널하다고 생각되어도, 그 안의 로직에 substring을 조회해서 재할당 한다던가, substring을 다시 참조해서 len 값을 비교한다던가 하면 시간 복잡도는 더 이상 같지 않다.따라서, 최대한 이런 수정을 피할 수 있도록 설계하
이런 류의 문제를 보면 시도해볼 수 있는게 combinations, DFS/BFS, 직접 구현(완탐) 정도가 있을 것 같다.하지만 DFS나 완탐은 n이 큰 조건이 달려있으면 시간초과나 recursion depth에 걸리지 않을까 불안하다.따라서, BFS를 시도해봄직 하
Stack 형식을 deque로 구현함.무난한 구현이라고 생각했으나 테스트 케이스 4개에서 시간초과첫번째 생각한 로직은 order 배열을 돌면서, mainStack에 item이 있는지 확인하는 if item in mainStack 이었는데, 이 탐색 부분에서 시간을 많이
n=1000으로 상대적으로 원소개수가 적어서 안심될 수 있으나, 생각나는 로직이 O(n^3)으로 만만치 않았음.연속 부분수열의 합을 구하는 과정에서 쓰인 합이 계속 사용되고 있으므로 누적합 개념을 이용해서 값을 재사용하면 시간을 많이 줄일 수 있을 것이라 생각.순환하는
아이디어 자체는 Counter 를 사용해 문자열의 갯수를 세어주고 다시 정렬한 뒤 다시 문자열로 합쳐주면 되는 문제이다.그러나 예외처리를 할때, 공통된 정수의 자릿수가 최대 10^6이기 때문에 이걸 그대로 int로 바꿔서 ==0 비교를 한다던지, 결과를 반환하게 되면
처음 풀 때 로직과 코드는 잘 짰다. 그러나 계속 3-4개의 테스트 케이스에서 시간 초과가 났다.반복문 탈출 조건에 문제가 없는 것 같은데, 참 희한했다.그 답은 pop(0)에서 찾을 수 있었다.list의 pop(0) 보다 deque로 전환하더라도 popleft() 를
defaultdict 를 이용하면 편한 무난한 구현 문제이다.프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges
처음에는 아이디어를 생각하지 못했다.아예 화살 0개를 쏘거나(점수 포기), 어피치+1 개를 쏘거나(점수 쟁취)또, 구현도 만만치 않았다. 고민한 결과, DFS 백트래킹이 따져야 할 경우의 수도 그렇고 구현하기에 가장 수월해 보였다.중간 중간에 세밀한 조건 처리도 중요했
꼼꼼하게 조건을 보며 구현하면 무난한 문제이다.시간 적게 쓰고 푸는 것을 연습하자.프로그래머스 연습문제: https://school.programmers.co.kr/learn/challenges
조건에 맞게 침착하게 따라가면 무난한 문제다.소수 판별 함수, list -> string으로 만드는 join 메서드에 대해 확실히 알아두자.프로그래머스 연습문제, https://school.programmers.co.kr/learn/challenges
아주 간단한 구현 문제지만, 코드를 간결하고 최적화 하기 위해서는 노력이 필요하다.예를 들면, 나는 처음 코드를 짤 때 신고자가 몇 번 신고 당했는지의 defaultdict, 그리고 누가 누구를 신고했는지의 또 하나의 defaultdict 를 선언해서 풀었다.하지만,
이 문제는 보면 DFS 백트래킹으로 풀면 되겠다 느낌이 온다.하지만 로직을 깔끔하게 짜는 것에 집중하자.백트래킹은 dfs 전후로 visited 배열을 갱신하고 되돌리고 하는 과정의 반복이기 때문에 굳이 시작 순서를 주지 않아도 알아서 모든 경우를 탐색하는 방법이다.그대
문제를 보면 단순 노가다 후 문자열 처리를 하는 문제는 아님은 감이 온다.조금만 생각해보면, 2차원 배열은 눈속임이고 n\*n 배열에서 시작과 끝 지점을 n을 가지고 나눈 몫과 나머지라는 점을 캐치할 수 있다.그래서 나는 위 코드같이 짰는데, 아래 코드는 다른 사람이
처음 문제를 봤을때, 할인 종류가 4종류, 최대 이모티콘 개수는 7개. 그러니까 완전 탐색을 해도 4^7(즉, 2^14가지, 그리고 user 마다 각각 반복문을 돌려도 약 160만 가지) 넉넉하다고 판단했다.그 생각은 쉬웠는데, 중복 순열을 구성하는 단계에서 고비였다.
삼성 코테 형식을 익히기 위해 SWEA 사이트에서 문제를 풀기 시작했다. 역시 적응이 좀 필요할 것 같다. input.txt로 입력 받아오고 제출할 땐 또 주석처리 해야 하는 것과, 모든 테스트 케이스가 하나의 코드의 반복문으로 실행된다는 점(프로그래머스는 테스트 케이스 별로 하나의 함수가 여러 번 실행됨), 파이참 ide로 작성 후 복붙해서 제출해...
D4 난이도도 무난한 듯 하다. 기본적으로 삼성 코테는 복잡한 구현, 탐색(dfs, bfs, 완전탐색 with 자료구조 최적화) 의 문제를 많이 좋아하는 듯 보인다. 시간초과는 가장 주의해야 할 점이지만, 이 정도 난이도에선 그다지 신경 쓸 필요 없이 구현만 되면 되는 것 같다. 문제 출처: https://swexpertacademy.com/mai...
역시 삼성 기출답게 복잡한 구현 문제였다.문제 상황 자체는 bfs만 잘 사용하면 돼서 그렇게 까다롭진 않았는데, 아무래도 이런 류의 문제가 익숙하지 않다보니 시간이 엄청 걸렸던 것 같다.그리고 각각의 함수에서 global을 선언하지 않아도 변수가 참조될 수 있다는 사실
구현을 시작하면서 생각보다 로직이 꼬이고 조건을 여러 개 달면서 디버깅을 하다보니 아, 이렇게 하는거 아니다. 이런 식으로 짜면 나중에 엣지 케이스에서 분명히 걸려서 통과 못한다 는 생각이 강하게 들었다.결국 엣지 케이스에서 걸려서 구글링으로 답을 봤는데, 생각보다 로
BFS 응용에 관한 간단한 문제였다. 처음엔 시간 초과가 약간 염려되긴 했지만 맵 최대 크기가 8\*8 이여서 괜찮다고 판단했다.여기서 한 가지 새로 안 사실은 파이썬에서 리스트를 메서드 파라미터로 넘겨서 메서드 안에서 바꿔도 그대로 반영 된다는 점이다. 즉, Pass
구현 문제를 풀 때, 자꾸 예외 상황을 처리하려고 조건문을 거는 습관이 있는데 그러면 로직이 너무 복잡해지고 디버깅도 까다롭고 시간도 많이 걸린다.예를 들면, 처음에 풀 때 일단 맵에 물고기가 존재하는지 search 함수 로 확인을 하고 존재한다면 bfs 를 돌리는데
구현 로직이 생각보다 복잡하지는 않았다. 하지만 두 가지 이유로 풀이 시간이 엄청나게 걸려 버렸다.첫번째는 문제의 조건과 입력이 1행 1열 부터 시작했고 그렇게 입력을 줬다는 점이다. 나는 당연하게도 0행 0열 부터로 생각하고 코드를 짰는데 입력이 1씩 커졌고 예외 처
처음에 문제를 풀 때 접근 로직을 잘못 설계했다. 문제에서 다음과 같이 설명하고 있다.여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다.이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다.
조건대로 설계만 하면 풀리는 무난한 구현 문제였다.다만 로직을 더 깔끔하게 짜는 연습을 하기에 좋은 문제인 것 같다.예를 들어, 문자열 단위를 1~len(s) 만큼씩 잘라 temp라는 배열에 넣을 것이라면,위와 같은 식으로 처리하면 로직은 맞지만 코드가 너무 길어지고
이 문제의 포인트는 각각의 item이 꼭 어떤 방에 들어갈 것인지 정하지 않아도 된다는 것이다.오히려 위와 같이 풀면 구현이 너무 복잡해지고, 어떤 방에 어떤 우선순위로 들어갈지 로직을 세우는 과정에서 예외 케이스가 많이 생겨 틀릴 확률이 높다.입실과 퇴실을 하나의 배
완전탐색이 가능한 상황임을 인지하는게 포인트인 문제였다.경우의 수는 기껏해야 7! + 6! + ... + 1! 정도가 나오니 완전탐색을 하기에 문제 없었다.완전탐색으로 가능하다는 사실을 알게되면 그 다음은 순열, 소수 검증 함수를 만들어 구현을 꼼꼼히 하는게 다였던 문
문제에서 total_size가 소수이거나 가로 세로 개수와 yellow 의 개수가 맞지 않는 상황의 인풋은 주어지지 않음을 알 수 있으므로 간단하게 로직을 작성할 수 있다.세로 길이보다 가로가 길기 때문에 역순으로 따져 내려오면서 답을 구해주면 된다. 무난한 문제이다.
한개씩 트리의 간선을 끊어보고 둘로 나누어진 트리 크기 차를 구할 수 있느냐의 문제였다. 처음으로 든 생각은 DFS였다. 나누어진 두 트리의 노드를 기준으로 dfs를 수행하면 트리의 개수가 나오고, 나머지는 전체에서 그 크기를 뺀 만큼의 크기일 것이다.풀이를 마치고,
word의 길이가 1이상 5이하 밖에 되지 않으므로 직접 중복순열 사전을 만드는 것이 가능하다는 것을 알아내는게 중요하다. 즉, 완전탐색이 가능한 문제이다.그 다음은 중복순열을 위한 product 임포트와 적절한 구현이다.문제 출처: https://school
엣지 케이스를 상당히 많이 확인해야 하는 조금 까다로운 문제였다.핵심 알고리즘 자체는 순차적으로 탐색하고 나머지와 비교하면서 swap 해주면 되는 간단한 로직이었지만,최대 수를 만들고 swap 횟수가 남았을 때의 처리, 같은 수를 바꾼 카드의 경우 swap 횟수를 차감
우선 모든 가능한 경우를 조합으로 나타내도 타임 아웃이 걸리지 않는다는 것을 파악하면 매우 쉬운 문제이다. 다만 score, cal를 하나의 자료구조로 넣고 그 안에서 조합을 돌려 특정 부분에서만 합(sum)을 구하는 로직을 잘 기억해두자. combCal = [
전형적인 BFS 문제라고 생각했다. 여기서 조금 변형을 주어야 한다는 점을 일찍 깨닫고 Dijkstra 로 바로 갔어야 했는데, 그러지 못했던 점이 조금 아쉽다. 길의 중복은 상관없고 무조건 도착점에 작은 가중치의 합으로 도달해야 하므로 visited 배열은 사용
BFS 적용하면 바로 풀리는 문제였다. D4 문제치고는 너무 쉬운 문제였다. grid 크기도 4*4 이고 문자열 길이도 7로 맞춰놔주어 모든 지점에서 bfs를 돌려도 시간초과를 걱정할 필요가 없었다. 문제 출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4...
dfs/bfs를 사용해서 몇 개의 무리가 있는지를 찾아내는 문제였다.dfs가 개인적으로 더 사용하기 편해서 썼고, 이 때 visited 배열 조건을 잘 세팅해주는 것이 중요했다. init() 함수와 global 키워드로 깔끔하게 작성하는 것을 연습하자.출처: https
D2 단순한 오타로 시간이 좀 걸렸었는데 로직 자체는 어렵지 않았다. 꼼꼼하게 + 형태 체크하고 x 형태 체크하는 구현 능력 문제였음
D2 역시 꼼꼼한 구현 문제. 3x3, 9x9 체크 로직만 잘 설계하면 끝나는 문제였다. 이중 for문에서 초기화 로직 짤 때 더 주의하면 좋겠다. 출처: https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYj2mga6ZewDFASl&contestProbId=A...
90도, 180도, 270도 상황별로 어떤 식으로 출력되는지만 파악하면 되는 문제다.그런데 출력이 조금 생각해 볼만 했다.회전배열이 다음과 같이 출력되어야 했기에각 회전배열마다 출력하는 것이 모든 배열의 한 줄씩 출력씩 출력해야 했던 것이 생각해볼만한 포인트였다.출처:
단순한 linear 구현이었지만 범위 index 설정을 잘못해서 두 번 틀림.. 이 부분 신경써야겠음! 출처:https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYj2mga6
쭉 나와있는 값들의 최빈수를 구하는 아주 간단한 문제였다.Set으로 바꾼 뒤 순회하면서 업데이트 해주는 방식으로 간단하게 풀렸다.출처: https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solv
첫번째 풀이
문제에서 대놓고 완전탐색을 하라고 가이드를 주었기 때문에,n=10, 순열(permuation) 사용 가능.따라서 가능한 순열쌍을 전부 만들고 완전탐색을 돌리면서 답을 갱신하면 풀리는 간단한 문제였다.만약, 효율성을 요하는 문제였다면 더 어려운 문제가 되었을 것이다.출처
전에 파이썬 코드로 풀었던 문제를 java언어로 다시 풀어보았다.삼성 B형은 파이썬을 지원하지 않는데다가 현재 다니고 있는 ssafy에서도 자바로 월말 시험이나 코딩테스트를 보기 때문에 java로 코테를 연습해야 될 필요가 생겼다.웹 개발은 이전에도 java Sprin
첫번째 풀이두번째 풀이주어진 2가지 변환조건으로문자열 S -> 문자열 T로 만들 수 있는지를 판단하는 문제였다.처음에는 백트래킹으로 풀었는데 시간초과 가 났다. 아무래도 경우의 수가 너무 많았던 것 같았다.그래서 역방향으로 목표 문자열에서 차감해서 처음 문자열이 되는지
전형적으로 단계별로 나눠서 빡세게 구현시키는 삼성 코테 문제였다.첫번째 도망자 이동, 두번째 술래 이동, 마지막 시야 체크 후 잡기이렇게 크게 3
출처: https://www.codetree.ai/training-field/frequent-problems/problems/tree-kill-all?page=3&pageSize=20
D3 난이도 측정이 잘못됐나 싶을 정도로 간단한 문제였다. 결국 조건대로라면 가장 작은 자연수(1) 로 잘라야 하기 때문에, 자르는 방법에 관계없이 자르는 횟수는 정해져있다. 따라서 홀수, 짝수에 따라 답이 결정된다. 출처: https://swexpertacad
출처: https://www.acmicpc.net/problem/1966
BFS 로 풀면 되겠다는 생각이 처음 든다.하지만 전형적인 BFS 문제는 아니라서 어려운 문제라고 생각했다.내가 생각하는 전형적인 BFS 문제는 dx, dy 배열로 상하좌우 이동하며 아직 방문하지 않은 장소를 탐색하는 문제였는데,이 문제는 그런 식으로 탐색하면 6553
Java로 풀어본 알고리즘 문제였다.우선 자바로 입력을 받는게 무척 익숙하지 않았는데, InputStream으로 BufferedReader 를 선언하고 readLine() 메서드를 통해서 입력을 한 줄씩 읽어오는 방법이었다.처음에는 StringTokenizer로 nex
순열(permutation) 을 돌리거나 백트래킹(dfs) 를 쓸 경우, 최악의 경우 20! 를 연산해야 될 수 있다.이렇게 되면 무조건 시간초과다.따라서 앞자리 수를 계속 결정해나가면서 k를 줄여나가야겠다고 생각했다.(n-1)! 을 기준으로 몫과 나머지를 계산해서 앞
자바로 순열 문제를 풀어봤다.파이썬으로 풀면 평소같으면 바로 itertools permutation 써서 제출했겠지만, dfs 한땀한땀 만드는 것은 너무 익숙치 않았다.\*\*자바로 입력받는 법, 배열과 리스트 다루는 법에 더 익숙해져야겠다.출처: https:
역시 자바로 입력받고 정렬하는 과정이 익숙하지 않았다. 생각보다 시간이 더 걸렸지만 논리가 어려운 문제는 아니었다.n 최대횟수 1000번에 리스트 sort() 를 돌리는건 너무 무식한 코드인 것 같아 max, min, index 를 받아와 처리했다.출처: https&#
역시 자바로 풀어봤다.로직 자체는 매우 간단했고 반복문의 index 문제만 신경써주면 바로 풀리는 문제였다.출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7G
주어진 조건에 맞게 입력받고 단순 구현하면 되는 간단한 문제였다.하지만 출력형식이 조금 까다로워서, 따로 함수로 빼서 처리해주었다.출처: https://www.acmicpc.net/problem/1244
아이디어가 중요한 문제였다.처음에는 문제를 읽고 어떻게 풀어야 될지 감이 안잡혔다.우선 직사각형의 좌표 정보만을 받아서 겹치는 부분을 어떻게 표현할지, 그리고 둘레 정보만을 어떻게 뽑아낼지 애매했다.그러다가 문득 든 생각은 점의 좌표를 칸으로 생각해서 직사각형이 존재하
그룹을 어떻게 나누고 최단거리의 합을 어떤 식으로 계산해야 하는가의 아이디어를 생각하기 까다로운 문제였다.우선 센서 간의 차이를 계산해서 정렬했으면, 그 배열에서 0 부터 N-K 전 까지의 원소들이 바로 최소 거리들이라는 사실을 알아채는 것이 중요하다.왜냐하면 오름차순
유명한 문제다. 풀 때마다 느끼는 거지만 조건을 하나씩 따지기 보다 로직을 크게 보는 훈련이 되는 것 같다.행 별로 훑으면서 들어갈 위치(열)를 배정하고, 그 자리가 대각선과 세로 줄을 검토해보았을 때 통과라면 계속 진행, 아니라면 멈추는 방법의 생각보다 간단한 방법이
크게 복잡하지 않은 조합 문제였다.결국 course 에 있는 수로 모든 조합을 만들어 구현하기 되면 풀리는 문제이기 때문에 특별히 어렵다고 느끼지는 못했다.하지만 만약 파이썬으로 짜지 않고 Java로 짰다면?itertools>combinations 와 같은 편리한 라이
Java 코드Python 코드문제의 핵심은 한번 쭉 순회하면서 앞선 수를 계속해서 비교해야 한다는 것인데, N의 크기가 10^9 이기 때문에 이중 for문은 무조건 터진다는 것이다.따라서 O(N)으로 만들어야 한다.문제를 보자마자 프로그래머스 뒤에 있는 큰 수 찾기 문
풀면서 특이했던 점은 왔던 길을 또 가도 상관없다, 즉 visited 배열이 소용이 없다는 것.따라서, bfs 를 쓰기 애매해진다.왜냐하면 visited 배열을 체크를 안해주면서 bfs를 돌리면 그 경우의 수가 정말 너무 많아지기 때문이다.문제에서도 답을 String의
프로그래머스 호텔 대실 문제와 굉장히 유사하다고 생각했다.https://school.programmers.co.kr/learn/courses/30/lessons/155651하지만 큰 차이점이 있는 부분은,방이 한 개 있고 그 중에서 진행할 수 있는 최대 회의
이전까지 자판기 문제라 하면 W원을 만들기 위해 필요한 가장 적은 수의 동전 류 라고 할 수 있겠다.근데 이 문제는 가능한 많은 수의 동전을 사용해야 하는 문제이다.그래도 달라질 건 없다.각 동전의 금액이 서로의 배수, 약수 관계이기 때문에,금액이 적은 동전부터 시작해
놓을 수 있는 파이프라인의 경우의 수 가 아니다.놓을 수 있는 파이프라인의 최대 개수 이다.이게 그리디를 생각해낼 수 있는 포인트다.만약 전자라면, R\*(3^C) 이다.=> 열에서 각 행의 위치당 3가지 탐색을 하고 열을 끝까지 이동하는 모든 경우의 수.이러면 어떻게
우선 문제를 첫번째 봤을 때, dp 생각을 못했다.하지만 알고력, 코딩력 2가지의 척도가 있고 시간에 따라 계속해서 작은 값을 유지해야 하기 때문에 이차원 배열의 dp를 생각하는게 자연스러웠다.이 부분이 이 문제에서 얻어갈 첫번째 아이디어이다.그런데 dp를 생각했음에도
두 구역으로 나누고 그 안에서의 합 결과의 최솟값을 구하는 문제였다.처음에는 dfs 로 접근을 해볼까 고민도 해봤지만, 백트래킹으로 돌아오는 조건을 구현하는 부분에서 도저히 모든 케이스를 커버하는게 불가능해 보였다.예를 들어서, 1-2-3 (2에 연결된 4) 즉, 3에
10달 전에 이 문제를 풀어봤던 기억이 난다. 그 때는 풀지 못했는데 오늘은 시간, 정확성 면에서 깔끔하게 풀어냈다. 그 기간 동안 알고리즘 면에서 실력이 늘었다고 느껴진 부분이었다.처음에 문제를 봤을 때 N과 M의 크기가 작음(N=50, M=10) 에도 불구하고 시간