WIZI Blog

programmers.co.kr/learn/courses/30/lessons/72410 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문제를 보면 단계가 주어진다. 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다..

www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 과정 1. 각각의 섬들을 bfs를 사용하여 구분한다. 코드에서 color 변수가 구분해주는 역할을 한다. 1번섬은 1로 표시 2번섬은 2로표시... 2. 구분된 섬들을 저장한 map배열을 순회하면서 가장자리인 {i,j}와 가장자리가 몇번섬의 가장자리인지를 함께 edge vector에 넣는다. 3. edge벡터를 2중 반복문으로 택시거리를 이용해서 거리를 구한 후에 가장 최소값 저장후 답에서 -1을 했다. 가장자..

www.acmicpc.net/problem/16947 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 문제 풀이 과정 1. 주어진 노드들로 부터 싸이클을 판별한다. 2. 정점을 돌며 싸이클에 속하는 노드면 0을 출력하고 그렇지 않다면 가장 가까운 싸이클까지의 거리를 출력한다. 싸이클 판별을 어떻게 해야 간단하게 구현할까 생각을 해봤다. 일단 내가 선택한 방법은 dfs의 인자로 (첫 시작노드, 현재 보고있는 노드, 깊이) 를 주었다. 그리고 만약 깊이가 2이상이고 현재 보고있는 노드에 ..

programmers.co.kr/learn/courses/30/lessons/49191?language=cpp# 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 결과적으로 플로이드 와샬 알고리즘을 사용하면 풀리는 문제였다. 그렇다면 왜 플로이드 와샬 알고리즘을 사용하면 되는 것일까? 아래의 표는 문제의 테스트 케이스를 플로이드 와샬 알고리즘을 사용한 후의 dist 배열을 출력한 것이다. 0 1 INF INF 1 -1 0 -1 -1 1 INF 1 0 -1 1 INF 1 1 0 1 -1 -1 -1 -1 0 플로이드 와샬 알고리즘은 반복문을 돌면서 모든 지점을 비교하여 최단거리가 갱신되는데, 이때, 순위가 확실하게 이기거..

www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 프로그래머스 - 가장 큰 수 문제와 비슷하다. 오세준이 현재 가지고 있는 K개의 수들 중에서 이 수들을 적어도 한번 이상 사용해서 만들 수 있는 가장 큰 수를 만들어야 한다. 만약 수가 3개가 있다고 생각해보자 [3, 4, 10] 3개를 이용해서 만들 수 있는 가장 큰 수는 4310이다. 4개를 이용해서 만들 수 있는 가장 큰 수는 431010이다. K개가 주어지고 K+N 만큼 수를 ..

programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 내림차순 정렬을 풀 수 없는 문제다. 예제에서 [3, 30, 34, 5, 9] 의 경우를 살펴보자 이를 내림차순 해보자 => [34, 30, 9, 5, 3] 답 : 3430953 그렇다면 맨 앞자리부터 순서대로 큰 순서로 정렬을 한다면? [9, 5, 34, 30, 3] or [9, 5, 34, 3, 30] 이런식..

*문제출처* programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 문제 분석 가로(W), 세로(H) 길이의 직사각형이 주어진다. 1X1 크기의 정사각형으로 자르고 대각선을 그었을 때 온전한 정사각형의 개수를 구해보자 처음 문제를 접했을 때 DP로 접근하였다. 하지만 4*10 정도 크기를 직접 구해보니 규칙이 없어서 이 방법은 포기하고 다른 방법을 강구하였다. 1차함수를 배운 사람이라면 쉽게 풀 수 있는..

DFS로 풀게되면 시간초과의 우려가 있어 DP로 풀었다. 현재칸을 ( i, j )라고 했을 때, ( i, j-1 ) 의 칸에서 이어지는 경우, ( i-1, j ) 의 칸에서 이어지는 경우, ( i-1, j-1 ) 의 칸에서 이어지는 경우 3가지의 경우로 파이프가 이어질 수 있다. 3차원배열을 선언하여 각 칸에 들어오는 파이프의 개수가 가로에서 들어왔는지, 세로에서 들어왔는지, 대각선에서 들어왔는지 개수를 세주었다. index => 가로 : 0 대각선 : 1 세로 : 2 각 그림에서 주황색 칸은 값을 채우려는 현재 위치이고 빨간색 화살표는 파이프가 이어지는 방향, 파란색 화살표는 이으려는 파이프의 이전 파이프의 방향이다. 1. ( i, j-1 ) 칸의 경우 가로로 이어지는 경우 dp[0][i][j] = d..

문제링크 : https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 최대 M개의 치킨집을 골라서 도시의 치킨 거리 최소값을 구해야한다. 다만,, 최대 M개를 고를 수 있는 것이므로 1개 부터 M개 까지 경우를 고려해야 한다. getAns() : 선택한 치킨집을 통해 치킨거리를 구하는 함수 solve(int cnt, int istart) : 주어진 치킨집에서 1~M개를 고르는 조합을 구현한 함수

문제링크 : https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커� www.acmicpc.net 인풋이 주어질때 좌표평면의 x,y값으로 주어져서 굉장히 헷갈리는 문제였다. 코드를 짤때 애초에 r,c를 이용했으면 덜 헷갈렸을 문제이다. 문제풀이 : 처음 좌표를 벡터에 담고 d값을 통해 두번째 좌표 또한 벡터에 담는다. 이 과정에서 벡터에는 0세대 드래곤 커브가 담겨있다. 이제 0세대 드래곤 커브를 1세대로 , 1세대 드래곤 커브를 2세대로 ... n세대..