Algorithm

이진탐색(binary search)리스트에서 특정 수를 찾는데 쓰이는 알고리즘단순히 n개의 리스트에서 x를 찾기 위해서는 간단하게 O(n)의 시간복잡도로 풀 수 있는 방법이 있음(리스트를 전체 탐색해보면 됨). 그러나, 이 방법은 n = 1억이 되는 순간 너무나도 커지

해쉬 구조Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄(ex, name_dict = {'name':'yongki'}/ name

1) 선택정렬(selection sort)정렬된 쪽과 정렬되지 않은 쪽 이렇게 두개로 나눠서 생각한다.정렬되지 않은 리스트를 받았을 때, 첫 번 째 요소를 가지고(비교의 기준점) 그 외의 나머지 요소들과 비교한다.나머지 요소들 중에 비교의 기준점이 되는 요소보다 작은

1) 유클리드 호제법=> 최대 공약수와 최소 공배수(최소공배수=구하려는 두개의 수의 곱/최대공약수)와 연관된 이론!​먼저,출처 : 한국정보올림피아드 지역본선 2004 중등부 1번, 고등부 1번 이 문제를 유클리드 호제법이 아닌 방법으로 구현해보면,이렇게 풀어볼 수 있다

질문에 적혀있는 숫자가 실제로 주어진 숫자중에 몇개나 포함되어 있는지를 '세는' 문제그러나, 간단하게 물어보는 숫자가 있는지를 알기 위해 리스트를 한번 쭉 탐색하는 방법은 리스트의 개수(N), 질문의 개수(M)이라할 때 결국 O(N\*M)이 되어 O(N2)이되는데, 여

먼저 이 문제는 한번에 풀지 못했다..일단 이중 for문으로 접근하면 풀 수 없다. N이 최대 100,000이기 때문에 이중 for문으로 풀면 시간복잡도에서 걸린다.따라서 다른 아이디어를 떠올려야하는데, 탐색을 처음부터 하지않고, 먼저, 리스트를 정렬한 뒤에 양쪽에서

SWEA 문제 링크 - 시각 덧셈

SWEA 문제 링크 - 어디에 단어가 들어갈 수 있을까완전 탐색으로 풀어서 전체 row, column을 한줄씩 체크함경계 에러 처리로 배열의 테두리에 임의로 -1을 채워넣음0,-1을 만났을 때 1을 세는 카운트가 3이면 result+=1해줌으로써 정답을 얻음

SWEA 문제 링크 - 조교의 성적 매기기왜그랬지는 모르겠으나..ㅎㅎ 문제를 제대로 안읽고 총점 계산을 마음대로 int로(정수)형으로 바꾼다음 계산했음.그 결과 fail.. 이 떴고 한참을 고민하다가 간신히 디버깅 성공...ㅎ

SWEA 문제 링크 - 초심자의 회문검사요즘 재귀함수를 많이 쓰다보니까 떠오른 발상양옆의 요소를 비교하면서 끝에가서 남은 요소가 1개일 때 혹은 2개 일때를 기저조건으로 놓고 재귀함수로 만드니까 간단한 체크 함수가 만들어졌다

SWEA 문제 링크 -파리퇴치조건이 m<=n<=30이였기에 메인 로직을 4중 for문으로 할 수 있었던 것 같다. 만약 n<=1000 이런식의 문제였다면 다른 방법으로 풀어야했을 것 나는 완전탐색법으로 풀었다. board라는 모기가 담긴(?) 판을 먼저

우선순위 큐란 간단하게 말해서 일반적인 큐와 달리 pop을 할 때 임의로 '우선순위'를 정해놓고, FIFO(First In First Out)를 따르지않고, 정해진 우선순위대로 pop이 되는 큐를 말한다.그래서 push를 할 때는 js에서 push() 메서드를 해주는

