분류 : brute-foce, 재귀
분류 : stack, 수학(계산)
분류 : 구현, 시뮬레이션
분류 : 완전 탐색의 유연한 생각
분류 : 그리디 / 리스트의 중복을 제거하며넛 순서를 보장 받는 법
링크n의 값이 100,000까지 입력가능하기 때문에 기본 탐색 반복문(시간복잡도 : O(N^2))을 사용하면 시간초과로 인해 정답을 맞출 수 없다. 따라서 투포인터를 사용해서 풀이해야만 한다.포인터 방식은 크게 두가지 방식이 있는데,(1) 앞에서 시작하는 포인터와 끝에
링크다익스트라 알고리즘을 그대로 구현하여 풀이하는 문제이다. 따라서 다익스트라 알고리즘 개념과 구현방식을 알고있다면 바로 정답을 맞출 수 있다.따라서 풀이 과정은 간략한 주석으로 대체하고, 관련 포스팅 링크를 첨부하겠다.코드는 아래와 같.다익스트라 알고리즘과 플로이드
링크서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값을 구하는 문제이다. 자연수 N이 최대가 되려면 가장 작은 자연수인 1부터 차례대로 더해나가야 한다. i를 현재까지 더한 자연수의 개수, cur을 현재 값이라고 했을 때계속 i를 1씩 증
링크문제 한 줄 한 줄을 그대로 코드화 시키면 되는 구현 문제이다. 처음엔 그래프 알고리즘으로 풀 수 있을까 싶어 고민하다가, 그냥 완탐으로 풀었다.4중 for문이 들어가긴 하지만 가능한 n의 최댓값이 50이므로 50^4 < 2000만이라 충분할 것이라 생각했기
링크백트래킹인가 고민하다 잘 모르겠어서 결국 다른 풀이를 참고해서 풀었다.전형적인 dp 문제였다 (ㅋㅋ) 시간제한도 0.5초이기 때문에 매우 빨리 풀어내야 한다.dp는 1) 문제를 작게 나눠서 보고, 이후 2) 점화식을 찾으면 된다.1) 문제에서 '가치의 합이 k원이
링크직전에 2293번 동전1 문제를 풀었기 때문에 매우 순조롭게 풀이할 수 있었다. 해당 문제도 전형적인 dp 문제이다.dp 풀이 순서대로 1) 문제를 작게 나눠서 보고, 이후 2) 점화식을 찾아보자.1) 문제에서 '가치의 합이 k원이 되는 동전 최소 개수'를 구하라는
링크이코테 음료수 얼려먹기 문제와 완전히 똑같은 방식의 문제이다.bfs와 dfs 두 방식으로 모두 풀이 가능하지만, 본인은 dfs 방식이 더 편하기 때문에 dfs 방식으로 풀이했다. 코드는 아래와 같다.2차원 리스트 형태의 배열 arr 생성해 집과 벽의 정보를 저장해두
링크⭐️ 경우의 수를 구할 때엔 반사적으로 백트래킹, 그리고 itertools 를 떠올리자 ⭐️ 먼저 문제를 살펴보면,음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면 그 수를 '감소하는 수'로 정의하고 있다. 예를 들어 321과 950은 감
링크아무 스킬 없이 dfs와 bfs를 구현하면 되는 문제이므로 해설은 생략하겠다.한 번 짚어볼 만한 것은 인접리스트를 활용해 그래프 정보를 저장하는 방식이다. 각 노드마다 연결된 모든 노드를 기입하기 위해 graph\[a].append(b) 뿐만 아니라 graph\[b
링크이코테의 음료수 얼려먹기 문제랑 거의 동일한 문제이다.문제의 포인트는 일단 우리 병사와 적국 병사의 그룹, 그리고 각 그룹의 인원수를 파악해야 하는 것인데 이는 bfs로 쉽게 구할 수 있다. (물론 dfs로도 풀이 가능) bfs 동작 과정은 아래와 같으며, 아직 b
링크이코테의 미로 탈출 문제와 완전히 동일하다.이 문제 또한 bfs()를 이용해주면 되는데, 가장 왼쪽 상단 지점부터 시작하여 bfs()를 수행해 이동 가능한 칸을 차례차례 방문한다. 이 때 방문 여부와 이동 거리를 표시하기 위해, 특정 노드를 방문하면 그 이전 노드의
링크백준 전투 문제와 비슷하며 난이도는 더 쉽다.bfs()를 이용해 음식물 그룹을 파악함과 동시에 음식물 개수를 반환한다.따라서 모든 위치에 대하여 bfs()를 수행하였을 때 반환되는 음식물 개수의 최댓값을 최종 결과값으로 지정하여 출력하면 된다.매우 쉬우므로 해설은
링크그래프 정보를 인접리스트에 잘 담고, 1을 루트 노드로 하여 bfs()를 수행한다. 이 때 다른 노드를 방문할 때 마다 cnt를 1 더해준다.bfs() 실행이 끝나면 cnt 값을 출력해 주면 된다. bfs()를 모든 노드에 대해서 돌릴 필요없이 1을 루트 노드로 하
문제 링크 풀이 문제를 다시 찬찬히 살펴보자. 정수 A를 B로 바꾸려고 할 때 가능 한 연산은 아래 두 가지이다. 2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. 다시 말하면,
링크백준의 A->B 문제와 매우 유사하다. 차이점은 A->B 문제에서는 최소 연산 횟수만 구하면 되지만 이 문제에서는 최소 연산으로 연산 가능한 경우의 수 까지 함께 구해야한다는 점이 다르다. 아무튼 이 문제 또한 bfs로 풀이하면 쉽게 답을 찾을 수 있다.일단 위치
링크백준의 숨바꼭질2 를 풀어본 사람이라면 기세등등하게 숨바꼭질3도 풀어봤을 것이다. 숨바꼭질3에서 달라진 점은 2\*X 위치로 이동할 때는 시간이 걸리지 않는다는 것이다. 그래서 본인은 해당 문제를 보자마자 heapq으로 풀어봤는데 (시간 순 원소 정렬을 위해) 시간
링크숨바꼭질 시리즈를 깨는 맛이 있다.이번 문제는 수빈이가 동생을 찾는 가장 빠른 시간을 구하는 것은 동일하나, 그 경로까지 출력해야한다. 따라서 경로 파악을 위해 visited 리스트와 같은 크기의 move 리스트를 만들어주었다. move의 인덱스는 현재 위치를 의미
문제 링크 풀이 최단시간을 구하는 것이니 해당 문제 또한 bfs로 풀어주면 된다. 이전 숨바꼭질 문제들과 다른 점은 visited 배열이 2차원으로 생성된다는 점인데 현재 화면에 나와있는 이모티콘 개수가 동일하더라도 클립보드에 저장되어있는 이모티콘 개수에 따라 연산
링크문제에서 제시한 그대로 풀이한다면 배열의 상어가 존재하지 않는 모든 원소에 대하여 bfs()를 진행하여 반환된 최소 안전 거리의 최댓값을 구하면 된다.그 코드는 아래와 같다정답이지만 시간이 매우 오래걸린다.역발상을 해보자 (내가 한 것은 아니고 다른 분의 풀이이다)
링크난이도가 있는 문제인 만큼 바로 풀어내진 못했다. 현재 이동 방향을 기준으로 원소를 계속 삽입해야한다는 아이디어는 생각했으나 어떻게 코드를 짜야하는 지에 대한 감이 부족했다 🥲문제 내용은 다른 보통의 bfs 문제와 비슷하게, 출발점과 도착점이 존재하고 주어진 ma
링크전형적인 dp 문제이다.1일까지 밖에 없을 때의 최댓값2일까지 밖에 없을 때의 최댓값3일까지 밖에 없을 때의 최댓값...N일까지의 최댓값이런식으로 계속 나아가다 보면 결국 총 주어진 일 수인 N일까지 얻을 수 있는 이익의 최댓값을 구할 수 있다.문제 예시에 따라 순
링크언뜻 보면 그래프 알고리즘같이 생겼으나, 모든 경로의 개수를 체크하는 것이므로 중복되는 부분 문제가 생긴다. 따라서 해당 문제는 dp로 풀이하면 된다. 먼저 dp 테이블은 게임판 크기만큼 n\*n 크기의 이차원 배열로 만들어준다.가장 오른쪽 위는 dp0=1로 초기화
링크너무나도 전형적인 dp 문제!최적 부분 구조와 중복 부분 문제가 한 눈에 보이기 때문이다. 풀이 방식은 정수 n에 대하여1로만 1~n까지 만드는 경우의 수1,2으로 1~n까지 만드는 경우의 수1,2,3으로 1~n까지 만드는 경우의 수이런식으로 계속 나아가다 보면 결
링크함수의 유형은 배열을 뒤집을 수 있는 R과 배열의 첫째 수를 버리는 D 두 가지이다. 또한 함수는 조합해서 사용 가능하며 이들은 모두 연속적으로 수행되어야한다.해당 문제는 배열로 파이썬의 리스트 자료형을 사용할 경우 reverse()나 pop(0)를 수행 할 때마다
링크아주 베이직한 bfs 문제이다. 왜 골드이지 싶은..?먼저 익은 토마토가 존재하는 배열의 인덱스 좌표값을 큐에 모두 삽입한 후, 이들을 하나씩 popleft()하면서 상하좌우에 있는 값에 (자신의 값+1)을 더해주며 업데이트 하면 된다. 값이 -1인 경우는 토마토가
링크사실 본인은 union-find 문제 유형임을 알고 풀이에 들어갔지만, 그럼에도 한 번에 아이디어를 못 떠올렸다 🥲문제를 읽다보면 자연스레 서로소 집합구조 문제란 것은 쉽게 알아차릴 수 있긴하다. (여기서 플레이어 순서는 풀이할때 전혀 상관하지 않아도 됨) 그래서
링크일단 문제를 이해하는 데 조금 시간이 걸린 것 같다. 보자마자 dp 문제임을 알았고 매우 빠르게 풀이했으나 자꾸 틀려서 막바지엔 다른 풀이의 힘을 빌렸다. 조금 아쉽지만 틀린 이유를 찾는 과정에서 큰 깨달음을 얻어서 만족스러운 문제이다.dp는 아래의 사이클을 돌며
링크먼저 dp는 아래의 사이클을 통해 업데이트 되며 dp 테이블은 n의 크기만큼 1e9로 초기화해준다.1칸까지 점프하는데 필요한 에너지 양의 최솟값 2칸까지 점프하는데 필요한 에너지 양의 최솟값3칸까지 점프하는데 필요한 에너지 양의 최솟값...n칸까지 점프하는데 필요한
어찌저찌 풀어냈는데 고작 실버면 한숨 정답율도 50% 육박하면 한숨 두번 여러모로 양심없는 유형이다 욕을 적고 싶지만 참고 포스팅 해보겠다
링크매우 쉽다. 호흡이 매우 긴 삼성 기출 풀다가 이거 푸니까 행복하다..일단 2차원 배열 3개를 만든다.speak 사회자가 말하는 순서대로 값을 적어둔 2차원 배열생각해보니 굳이 이건 2차원 배열로 만들지 않아도 된다board보드판 2차원 배열bingo사회자가 부른
링크이진수로 바라보고 풀어야하는 문제이다. 이것만 깨달으면 답은 매우 쉽게 찾을 수 있다. 문제를 보다보면 이진수로 문제를 해결해야겠다는 감이 오는데그 이유는 물의 양이 1, 2, 4, 8, 16, ... 이렇게 2의 제곱 형태일 때만 합칠 수 있기 때문이다.먼저 문제
문제 링크 풀이 2차원 배열에서 이동하면서 가져올 수 있는 사탕의 최댓값을 구하는 것이 문제이다. 언뜻 보면 bfs나 dfs로 풀어야할 것 같지만 해당 문제의 정석 풀이는 dp로 풀이하는 것이다. bfs와 dp 문제 구분법 bfs 간선의 가중치가 모두 같을 때
링크참가자가 이동할 수 있는 경우가 2개 이상일 때 어떻게 처리하지?처음 시도한 방식 : candidate라는 리스트를 선언해서 후보지를 모두 모으고, 우선순위에 따라 sort()하여 첫번째 값을 꺼내는 방식으로 구현함위 방식으로 해도 틀리진 않는 것 같음. 그러나 해
삼성 기출에서 자주 나오는 코드 유형들을 추려봤습니다 혹시 자주 나오는 또다른 유형이 있다면 댓글로 알려주시면 감사하겠습니다 🙇🏻♀️
> 💡 먼저 모듈, 패키지, 라이브러리에 대해 짚고 넘어가보자 라이브러리 : 여러 패키지와 모듈을 모아둔 것 패키지 : 특정 기능을 하는 여러 모듈을 모아둔 것 모듈 : 함수와 변수, 클래스들을 모아둔 것. 일반적으로 파일 하나( 모듈.py )가 모듈이다. > 즉, 라이브러리 >= 패키지 >= 모듈 이다. 참고로 특정 기업의 코딩테스트에서는 사용할 ...
링크공격자 선정부서지지 않은 포탑 중 가장 약한 포탑이 공격자로 선정가장 약한 포탑 선정 기준 (우선순위 순)공격력이 가장 낮은 포탑가장 최근에 공격한 포탑(행+열)의 합이 큰 포탑열 값이 가장 큰 포탑공격자에겐 n+m 만큼 공격력 부여 공격대상 선정부서지지 않은 포탑
링크최근 삼성 기출 풀면서 문제 읽고 풀고 디버깅하는데 2시간 이내로 끝내본 적이 없는데 해당 문제는 그래도 꽤 빠르게 풀어서 집나간 자신감을 조금이라도 되찾게 해준 문제이다.나선형 코드를 이미 알고 있고, 일차원 배열 관점에서 풀이해야겠다는 두 가지 아이디어만 갖고
링크처음 제출하자마자 채점률이 쭉쭉 오르길래 1트에 성공하는 줄 알았는데 시간초과가 떠서 1시간 가량 헤메다 결국 정답 코드의 도움을 조금 빌렸다. 웃긴건 내 코드의 경우 bfs 시간초과 때문이 아닌 것 같긴 하지만 . . ㅋ 해당 문제에선 bfs 최단경로를 파악해야
링크정답률보고 만만하게 봤으나 결코 그렇게 만만하진 않았던 문제이다. 그래도 최근 기출 문제 중에서는 쉬운 편에 속한다. 그래도 제약조건이 많지 않아서 테케만 맞추면 무난하게 정답을 도출해낼 수 있는 문제였던 것 같다(디버깅을 안해서 너무 행복했다)해당 문제에서의 ke
링크특별한 테크닉 없이 문제에서 주어진 상황대로 함수화해서 짜면 된다. 실제로 구현할 때에도 막힘 없이 1시간 내로 풀이해서 제출하였다. 그러나 역시나 한 번에 성공하지 못했고 예외 처리 안 한 부분이 한 곳 있어서 정답을 맞추지 못했던 것 같다 board : 나무 &
링크복제 마법을 진행한다. 결과 자체는 나중에 반영된다.모든 물고기가 이동한다못 가는 경우 : 가려는 좌표에 상어가 있거나 물고기 냄새가 있거나 격자 범위가 나감갈 수 있을 때까지 자신의 방향을 45도 반시계 회전시킨다그래도 없으면 이동하지 않는다 -> 방향 원래대로
링크크게 도망자 이동 그리고 술래 이동이 세트가 되어 하나의 턴을 이루고 있다.도망자 이동 함수는 매우 쉽게 구현 가능하고 술래 이동이 굉장히 까다롭다하나의 턴 안에 나선형 알고리즘을 온전히 사용하는 것이 아니라 하나의 턴마다 한 칸식 나선형 알고리즘에 따라 이동해야하
링크말그대로 빡구현 문제이다.정말 이렇다할 테크닉이 없고 대신 2차원 전역 배열 내에서 관리되어야하는 정보들 자체가 꽤 많기 때문에 실수 없이 꼼꼼히 구현해야하는 문제이다.현재 시점에서 무얼 저장해야하는지 어떤걸 건들일때 어떤 또다른 배열을 건들여야하는지를 계속 되새김
링크문자열 s에 대하여 g 크기 만큼 슬라이딩 윈도우 기법으로 탐색해가며 문자열 w 와 매치하는 부분이 있으면 카운트 +1 해주면 된다.여기서 문자열 w와 매치된다는 것은 W의 순열 중 하나가 부분 문자열로 들어있는 모든 경우의 수를 의미하는데, 슬라이딩 윈도우 진행하
링크처음에 문제를 잘못 읽어서 입력으로 들어오는 a, b를 union 연산 하라는 줄 알았는데 알고보니 a가 b의 부모 관계였다. 따라서 유니온 파인드의 기본 풀이인 부모를 찾는 과정은 입력 자체로 바로 알 수 있으니 패스.마지막 줄에 입력된 두 노드에 대하여 가장 가
링크계속 더하다보면 heap의 길이가 0이 아니라 1이 된다는 것 잊지 말기
링크입력값이 매우 작아서 시간복잡도를 신경 쓰지 않고 순열 사용동일한 정수를 만들 수 있는 경우의 수가 여러개일 수 있기 때문에 중복 방지를 위해 set 활용join 함수 쓸 때 리스트 내부 원소 str 타입이어야 함 주의 !
링크union 함수와 find 함수만 알면 풀 수 있는 문제union 함수 내 변수 주의
링크보통 집합의 원소가 숫자로 되어 있는 경우가 많은데 여기선 문자열이 들어오기 때문에 딕셔너리를 사용해준다 <- 여기까진 스스로도 생각해내었음 근데 한 줄씩 입력될 때마다(친구 관계가 생길 때마다) 두 사람의 친구 네트워크에 몇 명이 있는지 세어주는 걸 어떻게
링크해당 문제에선 중간값을 계속해서 업데이트 하기 위해 힙을 두가지를 쓴다.하나는 leftHeap(최대힙), 다른 하나는 rightHeap(최소힙)이다.두 힙의 길이의 균형을 맞추기 위해 번갈아가며 현재값을 넣어주는 것이 핵심이다. 이렇게 하면 중간값은 항상 LeftH
링크걍 완탐으로 인덱스 잘 생각해서 풀면 됨
매우 쉽고 제출만해도 이렇게 있어보이는 Certificate가 나온다(총 2문제, 120분)코테에서 rest api 호출하는 문제도 가끔 출제하니 한 번 풀어봐도 좋을 듯하다REST API 해커링크 문제는 여기서 보면 된다다른 건 모르겠고 영어싫어인간에게 영어지문은 언
링크그리디하게 풀어내는 문제이다.풀이 순서는 다음과 같다pop()을 통해 배달/수거를 해야하는 가장 먼 집을 찾는다.answer는 배달/수거를 해야하는 가장 먼 거리에 2를 곱하여 더해준다. 2를 곱하는 이유는 왕복거리를 계산하기 위함이다.배달 및 수거는 독립적인 행위