algorithm

🔒 문제 💡 생각의 흐름 1,2,4 3개의 숫자만으로 한 자리씩 표현 총 자릿수는 3^N + 3^N-1 + 3^N-2 .... 3^0 => N+1 의 문자열 길이를 갖는다. 군 내에서 N번째 숫자를 3^N * n + 3^N-1 * n ... N+1 만큼 loop을 돌고 n을 이어붙이면 된다고 생각했다. 먼저, 10진수 -> 124나라의 숫자가 바로 생각나지 않으니 124나라의 숫자 -> 10진수변환을 곱씹어 보았다. 예를들면 10진수 '241' 3^2 * 2 + 3^1 * 4 + 3^0 * 1 >[0단계] 3마다 단위가 바뀌는 걸로 봐서 3진법!!!!!?!?!?! 근데 숫자 0과 4를 따로 처리해야겠네? [1단계] 124나라의 숫자의 길이 == 3^1 + 3^2 + 3^3 + .... 3의 제곱수의 누적..

1. 문제 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr ⭐ 카카오 2019 블라인드 공개채용 기출문제 2. 실수 loop을 2번 중첩했다가 시간초과로 75점을 맞았다. loop 2중첩 시나리오는 다음과 같았다. 아이디 - 닉네임이 매핑되어야 한다는 사실로부터 (1) 중복을 제거한 아이디 목록 Set (집합) (2) Set element 수 == 회원수 만큼 loop (3) (2) loop 안에서 record 로그 수만큼 또 loop (2) + (3) => Time Complexity O(N^2) => 시간..

문제 해결 방법 문제를 읽자마자 "전체 참가자 Set - 완주자 Set 으로 풀면 되겠다!"고 생각했고 멋지게 틀렸다. 제한 사항에 다음과 같은 문장이 있다. 참가자 중에는 동명이인이 있을 수 있습니다. * Set은 '중복'을 허용하지 않는 자료구조이기 때문에 동명이인 처리가 불가능하다. 내 아이디어는 이렇다. HashMap 를 생성하여 동명이인 수 '1명' 이 되는 사람의 이름을 구하자. 구현 (Java)

문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결 방법 행렬에 1로 되어있는 영역 (Graph) 갯수를 구하는 문제 BFS로 풀이한다. 노드간 연결을 수행할 때 양방향으로 해야하는지 단방향으로 해도 되는지 판단한다. 연결 대상 탐색은 우-하방향으로 하고 연결은 양방향 (우-좌, 하-상) 다 수행한다. 구현 [OrganicCabbage.kt] [main.kt]

문제 아이디어 총 단지수 == Graph 갯수 단지 내 집의 수 == Graph 내 노드(Vertex) 수 출력으로 요구하는 값만 봐고 DFS & BFS가 떠올랐다. 총 단지수 => main 에서 DFS 호출 수 단지 내 집의 수 => 한 DFS 내 재귀 호출 수 그래프 연결작업 => 행렬 전체를 돌며 '오른쪽, 아래'로 연결된 [행번호,열번호] 양방향 연결 리스트 추가 약간 헷갈렸던 것이 단지 내 집의 수 (DFS내 재귀 호출 수 카운트) 하는 부분이었다. DFS 코드 // main에서 마지막 argument로 DFS 호출 횟수를 keep하는 변수를 넘겨서 fun dfs (rowIndex: Int, colIndex: Int, callCount: Int) { //start vertex 는 0,0 가정 상..

문제 아이디어 정점, 간선 단어를 보자마자 '그래프'? 연결 요소 == 이어진 그래프를 의미한다. BFS or DFS를 떠올린다. 나는 BFS를 선택했다. 모든 노드(정점) 목록을 원소로 갖는 집합(Set)을 두고 한 번의 BFS마다 생기는 그래프를 전체 집합에서 제외시키는 방식으로 풀이했다. (전체 집합이 공집합이 될 때까지 Loop) 실수 undirected graph (무방향 그래프) 인것을 확인하지 않고 단방향 연결 리스트로만 체크하다가 틀려버렸다. 구현 [Graph.kt] import java.util.* import kotlin.collections.ArrayList class Graph(private val vertexNumber: Int) { val vertexSet : Set = (1 ...