dessert 문제합병정렬, 퀵정렬 다시 구현해보기숫자 개수 세기두 용액 문제 NN 단표접시, 괄호의 값(stack 관련 2문제)트리 순회 결과 출력하기 레벨 14, 15 이론 및 \*문제 풀기

: 문제를 해결하는 데에 있어서 문제를 해결만하면 장땡(?)이라는 접근보다는 옛날에 비문학 지문을 풀 때도 일정한 스텝이 있듯이 알고리즘 문제를 풀 때에도 일정한 스텝을 정해놓고 푸는 것이 좋을 것 같고, 그 부분에 대해서 포스팅을 해보고자 한다.1) 문제를 정확히 이

: 거창한 제목이지만, 사실 내가 모듈러 연산에 대해서 깊게 팔 자신은 없는 것 같다. 인터넷을 통해서 몇분이긴하지만.. 살펴봤지만 수학적인 개념(유클리드 호제법과 같은)인데, 블로그 내용만으로 내가 학습하기에는 약간 한계가 있는 것 같아서, 일단 오늘은 모듈러 연산을

: 분할정복법은 사실 거창한 이론은 아니고, 여태까지 공부했던 합병정렬, 퀵정렬을 구현할 때도 사용했던 일종의 방법론이다. 알고리즘을 설계하는 데에 있어서 문제를 몇개의 부분으로 나누고(Divide), 나눈 부분을 각각 정복하고, 그 정복한(해결한) 부분을 합쳐서 최종

:간단하게 재귀함수에 대해서 정의를 해보면,재귀함수는 '자신을 통해서 자신을 구하는 함수'라고 할 수 있다.흔히 재귀함수 관련해서 러시아 인형(?)을 얘기하는 것도 이러한 맥락인데하나의 러시아 인형이 존재(?)하기 위해서 그 안에 겉에서는 보이지 않는 수많은 다른 러시

1) 재귀함수를 이용해서 n\*\*m을 리턴하는 함수2) 재귀 함수를 이용해서 n부터 m까지의 합을 리턴하는 함수3) n을 입력받고, n의 각자리수의 합을 구하는 함수4) 문자를 입력받고 그 문자가 palindrome인지 판별하기

동적계획법 문제를 풀 때는, 사실 문제를 낼 때 "이건 동적 계획법 문제니다."라고 하지는 않으므로, 내가 찾아내야하는데, 이 문제는 구슬의 개수 범위가 1,000,000이라는 점을 토대로 일단 제일 처음 접근해볼 수 있는 해결책인 '완전탐색(brute-force)'가

: 이전에 이문제를 분할정복법, 완전탐색법 이렇게 두가지 방법으로 풀어본적이 있는데 오늘은 이 문제를 '동적계획법'을 써서 풀어보고자 한다. 이렇게 보면, 동적계획법은 일종의 규칙을 찾아내서 푸는 방법인 것 같고, 나머지는 완전탐색법 -> 좀 더 효율적인 완전탐색법 이

직사각형의 합 문제 풀이 및 해설 : 오늘은 DP 혹은 Dynamic Programming으로 불리는 동적계획법과 관련된 문제에 거의 집착(?)하듯이 풀었는데 이문제도 그 유형이다. 이 유형은 많이 풀어보는게 답이라해서.. 일단 이번주에는 최대한 많은 문제를 접해보

제곱수의 합 - 백준 알고리즘 사이트: 본래 백준 알고리즘에서 이 문제를 푼 것은 아니지만, 거의 똑같은 문제가 있길래 일단 링크를 첨부한다.: 사실 이문제는 한번에 풀지 못했다. 인터넷에 해설을 양심적으로 약간 흘끗(?) 보고 또 생각을 해보고, 간신히 푼 문제이다.

1) 그래프와 관련된 수학적 규칙에 대하여그래프의 노드(정점이라고도 함)와 노드를 이은 선을 간선(edge)이라고 하고, 한 노드를 기준으로 다른 노드와 이어진 간선의 수를 '차수'라고 한다. 이 때, 전체 차수의 합은 간선의 2배가 된다. 이유는 차수를 더하다보면 결

