알고리즘

[Python] 프로그래머스 고득점 Kit (정렬) : K번째 수

문제 코딩테스트 연습 - K번째수 [ 문제 풀이 ] 문제에서 제시한 대로 array를 여러 commands 배열의 0번째 값 부터 1번째 값 까지 잘라낸 후 자른 배열 정렬 후 2번째 값 인덱스를 return 하면 되는 간단한 문제다. 다른 짧은 풀이도 봤는데, 한줄로도 풀 수 있는 문제였다. 나는 몇 줄에 걸쳐했지만,, 문법 공부하자... 코드

[알고리즘] dx, dy 좌표 상하좌우 탐색 로직

탐색 알고리즘 문제를 처음 접하는 분들은 상하좌우 탐색할 때 (0, -1)인데 x, y좌표 그려서 생각해보면 아래쪽인 것 같은데 왜 왼쪽을 탐색하지? 라고 헷갈릴 수 있다. 필자도 처음에 이해가 안되었다. # 좌, 우, 상, 하 dx = [0,0,-1,1] dy = [-1,1,0,0] 필기를 하면서 직접 그려보니 이해가 쉬웠다. (1, 1)을 현재 위치라고 가정하고, 왼쪽으로 이동하면 값이 (1, 0)으로 y값이 -1 되어야 한다. 오른쪽으로 이동하면 (1, 2) 위치가 되므로 y 값을 +1 해주어야 오른쪽 이동이 된다. 상, 하 이동도 마찬가지이다. 코드만 봐서는 잘 이해가 안갔던 부분이, 직접 손으로 그려보니 이해가 빨랐다!

[Python] 프로그래머스 고득점 Kit (해시) : 전화번호 목록

문제 코딩테스트 연습 - 전화번호 목록 [ TIL ] 접두사를 찾을 때 str.startwith(접두사) : str에 해당 접두사가 포함되면 True를 리턴, 아니면 False를 리턴 str.startwith(접두사, end) : 선택적으로 end를 사용하면 해당위치에서 비교를 중단 정렬할 때 list.sort() : 원본 리스트를 변형시켜 정렬한다. sorted(list) : 정렬된 결과를 반환하여 새로운 리스트를 내보냄. 원본 리스트는 변하지 않는다. ✏️한줄평 : 파이썬 문법을 잘 모르니 계속 구글링 하는 한계가 발생한다. 파이썬 공부도 코테를 위해 꾸준히 해야겠다. 코드

[Python] 백준 15992번 : 1, 2, 3 더하기 7

문제 15992번: 1, 2, 3 더하기 7 [ 문제 조건 ] 정수 n을 가지고 m개의 수를 사용해야 함. 즉, 4를 가지고 2개의 수를 사용한다면 (2+2), (1+3), (3+1) 총 3개의 경우의 수가 있을 것이다. [ 해결순서 ] dp 문제는 늘 전에 계산한 값들을 다시 이용해서 사용해야 하므로 고정된 범위의 1~3의 값을 미리 계산해서 dp 배열에 넣었다. 그리고, 첫번째 시도 풀이에서 메소드를 넣어 값을 구하려고 했는데 이렇게 하면 시간초과가 발생한다. ❗️ 여기서 중요하고 내가 간과한 사실을 알아냈는데, 메소드로 반복해서 값을 구하면서 dp 배열을 계산하면 테스트 케이스만큼 dp 배열의 값을 계산하게 된다. 한번 구해서 갱신한 dp 배열은 공유해서 사용하기 때문에 굳이 테스트 케이스마다 중복..

[Python] 카카오 2021 BLIND : 신규 아이디 추천

문제 코딩테스트 연습 - 신규 아이디 추천 [ 문제 조건 ] 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다. 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니..

[Python] 백준 5567번 : 결혼식

문제 5567번: 결혼식 [ 문제 조건 ] n : 동기의 수 (즉, 숫자의 종류) m : 친구 관계 나타내는 리스트 개수 [ 해결순서 ] 상근이는 결혼식에 자신의 친구 + 친구의 친구까지 초대 가능하므로 너비우선탐색을 이용해서 자신의 친구먼저 몇명인지 탐색 후 친구의 친구까지 탐색한다. bfs 메소드를 이용해서 친구 1명을 먼저 구한다음 그 친구의 친구까지 탐색하고 다음 친구의 친구의 친구 탐색하고 초대인원 값 + 1하면 깊이를 계산해서 깊이가 2이면 (친구의 친구까지만 초대가능하므로) 총 초대인원 출력하고 종료한다. ✏️한줄평 : 처음에 이진트리를 생각해서 그렇게 풀려고 했는데 사실 굳이 그럴필요 없이 그냥 bfs로 친구들 탐색하고 깊이 +1 하다보면 구해지는 문제였다. 코드