: 먼저 구현한 코드부터 올려보면 위와 같다. DFS는 스택을 사용해서 그래프를 순회하는 것인데, 스택이란 일종의 발자취를 기록하는 자료구조와 같다. 또한, 스택은 재귀함수로 구현되기 때문에 결과적으로 DFS도 스택으로 구현할 수 있다.: 위의 그림을 DFS 방법으로

BFS의 원리 및 개념 설명1) BFS는 큐를 이용해서 구현한다.2) 넓이 우선 탐색이라는 이름에 맞게 깊이 우선 탐색과 달리 층마다 모든 요소를 훑으면서 내려간다. 실제 구현 코드: 위의 그래프를 BFS 순회하기 위해 아래와 같은 코드를 짜봤다. 이 때, 그래프 객체

: 왼쪽 최하단 좌표에서 우측 최상단 좌표로 이동하는 경우에 최단거리로 가는 거리가 얼마나 되는지를 구하는 문제이다. 0,1 로 이뤄진 좌표에서 1은 지날 수 없는 부분이고, 0만 지날 수 있다. n\*m의 크기를 가졌는데, n,m 각각 1보다 같거나 크고, 천보다 작

: 이전에 '미로 찾기' 문제와 똑같은 문제지만, 거기에 목수가 하나의 장애물을 부술 수 있다는 조건이 추가된 문제이다. 특정 좌표 x,y에서 z,a까지의 '최단거리'를 구하되, 중간에 1로 표현된 장애물이 있는데, 이 장애물 중에 하나를 부술 수 있는 조건이 추가된

: 아침 8시 30분 부터 9시 30분까지 한시간의 시간 제한을 두고 풀었으나, 결국 풀지 못했다. 사실 문제 자체가 뭘 요구하는지 명확히 파악도 제대로 못한 것 같다. 주어진 예제를 보고도 잘 이해가 안됐으니까..ㅎ 나는 모든 완료시간을 날짜를 제외하고 초단위로 먼저

: 처음에는 BFS를 써야겠다는 생각조차 하지 못했지만 BFS로 간단하게 풀 수 있는 문제: 일단 문제에서 요구하는 것은 특정 수 N을 주어진 조건의 이상한 계산기로 만들기 위해서 몇번의 버튼을 눌러야하는지를 구하는 것이다. 이 때, 계산기에서 할 수 있는 선택지는 \

문제를 명확히 이해한다. 문제에서 요구하는 것이 무엇이고, 그 사이사이에 어떤 제한 조건 등이 있는지를 디테일하게 파악해둔다.이해한 문제를 바탕으로 설계를 한다. 이 때, 문제에 대한 명확한 이해가 돼있어야 이 문제의 풀이 로직도 제대로 짤 수 있다. 가장 먼저 생각해

: 알고리즘 잡스에서 푼 문제중에 역대급.. 이거 결국 혼자 힘으로는 60점 밖에 못냈고 3일에 걸쳐서 풀었다.. 이렇게 풀면 안되긴 하는데 이 고비를 스스로 넘겨야 할 것 같았다..BFS ^^ : 특정 좌표에서 로봇에게 명령을 내려(1,2번) 특정 좌표로 이동하게 할

알고리즘 잡스 / CHEEZE 문제: 치즈와 치즈가 놓여진 판이 주어진다. 판 위에 치즈가 놓인 정보를 바탕(2차원 배열)으로 치즈가 '공기와 닿는' 부분을 1시간 마다 없애면서 치즈가 모두 없어지기 까지 몇시간이 걸리고, 마지막 없어지기 1시간 전의 판위의 치즈가 차

[알고리즘 잡스 / TOMATO] :

출처 : 알고리즘 잡스: 구현 코드 깃헙 링크: 전형적인 시뮬레이션 문제였던 것 같다. 이런 문제는 정말 한번에 풀어야하고, 한번에 못풀더라도 코드를 간소화해서 에러 핸들링에 유용하도록 해야한다. 잔실수가 일어날 수 있기 때문에 코드 간소화는 항상! 그리고 여기서 내가

문제는 저작권이 있어서 올릴 수 없으나 나혼자 복습하기 위해문제 해석 및 풀이 링크를 올린다깃헙 문제 풀이 및 코드 링크

: 레벨 체크 lv3에서 이 문제 때문에 통과를 못했다... 나머지 한문제는 제대로 기억은 안나는데 DB를 이용해서 푸는 문제였다(피보나치 유형). 아쉽지만 lv3은 다시 도전해보도록 하고! 오늘은 이 문제를 파헤쳐본다.문제 링크: 문제에서 요구하는 것은 주어진 심사관

: 일단 과거에 코드스테이츠에서 거의 똑같은 문제를 단순히 알고리즘 문제 풀이 말고, 좀 다른 방식으로 푸는 세션을 했던 것 같은데.. 어쨌든 한번에 못풀고 헤맸다.: 체스의 퀸이 갈 수 있는 방향은 왼쪽, 오른쪽, 위쪽, 아래쪽, 대양옆 대각선이고 거리는 자유이다.

: 건방진(?) 얘기지만.. 이게 왜 정렬 파트에 있으며(예를 들어 병합정렬, 퀵정렬 등을 쓰는 문제도 아니고..), 문제 자체가 쓸데없이 복잡하게 주어진다. 문제를 푸는 로직이 복잡한게 아니라 문제 워딩을 애매하게 해서 어렵게 낸 문제?...

: DFS 백트랙킹을 이용해서 풀었다. 코드가 약간 지저분한데 한번더 풀 때는 좀 더 간결화한 코드로 풀면 좋을 것 같다!: 프로그래머스 타겟넘버 풀이

프로그래머스 네트워크 문제 문제 해석 : 문제 자체는 어렵지 않다. 컴퓨터의 수 n과 컴퓨터간의 연결관계를 나타내주는 2차원 배열을 받아서(0이면 비연결, 1이면 연결), 전체 네트워킹이 몇개나 형성돼있는지를 구하는 것이다. 이 때, 네트워크 단위는 연결단위이다. 즉

프로그래머스 단어변환 문제 구현 코드 def solution(begin, target, words): answer = 0 BFS ! queue = [begin] path = {} path[begin] = True def is_possible(word1,word2): cnt = 0 for ...

: 2번만에 해결할 수 있었다. 솔직히 처음에는 문제 스케일에 압도(?)돼서 이상한 생각을 해서.. 헤맸던 것 같고, 차근차근히 풀어보니까 은근히 쉬운 문제였다. 하지만 코드 길이도 그렇고 확실히 스케일이 있는 문제인 것 같다정보를 통해 주어진 물풍선을 주어진 바늘의

: 휴.. 시간 초과(효율성 1번) 때문에 별짓을 다해본 문제이다. 내 풀이가 잘못된건가 하여 분할정복법도 써가며 풀어봤지만 불가능한 방법이었고, 결론적으로 파이썬 내장 함수를 쓸 때 시간복잡도를 잘알고 써야겠다는 생각이 든다.: 문제 자체는 간단하다. 주어진 문자열에

: 계속 고민하던 포인트에서 막혀서 못푼 문제. 근데 그 해답이 heap에 있었던 문제이다. 계속 고민하던 포인트는 결국 계속해서 최대값에 -1을 해주면서 n을 소비(?)해 나아가는 것이 문제 풀이 방법인 것 까지는 알았는데, 계속해서 최대값을 찾느라 max()를 써서

: 한번에는 못풀었는데, 이유는 문제를 제대로 이해하지 못해서이다..: 항공권 티켓(왕복이 아닌 편도행)이 tickets로 주어지는데, 그러한 항공권 티켓을 바탕으로 '여행 경로'를 짜야한다. 이 때, 티켓은 반드시 ICN에서 출발해서 비행기를 타고, 타고, 타서 어딘