[Python] 백준 14888번 : 연산자 끼워넣기

문제 14888번: 연산자 끼워넣기 [ 문제 조건 ] 입력 N : 수의 개수 A1 ~ An : 수들 sum(N-1) : 합이 N-1인 4개의 정수, 연산자 4개의 각각 개수가 주어짐 (+,-,×,÷) 순으로 출력 만들 수 있는 식의 최대 & 최소 값 출력 -10억 ≤ 결과값 ≤ 10억 [ 해결순서 ] 백트래킹 유형은 dfs를 주로 사용하는 것 같아 dfs로 풀어보려고 했다. 모든 경우의 수를 전부 구해 최대 최소를 비교하는 문제여서 어쨌든 모두 비교해서 구해야한다. 처음 먼저 plus가 1이니까 dfs가 걸려 깊이우선탐색 후 나머지 연산까지 깊이우선탐색 해 값을 갱신 깊이우선탐색 plus 연산은 끝났고, 나머지 연산 중 multiply 값이 1이므로 해당 연산 기준으로 재귀적으로 dfs 진행 후 최대, ..

[Python] 백준 1074번 : Z

문제 1074번: Z [ 문제 조건 ] Z 모양 순서대로 방문 입력한 r행 c열이 몇번 째로 방문하는지 출력 [ 해결순서 ] 1번째 풀이 -> 실패 재귀적으로 모든 분면의 모든 값을 확인해서 2X2 배열일 때 ( 더이상 등분하지 않아도 되면 ) 조건에 맞을 때까지 값을 하나씩 늘려가면서 몇번째 방문인지 계산하다가 r행 c열의 조건이면 여태껏 더한 방문값을 출력하고 종료한다. 이렇게 하면 시간 초과가 날 뿐만 아니라, 입력한 값에 포함하는 분면이 아닌 값들도 모두 확인해 비효율적인다. 2번째 풀이 (참고) 이 풀이는 아이디어를 참고한 후 코드를 짜면서 해석했는데, 이 문제를 풀 때 내가 처음에 생각해낸 아이디어와 비슷했다. (코드를 못 짜겠어서 1번째 풀이로 풀었지만..) 입력한 값이 몇 사분면인지 계산한..

[Python] 백준 11051 : 이항 계수 2

문제 11051번: 이항 계수 2 [ 문제 조건 ] nCk 를 구하면 된다. [ 해결순서 ] 먼저 분류가 DP라서 DP로 해결하려 했다. 팩토리얼 값들을 저장하기 위해 dp배열을 선언해서 반복해서 곱한 값들을 배열에 저장하였고 계산 된 값을 그냥 공식에 맞게 출력했다. nCn이나 nC0인 경우는 값이 그냥 1이기 때문에 조건문을 추가하였다. ( 넣지않아서 에러가 발생했다 ) 파이썬에 내장되어 있는 factorial 모듈도 있길래 그것도 사용해서 풀어봤다. 3줄만에 풀 수 있었다 ! ✏️한줄평 : 재귀적으로 팩토리얼을 구하지 않고 dp로 풀어볼 수 있는 문제였다. 코드

[Python] 백준 1309번 : 동물원

1309번: 동물원 [ 문제 조건 ] 2 * N 배열의 동물원 우리 사자를 배치할 때 가로 세로로 붙어있으면 안됨 사자가 한마리도 없는 경우도 1가지 경우로 침 [ 해결순서 ] 처음엔 기존의 dp 같은 방식으로 풀려고 시도해 배열의 각 칸에 숫자를 부여해서 조건에 맞는 조합으로 값을 계산해서 구하려고했다. 뭔가 규칙이 보이는 것 같다가도 막상 식을 못세우겠어서 조금 헤매다 결국 구글의 도움을 좀 받았다. ( 삽질을 하고있단 느낌이 .. ) 첫번째 줄에 경우를 3가지로 나눠서 계산을 해야한다. *4번 줄 참고 경우의 수를 나눈 후 제일 작은 예시인 2 X 2 배열일 때를 직접 적어가며 규칙을 찾아보려했다. 사진을 참고하면 이해가 빠르겠지만, 한마리도 두지 않는 경우는 ( 두지 않는 경우, 왼쪽, 오른쪽 )..