: 규칙을 찾아내면 쉽게 풀 수 있던 문제: n과 s가 주어지면 n개의 숫자를 이용해서 합이 s가 되는 조합(집합)을 찾는데(이 때, 집합은 중복집합이라해서 중복을 허용하는 집합이다), 이중에 n개의 숫자의 곱이 가장 큰 조합을 찾아서 리턴하는 것이 문제이다.: n개의

: 예를 들어, 리스트에 어떤 정보를 쌓아가면서 길이가 4가 됐을 때 조건을 체크한 다음에 조건을 충족하면 answer +=1 을 하고, 리스트를 reset하고 다시 탐색해 나아가는 형식의 문제를 푼다고 해보자. 그리고 이것을 N\*N배열에서 한다고 할 때, 하나의 r

매일 3개씩 알고리즘1) 프로그래머스 - 문자열 압축2) 프로그래머스 - 수식 최대화3) 프로그래머스 - 2개 이하로 다른 비트 10:10 ~ 11:50(1h 40m)3번 하나 풀었다. 그것도 힌트보고 풀음...나머지 문제는 시간상 문제도 못읽음어렵다..<a hr

프로그래머스 - 게임맵 최단거리 (solve)프로그래머스 - 방문 길이 (solve): 주말에 1시간씩 투자해서 알고리즘 잡스 문제 각각 한문제씩만 풀자

구현 목표 : push 메서드 만들기(O(logN)의 시간복잡도를 갖는)pop 메서드 만들기(O(logN)의 시간복잡도를 갖는)top 메서드 만들기(O(1)의 시간복잡도를 갖는)length 메서드 만들기(Heap 내의 노드의 개수를 출력해주는 메서드)먼저 Heap 객체

: 결국 스스로 풀지 못하고 힌트 보고서 풀 수 있던 문제. 이런 문제는 솔직히 딱 DP다 DFS다 해서 풀 수 있는 문제라기보다는 어렴풋 보이는 문제의 규칙을 하나하나 헤매가며 풀 수 밖에 없는 문제이기에 그러한 풀이 과정을 따라가보고자 한다. 그래야 다음에도 이런

: 그렇게 효율적인 코드인지는 모르겠지만 시간복잡도 관련 문제는 아니었어서 구현(시뮬레이션) 문제라고 생각하고 분기처리에 집중했다. 사실 작년 공채 시험을 봤었기에 알고 있던 문제긴 했다. 당시에 이문제는 굉장히 쉽게 풀었던 것 같은데 확실히,, 코딩테스트도 안풀어 버

링크 : 프로그래머스 - 양궁대회레벨 : 2출처 : 카카오 2022 블라인드 공채 기출문제1) 문제 해석최종 구현 요구 사항 : 라이언이 어피치를 이기는 케이스 중 가장 큰 점수차로 이기는 케이스를 배열에 담아 리턴하는 것추가 조건1) 만약에 가장 큰 점수차로 이기는

프로그래머스 분수의 덧셈 문제: while 문을 써서 분모를 통합하고, 그만큼을 분자에 곱해주고, 말그대로 분수의 덧셋 패턴을 이용해서 분수를 더해 준다음에 구한 값의 분자, 분모의 공약수를 써서 다시 기약 분수로 나타내면 되는 문제이다. 나는 굳이(?)라기보다는 좀

프로그래머스 코딩테스트 연습 - 나머지 구하기: 너무 쉬운 구몬 학습과 같은 문제들이지만 너무 오랜만에 코테 문제를 풀어서 이렇게 가벼운 문제들로 워밍업을 해보고자 풀어본다(왜 혼자 핑계를 대시고 계시죠..?): 문제는 너무나도 간단하다. 너무 간단해서 나만의 룰을 추